Fibonacci

Een zoekmethode

Anna en Bert spelen het volgende spel:
Anna neemt een getal kleiner dan 100 in gedachte.
Bert moet nu proberen d.m.v. vragen te achterhalen welk getal Anna in gedachte heeft. Anna hoeft alleen met ja of nee te antwoorden. Hoe kan Bert dat efficiënt aanpakken?

Een bekende manier is de halveringsmethode:
Is het getal kleiner dan 50? {(1 + 99)/2 = 50}


Zo ja, dan ligt het getal tussen 1 en 50. Is het getal kleiner dan 25? {(1 + 49)/2 = 25}

Zo nee, dan ligt het getal tussen 50 en 100. Is het getal kleiner dan 75? {(50 + 99)/2 = 74,5}


Het is een ieder wel duidelijk hoe dit verder gaat.
Vóór elke vraag moet er eerst een gemiddelde worden uitgerekend. Dat is een heel gedoe, vooral als het om wat grotere getallen gaat.
Met Fibonaccigetallen kunnen we een bijna net zo efficiënte methode bedenken. Het voordeel van de methode is dat volstaan kan worden met wat simpele optelsommetjes.
Bert heeft een lijstje met Fibonaccigetallen voor zich liggen en ziet daarop dat F₁₂ = 144 het kleinste Fibonaccigetal is groter dan 100. Dus vraagt hij:
Is het getal kleiner dan 89 (F₁₁)?

Zo ja, is het getal kleiner dan 55 (F10)?

Zo nee, vraag dan aan Anna van haar getal 89 (F11) af te trekken. Is dan het resterende getal kleiner dan 34 (F9)?



De lezer zal zich kunnen voorstellen hoe dit verder gaat.
Je ziet dat Bert geen enkele rekensom hoeft te maken. Voorbeeld: Anna heeft in gedachte het getal 70. Ze overweegt:
Is 70 < 89(F₁₁)? Ja. Is 70 < 55(F₁₀)? Neen. 70 - F₁₀ = 15.
Is 15 < 21(F₈)? Ja. Is 15 < 13(F₇)? Neen. 70 - F₁₀ - F₇ = 2.
Is 2 < 5(F₅)? Ja. Is 2 < 3(F₄)? Ja. Is 2 < 2(F₃)? Neen. 70 - F₁₀ - F₇ - F₃ = 0.
Is 0 < 1(F₁)? Ja.
Blijkbaar is 70 - F₁₀ - F₇ - F₃ = 0, en Bert concludeert dat het getal dat Anna in het begin in gedachte had is F₁₀ + F₇ + F₃.
Bert moet nu nog de 3 Fibonacci bij elkaar tellen voor het antwoord. Met dit algoritme kunnen we dus elk (positief geheel) getal schrijven als som van Fibonaccigetallen.
Vergelijk deze methode maar eens met de halveringsmethode als het gaat om een getal onder het miljoen. Hier de eerste 31 Fibonaccigetallen:
1:1, 2:1, 3:2, 4:3, 5:5, 6:8, 7:13, 8:21, 9:34, 10:55, 11:89, 12:144, 13:233, 14:377, 15:610, 16:987, 17:1597, 18:2584, 19:4181, 20:6765, 21:10946, 22:17711, 23:28657, 24:46368, 25:75025, 26:121393, 27:196418, 28:317811, 29:514229, 30:832040, 31:1346269.
Ik vind 100.000 = F₂₅ + F₂₂ + F₂₀ + F₁₄ + F₁₁ + F₇ + F₆ + F₅ + F₄ + F₃ + F₂ + F₁.

Nog wat feiten:
Elk getal kan geschreven worden als som van verschillende Fibonaccigetallen, waarbij de index van elk tweetal Fibonaccigetallen meer dan 1 verschilt. (Bewijs).
Elk getal kan geschreven worden als som of verschil van verschillende Fibonaccikwadraten.
B.v. 1 = F₁²,   2 = F₁² + F₂² ,   3 = F₃² - F₁²,   4 = F₃²,   5 = F₃² + F₁²,   6 = F₄² - F₃² + F₁², enz.
(Bewijs: Maak gebruik van Enkele algemene formules).