# Induction on Fibonacci Sequence and the Golden Ratio

I'm trying to prove $f_n \leq \left(\frac{1 + \sqrt{5}}{2}\right)^{n-1}$ with induction, and I'm stuck in the induction step.

Basis: n = 2

$f_{2} \leq \left(\frac{1 + \sqrt{5}}{2}\right)^{2-1} \Rightarrow f_{2} \leq \left(\frac{1 + \sqrt{5}}{2}\right)^{1} \Rightarrow 1 \leq \approx 1.68$ Base case is true

Ind Hyp.

Prove $n= k$ holds for 2 up to k

Ind Step

Consider $k+1$, let $\varphi = \left(\frac{1 + \sqrt{5}}{2}\right)$

LHS: $f_{k+1}=f_{k} + f_{k-1}$

$f_{k} \leq \varphi^{k-1}$ and $f_{k-1} \leq \varphi^{k-2}$

$f_{k+1} = \frac{\varphi^{k}}{\varphi} + \frac{\varphi}{\varphi^{2}}$

$f_{k+1} = \varphi^{k}\left(\frac{1}{\varphi} + \frac{1}{\varphi^{2}}\right)$

Here is where I'm stuck, I'm not sure if this was the right direction to take, but I believe I need to prove the following to continue:

$f_{k+1}< \varphi^{(k+1)-1}$

Could some one shed some light on my problem or show me a direction I can take?

From $f_k\le\varphi^{k-1}$ and $f_{k-1}\le\varphi^{k-2}$ you get $f_{k+1}\le\varphi^{k-1}+\varphi^{k-2}$, not $f_{k+1}=\varphi^{k-1}+\varphi^{k-2}$. Then
$$f_{k+1}\le\varphi^{k-1}+\varphi^{k-2}=\varphi^k\left(\frac1\varphi+\frac1{\varphi^2}\right)=\varphi^k\left(\frac{\varphi+1}{\varphi^2}\right)\;,$$
and you’re done as soon as you show that $\varphi+1=\varphi^2$. You can do this either by direct computation or by using the fact that $\varphi$ is a solution of the quadratic $x^2-x-1=0$.