# Thread: Why is Fibonacci =< golden ration^n-1

1. ## Why is Fibonacci =< golden ration^n-1

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=

2. 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.

3. Originally Posted by DeRSeD
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=
Start by showing that $\displaystyle F_n \leq \phi ^{n-1}$ for n = 0 and n = 1.

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.