WisFaq!

Fibonacci rij

Er wordt gevraagd aan te tonen dat er een element in de Fibonacci rij bestaat dat op n nullen eindigt. Waarbij n Î

Ik heb al wel wat dingen uitgeprobeerd maar het lukt me niet om aan te tonen dat het voor elke n geldt.

Zou iemand mij kunnen helpen....

Gegroet Amy

Amy
27-2-2005

Antwoord

Hi Amy,

Laat ik het eens proberen bewijzen voor n=3 (dus zoek een duizendvoud in de Fibonaccirij). In plaats van naar de rij zelf te kijken, ga ik de koppels opeenvolgende getallen in de rij bekijken:
(0,1),(1,1),(1,2),(2,3),(3,5),(5,8),...

Bekijk al die koppels nu eens modulo 1000. Met andere woorden, je neemt van elk getal de rest bij deling door 1000. Hoeveel verschillende koppels zijn er zo mogelijk? Dat zijn er 1000² = 1000000.

Volgens het duivenhokprincipe (of ook principe van Dirichlet genoemd) heb je dan dat er ergens in de eerste 1000001 koppels twee dezelfde zitten. Noem deze koppels (a,b) en (c,d), waarbij je afspreekt dat ac. a en c hebben dus dezelfde rest modulo 1000, en b en d hebben ook dezelfde rest modulo 1000.

Nu, het getal dat voor de a komt in de Fibonaccirij, is b-a. En voor de c staat d-c. Duidelijk zijn b-a en d-c dan ook gelijk modulo 1000. En het getal dat voor b-a staat, is ook gelijk aan het getal dat voor d-c staat (mod 1000)... Op die manier kan je verder werken, tot je helemaal van het getal a naar het getal 0 hebt gewerkt. Tegelijkertijd heb je dan ook van het getal c naar een getal m gewerkt, en dan zie je dat m en 0 gelijk zijn modulo 1000, of dus dat m een duizendvoud is.

Merk op dat dit nu met 1000 is uitgewerkt, maar je kan dat dus ook doen met eender welke macht van 10 (wat je dus wou bewijzen), maar ook voor eender welk natuurlijk getal: in de eerste t² termen van de Fibonaccirij zit dus minstens 1 t-voud en dit voor elk natuurlijk getal t.

Groeten,
Christophe.

Christophe
28-2-2005