# Thread: Fibonacci proof

1. ## Fibonacci proof

The numbers F0, F1, F2,... are defined as follows (this is a definition by mathematical induction, by the way): F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn for n = 0,1,2,....... Prove that for any n>=0 we have Fn<=((1 + sqrt5)/2)^(n-1)

Plz give a counting prof instead of induction.

2. Originally Posted by asc
The numbers F0, F1, F2,... are defined as follows (this is a definition by mathematical induction, by the way): F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn for n = 0,1,2,....... Prove that for any n>=0 we have Fn<=((1 + sqrt5)/2)^(n-1)

Plz give a counting prof instead of induction.
Can use fibonacci formula??

3. Originally Posted by asc
The numbers F0, F1, F2,... are defined as follows (this is a definition by mathematical induction, by the way): F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn for n = 0,1,2,....... Prove that for any n>=0 we have Fn<=((1 + sqrt5)/2)^(n-1)

Plz give a counting prof instead of induction.
We want to prove $f_n \leq \left( \frac{1+\sqrt{5}}{2}\right)^{n-1}$ for $n\geq 1$.
Which is true for $n=1$. Suppose it is true for all $k\leq n$. Then $f_{n+1} = f_n+f_{n-1} \leq \left( \frac{1+\sqrt{5}}{2} \right)^{n-1} + \left( \frac{1+\sqrt{5}}{2} \right)^{n-2}= \left( \frac{1+\sqrt{5}}{2} \right)^n$

4. Originally Posted by ThePerfectHacker
We want to prove $f_n \leq \left( \frac{1+\sqrt{5}}{2}\right)^{n-1}$ for $n\geq 1$.
Which is true for $n=1$. Suppose it is true for all $k\leq n$. Then $f_{n+1} = f_n+f_{n-1} \leq \left( \frac{1+\sqrt{5}}{2} \right)^{n-1} + \left( \frac{1+\sqrt{5}}{2} \right)^{n-2}= \left( \frac{1+\sqrt{5}}{2} \right)^n$
The original poster wrote
Plz give a counting prof instead of induction.