Laten we eerst het aantal mogelijkheden(p) bekijken per aantal stenen (n):
n p
1 1
2 2
3 3
4 5
5 8
Merk op: In de rij van het aantal mogelijkheden wordt elk getal bepaald door de 2 vorige in de rij
p(n) = p(n-1) + p(n-2)
Dit is geen toeval want:
Stel dat de steen aan het begin van de muur rechtstaat, dan passen daarachter alle mogelijkheden die ontstaan met 1 steen minder !
Stel dat de steen aan het begin van de muur neerligt, dan moet er 1 opgeplaatst worden en passen daarachter alle mogelijkheden die ontstaan met 2 stenen minder !
We kunnen nu de tabel verder aanvullen tot 24 stenen of we kunnen er een formule voor afleiden !
Beschouw de vergelijking: x²-x-1=0
Vermenigvuldigen we beide leden met x dan krijgen we:
x³-x²-x=0
We kunnen dit herhalen en er volgt algemeen:
x^n- x^(n-1)-x^(n-2) = 0
Dit doet denken aan de rij, want ook hier is x^n gelijk aan de som van de 2 vorige getallen in de 'rij', namelijk x^(n-1) en x^(n-2) !
We lossen x² - x - 1 = 0 op; de oplossingen zijn:
x1 = (5^(1/2) + 1)/2 = 1,618033989
x2 = (5^(1/2) - 1 )/2 = -0,618033989
Dit zijn beide kommagetallen en moeten nog dus verder bewerkt worden om hiermee het aantal mogelijkheden te vinden.
Stel: p(2) = a*x1² + b*x2² en
p(1) = a*x1 + b*x2 met a en b nader te bepalen constanten.
Dan is p(3) = a*x1³ + b*x2³ want uit de vergelijking volgt:
a*x1³ + b*x2³ = a*(x1²+x1) + b*(x2²+x2) = a*x1²+ a*x1 +b*x2² +b*x2
We kunnen zo verder gaan en we kunnen stellen:
p(n) = a*x1^n + b*x2^n
Dit is de functie de we zochten !
We gaan dus p(1) en p(2) ingeven om a en b te ontdekken.
Uit de tabel volgt: p(1) = 1 en p(2) = 2
Dan krijgen we:
2 = a*(1,618033989)² + b*(-0,618033989)²
1 = a*1,618033989 + b*(-0,618033989) <=>
a=(1-b*(-0,618033989))/1,618033989
Dit invullen in vergelijking 1 geeft:
2 = ((1-b*(-0,618033989))/1,618033989)* 2,618033989 + b*0,381966011 <=>
b= 0,2763932024= (5^(1/2)-3)/(-5+5^(1/2))
Dan a = 0.7236067977 = (3+5^(1/2))/(5+5^(1/2))
Dit kunnen we nagaan door met wortels te werken ipv met kommagetallen.
Onze formule wordt dan:
p(n)=0.7236067977 *(1,618033989)^n+0,2763932024*(-0,618033989)^n of
p(n) = (3+5^(1/2))/(5+5^(1/2))*(1/2*5^(1/2)+1/2)^n+(5^(1/2)-3)/(-5+5^(1/2))*(-1/2*5^(1/2)+1/2)^n
Met n = 24 krijgen we 75025 mogelijkheden
