Zeckendorfin lause

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 19. maaliskuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 5 muokkausta .

Zeckendorfin lause , joka on nimetty belgialaisen matemaatikon Eduard Zeckendorfin  mukaan, on lause kokonaislukujen esittämisestä Fibonacci-lukujen summina .

Zeckendorfin lauseessa sanotaan, että mikä tahansa luonnollinen luku voidaan esittää yksiselitteisesti yhden tai useamman erilaisen Fibonacci-luvun summana siten, että tämä esitys ei sisällä kahta naapurilukua Fibonacci-sekvenssistä. Tarkemmin sanottuna mille tahansa luonnolliselle luvulle N on olemassa luonnollisia lukuja  c i ⩾ 2 , c i  + 1 > c i + 1 , jolloin

jossa F n on n:s Fibonaccin luku. Tätä summaa kutsutaan luvun N Zeckendorf-esitykseksi . Fibonaccin lukujärjestelmä on rakennettu Zeckendorfin esityksen pohjalta .

Esimerkiksi Zeckendorfin esitys 100:lle on

100 = 89 + 8 + 3 .

Voit esittää 100 Fibonacci-lukujen summana ja toisella tavalla, esim.

100 = 89 + 8 + 2 + 1, 100 = 55 + 34 + 8 + 3,

mutta nämä eivät ole Zeckendorfin esityksiä, koska 1 ja 2 tai 34 ja 55 ovat peräkkäisiä Fibonacci-lukuja .

Tietylle luonnolliselle luvulle sen Szekendorf-esitys löydetään ahneella algoritmilla , jossa valitaan jokaisessa vaiheessa suurin mahdollinen Fibonacci-luku.

Historia

Vaikka lause on nimetty teoksensa vuonna 1972 julkaisseesta kirjailijasta, saman tuloksen julkaisi kaksikymmentä vuotta aiemmin Gerrit Lekkerkerker . [1] Sellaisenaan tämä lause toimii esimerkkinä Stiglerin laista .

Todiste

Zeckendorfin lause koostuu kahdesta osasta:

  1. Olemassaolo : Jokaisella luonnollisella luvulla on Zeckendorf-esitys.
  2. Ainutlaatuisuus : Millään luonnollisella luvulla ei ole kahta erillistä Zeckendorffin esitystä.

Lauseen ensimmäinen osa voidaan todistaa induktiolla . Kun n = 1, 2, 3 , väite on ilmeisesti totta (koska nämä ovat Fibonacci-lukuja), n = 4 :llä meillä on 4 = 3 + 1 . Oletetaan, että jokaisella positiivisella kokonaisluvulla  n ⩽ k on Zeckendorf-esitys. Jos  k + 1  on Fibonacci-luku, niin väite on todistettu; jos ei, niin on olemassa sellainen j , että F j < k + 1 < F j  + 1 . Tarkastellaan a = k + 1 − F j . Koska a ⩽ k , sillä on Zeckendorf-esitys (induktiohypoteesin mukaan). Lisäksi  F j + a < F j  + 1 ja koska F j  + 1 = F j + F j  − 1 (Fibonacci-lukujen määritelmän mukaan), a < F j  - 1 , joten a:n Szekendorf- esitys ei eivät sisällä F j  − 1 . Siten  k + 1 voidaan esittää F j  :n ja a:n Zeckendorf-esityksen summana .  

Lauseen toinen osa vaatii seuraavan lemman todistukseksi:

Lemma : Minkä tahansa eri Fibonacci-lukujen (ilman peräkkäisiä) ei-tyhjien joukon alkioiden summa, jonka enimmäisluku F j on ehdottomasti pienempi kuin seuraava Fibonacci-luku F j  + 1 .

Lemma todistetaan induktiolla j :llä .

