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 $\displaystyle f_n \leq \left( \frac{1+\sqrt{5}}{2}\right)^{n-1}$ for $\displaystyle n\geq 1$.
Which is true for $\displaystyle n=1$. Suppose it is true for all $\displaystyle k\leq n$. Then $\displaystyle 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 $\displaystyle f_n \leq \left( \frac{1+\sqrt{5}}{2}\right)^{n-1}$ for $\displaystyle n\geq 1$.
Which is true for $\displaystyle n=1$. Suppose it is true for all $\displaystyle k\leq n$. Then $\displaystyle 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.