prove by induction that $F(n) \leq \left(\frac{1 + \sqrt{5}}{2}\right)^n$

Question

I had the following prove by induction problem in an exam and I didn't do it because I didn't know how to. Could anyone solve it, please?

$F(0) = 0$

$F(1) = 1$

$F(n) = F(n-1) - F(n-2)$

$F(n) \leq (\frac{1+\sqrt{5}}{2})^n$

Thank you

Answer 1

Clearly true for $n=0$ and $n=1$. Assume that $F(n) \leq \left(\dfrac{1+\sqrt5}2\right)^n$ for all $n \leq m$. We then have \begin{align} F(n+1) & = F(n) - F(n-1) \leq \left\vert {F(n)} \right\vert + \left\vert {F(n-1)} \right\vert \leq \left(\dfrac{1+\sqrt5}2\right)^n + \left(\dfrac{1+\sqrt5}2\right)^{n-1}\\ F(n+1) & \leq \left(\dfrac{1+\sqrt5}2\right)^{n-1}\left(\dfrac{1+\sqrt5}2+1\right) = \left(\dfrac{1+\sqrt5}2\right)^{n+1} \end{align} where we used the fact that $\dfrac{3+\sqrt5}2 = \left(\dfrac{1+\sqrt5}2\right)^2$.