Otetaan nyt kaksi ei-tyhjää joukkoa erilaisia ​​ei-peräkkäisiä Fibonacci-lukuja  S ja T samalla alkioiden summalla. Tarkastellaan joukkoja  S′ ja T′ , jotka ovat yhtä suuria kuin S ja T , joista yhteiset alkiot on poistettu (eli S′ = S  \  T ja T′ = T  \  S ). Koska S :llä ja T :llä on sama alkioiden summa ja niistä on poistettu samat alkiot (eli alkiot S  ∩  T ), myös S′: lla ja T′: lla on oltava sama alkioiden summa.

Osoitetaan ristiriitaisesti , että ainakin yksi joukoista S′ ja T′ on tyhjä. Oletetaan, että näin ei ole, eli että  S′ ja T′ ovat molemmat ei-tyhjiä, ja olkoon S ′: n suurin alkio F s ja T′: n suurin alkio F t . Koska S′ ja T′ eivät sisällä yhteisiä alkioita, F s ≠ F t . Oletetaan yleisyyden menettämättä, että  F s < F t . Tällöin lemman mukaan S' :n alkioiden summa on ehdottomasti pienempi kuin F s  + 1 , eli tiukasti pienempi kuin Ft , koska T ' :n alkioiden summa ei ole pienempi kuin Ft . Ja tämä on ristiriidassa sen tosiasian kanssa, että S′: lla ja T′: lla on sama alkioiden summa. Siksi joko S′ tai T′ on tyhjä.

Olkoon (ilman yleisyyden menetystä) tyhjä S . Tällöin  S′ :n alkioiden summa on nolla, joten T′ :n alkioiden summa on myös nolla, mikä tarkoittaa, että  T′  on myös tyhjä joukko (sisältää vain luonnollisia lukuja). Siten S′ = T′ = ∅ , eli S = T , mikä oli todistettava.

Fibonaccin kertolasku

Käyttämällä Zeckendorf-esitystä voidaan ottaa käyttöön seuraava operaatio. Luonnollisille luvuille a ja b Zeckendorfin esityksillä ja Fibonacci kertolaskulla voidaan määritellä . Lisätietoja Fibonacci kertolaskusta on artikkelissa Fibonacci lukujärjestelmä .

Ei-Gafibonacci-lukujen esitys

Fibonacci-sekvenssiä voidaan laajentaa negatiivisiksi indekseiksi toistuvuusrelaatiolla

joka antaa " negafibonacci "-lukujen sekvenssin, joka täyttää tasa-arvon

Mikä tahansa kokonaisluku voidaan myös esittää yksiselitteisesti [2] ei-Gafibonacci-lukujen summana, jossa ei käytetä kahta peräkkäistä ei-Gafibonacci-lukua. Esimerkiksi:

Huomaa, että 0 = F −1 + F −2 , joten esityksen yksilöllisyys riippuu olennaisesti siitä ehdosta, että kahta peräkkäistä ei-Gafibonacci-lukua ei käytetä.

Tämä antaa  kokonaislukukoodausjärjestelmän , joka on samanlainen kuin Zeckendorf-esitys . Kokonaisluvun  x esityksessä n: s luku on 1, jos sen esityksessä on F n , ja muutoin 0. Esimerkiksi 24 on koodattu merkkijonolla 100101001, jonka kohdat ovat 9., 6., 4. ja 1., koska 24 = F −1 + F −4 + ​​​​F −6 + F −9 . Kokonaislukua  x edustaa pariton sana silloin ja vain, jos x > 0 .

Katso myös

Muistiinpanot

  1. ↑ Historiallinen muistiinpano nimestä Zeckendorf Representation Arkistoitu 25. marraskuuta 2009 Wayback Machinessa , kirjoittanut R. Knott, Surreyn yliopisto.
  2. ↑ Knuth, Donald. {{subst:AI}}

Kirjallisuus

Linkit

Tämä artikkeli käyttää " todistusta siitä, että positiivisen kokonaisluvun Zeckendorf-esitys on ainutlaatuinen " PlanetMathista , joka on lisensoitu Creative Commons Attribution/Share-Alike -lisenssillä .