Zeckendorfin lause

Wikipediasta
Siirry navigaatioon Siirry hakuun

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.[1] 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.

  1. Weisstein, Eric W.: "Zeckendorf Representation." From MathWorld--A Wolfram Web Resource mathworld.wolfram.com. Viitattu 24.10.2014.

Aiheesta muualla

[muokkaa | muokkaa wikitekstiä]