Zeckendorfin lause

Zeckendorfin lause on belgialaisen matemaatikko Edouard Zeckendorfin mukaan nimetty lause kokonaislukujen esittämisestä Fibonaccin lukujen summana. 

Zeckendorfin lauseen mukaan jokainen positiivinen kokonaisluku voidaan esittää yksikäsitteisesti yhden tai useamman Fibonaccin luvun summana siten, että summa ei sisällä kahta peräkkäistä Fibonaccin lukua. Summaa, joka täyttää tämän ehdon, kutsutaan Zeckendorfin esitykseksi. Formaalisti Zeckendorfin lause kuuluu muodossa:



missä  on n:s Fibonaccin luku ja  kaikilla  .

Esimerkiksi luku 100 voidaan esittää Zeckendorfin muodossa

100 = 89 + 8 + 3

Annetulle positiiviselle kokonaisluvulle Zeckendorfin esitys voidaan löytää ahneella algoritmilla valitsemalla esitykseen kullakin kerralla summan suurin mahdollinen Fibonaccin luku siten, että saatu summa ei ylitä alkuperäistä lukua. Vaikeampaa on osoittaa, että annetulle positiiviselle kokonaisluvulle on olemassa täsmälleen yksi Zeckendorfin esitys.

Lähteet

Aiheesta muualla


 Zeckendorf's theorem cut-the-knotissa

Luokka:Lukuteoria
Luokka:Matemaattiset teoreemat

de:Fibonacci-Folge#Zeckendorf-Theorem