WisFaq!

Beslissingsregel voor Fibonaccirij

Door het lezen van "Gödel, Escher, Bach" van Douglas Hofstadter, waarin de Fibonaccirij en de niet-Fibonaccirij als elkaar uitsluitende voor- en achtergrond werden behandeld, kwam ik op de vraag of er een beslissingsregel is waarmee je van een willekeurig getal kunt bepalen of het in de Fibonaccirij voorkomt of niet, zonder die rij eerst op te bouwen.

Omdat ik zelf neerlandicus ben, heb ik de vraag in enkele decennia aan de nodige exacte collega's voorgelegd maar ben niet wijzer geworden.

Als die regel niet bestaat of niet kan bestaan, zou het ook aardig zijn om te weten waarom.

Ton Wolf
21-3-2007

Antwoord

Volgens Wikipedia:

Van een niet-negatief getal is door een test, geformuleerd door Ira Gessel in 1972, eenvoudig te controleren of een getal in de rij van Fibonacci voorkomt: Het getal n komt voor in de rij van Fibonacci dan en slechts dan als 5n²+4 of 5n²-4 een kwadraat is.

Je zou ook kunnen zeggen dat dit een gevolg is van formule (37) van Chandra, Pravin and Weisstein, Eric W. "Fibonacci Number." From MathWorld--A Wolfram Web Resource.

Zie Wikipedia - Rij van Fibonacci [http://nl.wikipedia.org/wiki/Rij_van_Fibonacci]

WvR
21-3-2007