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:

$\mathrm{\forall }N\in$ $\mathbb{N}$ $N=\sum _{i=0}^k{F}_{c_i},$

missä $F_n$ on n:s Fibonaccin luku ja $c_i\ge c_{i-1}+2$ kaikilla $i=1\dots k$ .

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.

Aiheesta muualla

• Malline:Kirjaviite
• Zeckendorf's theorem cut-the-knotissa