Prove by induction that the Fibonacci sequence $≤ [(1+\sqrt{5})/2]^{n−1}$, for all $n ≥ 0$.

Question

If $F(n)$ is the Fibonacci Sequence, defined in the following way: $$ F(0)=0 \\ F(1)=1 \\ F(n)=F(n-1)+F(n-2) $$

I need to prove the following by induction:
$$F(n) \leq \bigg(\frac{1+\sqrt{5}}{2}\bigg)^{n-1} \quad \forall n \geq 0$$

I know how to prove the base cases and I know that the inductive hypothesis is "assume $F(n) \leq \bigg(\frac{1+\sqrt{5}}{2}\bigg)^{n-1} \quad \forall n \leq k, k \geq 0$".

For the inductive step, I need to show:
$$F(k+1) \leq \bigg(\frac{1+\sqrt{5}}{2}\bigg)^{k+1}$$

$F(k) + F(k-1) \leq \bigg(\frac{1+\sqrt{5}}{2}\bigg)^k$ -- by the definition of the Fibonacci sequence. $\bigg(\frac{1+\sqrt{5}}{2}\bigg)^{k-1} + \bigg(\frac{1+\sqrt{5}}{2}\bigg)^{k-2} \leq \bigg(\frac{1+\sqrt{5}}{2}\bigg)^k$ -- by the inductive hypothesis?

If I could show this last line then I could prove the overall question but I am unsure of how to prove this and that last line may not be correct. Any help would be greatly appreciated!

Answer 1

Hint: Let $\phi = \frac{1 + \sqrt{5}}{2}$. Note that $\phi$ satisfies $$ \phi^2 = \phi + 1 $$ (as you may verify using the quadratic formula, for example) and therefore for all $k$, $\phi^k = \phi^{k-1} + \phi^{k-2}$.

Answer 2

looks like you are most of the way there:

$F(k+1) = F(k)+F(k-1) \leq (\frac{1+\sqrt5}{2})^{k-1}+(\frac{1+\sqrt5}{2})^{k-2}$

$F(k+1) \leq (\frac{1+\sqrt5}{2})^{k-2}(1+\frac{1+\sqrt5}{2})$

You are home if: $1+\frac{1+\sqrt5}{2} \leq (\frac{1+\sqrt5}{2})^2$

Answer 3

$[(1+\sqrt {5})/2]^2=(1 +2*\sqrt {5}+5)/4=(6+2*\sqrt {5})/4=3+\sqrt {5} $

So

$F (k+1)=F (k)+F (k+1)\le [(1+\sqrt {5})/2]^{k-1} +[(1+\sqrt {k-2})/2]^{k-2} $

$=[(1+\sqrt {k-2})/2]^{k-2}([(1+\sqrt {5 })/2]+1)=[(1+\sqrt {5})/2]^{k-2}(3+\sqrt {5})/2$

$=[(1+\sqrt {5})/2]^{k-2}[(1+\sqrt {5})/2]^2=[(1+\sqrt {5})/2]^k $