How can it be proved by induction that the Fibonaaci series is always:
Fn <= ( (1 +sqrt 5)/2 )^(n−1).
F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn, for n = 0, 1, 2, . . .
golden ratio= http://upload.wikimedia.org/math/7/f...ab1e8044aa.png
Printable View
How can it be proved by induction that the Fibonaaci series is always:
Fn <= ( (1 +sqrt 5)/2 )^(n−1).
F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn, for n = 0, 1, 2, . . .
golden ratio= http://upload.wikimedia.org/math/7/f...ab1e8044aa.png
I don't know if you can just use the well-known formula for the nth term of the Fibonacci sequence, but if not you can find a derivation here as well as some other identities.
Start by showing that $\displaystyle F_n \leq \phi ^{n-1}$ for n = 0 and n = 1.Quote:
Originally Posted by DeRSeD
Then assume $\displaystyle F_n \leq \phi ^{n-1}$ for all $\displaystyle n \leq k$, where $\displaystyle k > 1$. If so, then
$\displaystyle F_{k+2} = F_{k} + F_{k+1} \leq \phi ^{k-1} + \phi ^k$
If you can show $\displaystyle \phi ^{k-1} + \phi ^k \leq \phi ^{k+1}$ then you will be done. You might want to start by looking at the case k=1.
