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

  • 1
    $\begingroup$ 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. $\endgroup$ – N. F. Taussig Dec 12 '15 at 14:01
  • $\begingroup$ You can also find a close form, e.g. adapting this answer to your case. $\endgroup$ – AndreasT Dec 12 '15 at 14:05
  • $\begingroup$ @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$ $\endgroup$ – zeeks Dec 12 '15 at 14:10
  • $\begingroup$ There is probably a mistake in the question. As stated, the sequence is a periodic repetition of (0,1,1,0,-1,-1) $\endgroup$ – 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$.

  • $\begingroup$ If the original question is stated correctly, then the sequence is periodic and there is no need for any of this. $\endgroup$ – thedude Dec 12 '15 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.