Hallo,
Ik ben bezig met een profielwerkstuk over de fibonacci-reeks en de gulden snede. Ik snap wel hoe je de rij van Fibonacci recursief definieert met de formules: f(n+1) = f(n) + f(n-1) en f(0)=1, f(1)= 1. Nou heb ik ook in een boek gevonden dat je de getallen van de Fibonacci-reeks kunt berekenen met de formule van Binet. Dit is handig want als je dan f(100) uit moet rekenen hoef je niet eerst f(2) t/m f(99) uit te rekenen.
Maar hoe kom je van de formules f(n+1) = f(n) + f(n-1) en f(0)=1, f(1)= 1 op de binet formule? Kan iemand mij hier een bewijs voor geven d.m.v. differentiëren?
Alvast bedankt!
recursieve Fibonacci-formule naar de binet formule
-
juliettejansz
- Nieuw lid
- Berichten: 1
- Lid geworden op: 31 jan 2009, 14:53
Re: recursieve Fibonacci-formule naar de binet formule
Een bewijs vind je op http://library.thinkquest.org/27890/applications2p.html.
Merk op dat ze hier stellen: F(0)=0, F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8, .....
Het was bovendien wat netter indien ze daar de inductieve stap in het algemeen zouden geven:
Stel de formule is waar voor a:
*\varphi + F(a-1))
dan geldt voor (a+1):
*\varphi + F(a-1)\right])
*\varphi^2 + F(a-1)*\varphi)
*(\varphi + 1) + F(a-1)*\varphi)
*\varphi + F(a) + F(a-1)*\varphi)
*\varphi + F(a-1)*\varphi + F(a))
+ F(a-1)\right]*\varphi + F(a))
*\varphi + F(a))
*\varphi + F((a+1)-1))
Dus: als de formule geldt voor a, dan geldt de formule ook voor (a+1), hetgeen we wilden aantonen.
Merk op dat ze hier stellen: F(0)=0, F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8, .....
Het was bovendien wat netter indien ze daar de inductieve stap in het algemeen zouden geven:
Stel de formule is waar voor a:
dan geldt voor (a+1):
Dus: als de formule geldt voor a, dan geldt de formule ook voor (a+1), hetgeen we wilden aantonen.