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
Asked
Active
Viewed 112 times
0
-
1What 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
1 Answers
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$.
Adhvaitha
- 20,259
-
If the original question is stated correctly, then the sequence is periodic and there is no need for any of this. – thedude Dec 12 '15 at 15:15