Where do I go from here to solve $F_{N}<\phi^N$, with $\phi = \frac{1+\sqrt{5}}{2}$

Question

The problem specified is to prove by induction the formula $$F_{N}<\phi^N,$$ with $$\phi = \frac{1+\sqrt{5}}{2}$$

So far I have proven the base case for N=1. My induction step is $$F_{k+1}<\phi^{k+1}$$

Previously I proved that $$F_{k+1} = F_{k}+F_{k-1}$$ and so I have $$F_{k}+F_{k-1}<\phi^{k+1}$$

However, now I'm lost. I was given the hint to use the formula $$\phi^{2}=\phi +1$$ but I'm not sure what to do with this or how it's even relevant. Can someone at least point me in the right direction here?

Answer 1

If $F_k<\phi^k$ and $F_{k+1}<\phi^{k+1}$, then\begin{align}F_{k+2}&=F_k+F_{k+1}\\&<\phi^k+\phi^{k+1}\\&=\phi^k(1+\phi)\\&=\phi^k\cdot\phi^2\\&=\phi^{k+2}.\end{align}