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

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

• What did you try? Where did you get stuck? By the way, you can produce $\leq$ by typing \leq when you are in math mode. – N. F. Taussig Dec 12 '15 at 14:01
• You can also find a close form, e.g. adapting this answer to your case. – AndreasT Dec 12 '15 at 14:05
• @N.F.Taussig i proved it for n=0 and n=1. Then I tried to prove that $F(n+1) = (\frac{1+\sqrt{5}}{2}+1)^n$ – zeeks Dec 12 '15 at 14:10
• There is probably a mistake in the question. As stated, the sequence is a periodic repetition of (0,1,1,0,-1,-1) – thedude Dec 12 '15 at 14:11

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$.