I'm having a lot of trouble with the following homework question:
Consider the following recursive function:
Base Case: $F(0) = 0,F(1) = 1$.
Recursive Step: $F(n)=F(n−1)+F(n−2)$ for all $n≥2$.
Prove that $F(n)\le \left ( \cfrac{1+ \sqrt5}{2} \right) ^{n-1}$
I have tried to do the induction step by rewriting this as $F(k+1) = F(k) + F(k-1)$ and then subbing in the inequalities for each of $F(k)$ and $F(k-1)$ but I feel that I am hopelessly barking up the wrong tree.
Best Answer
Hint: $\displaystyle \frac{1+\sqrt{5}}{2}+1= \frac{3+\sqrt{5}}{2}=(\frac{1+\sqrt{5}}{2})^2$
The above implies that,
$$\displaystyle F(k+1)=F(k)+F(k-1)\le(\frac{1+\sqrt{5}}{2})^{k-1}+(\frac{1+\sqrt{5}}{2})^{k-2} \text{ (By induction hypothesis)}$$
$$\displaystyle \Rightarrow (\frac{1+\sqrt{5}}{2})^{k-1}+(\frac{1+\sqrt{5}}{2})^{k-2}\le (\frac{1+\sqrt{5}}{2})^{k-2}(\frac{1+\sqrt{5}}{2}+1)\le (\frac{1+\sqrt{5}}{2})^{k-2}(\frac{1+\sqrt{5}}{2})^{2}=(\frac{1+\sqrt{5}}{2})^{k} \text{ (Using Hint)}$$