Proof by induction for a recursive function $F(n) = F(n–1)+F(n–2)$

Question

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.

Answer 1

Hint: The quantity $\dfrac{1+\sqrt5}2$ is one of the zeroes of $p(x) = x^2-x-1$. What does this mean for the sum of the two estimates?

Answer 2

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)}$$

Answer 3

Viewed conceptually, the proof becomes completely obvious. Let $\rm\,w = (1\!+\!\sqrt{5})/2.\:$ Notice that both $\rm\,F(n)\,$ and $\rm\:G(n) = w^{n-1}$ are solutions of the recurrrence $\rm\,f(n) = f(n\!-\!1) + f(n\!-\!2)\:$ since $\rm\: w^{n-1}\!+w^{n-2}\! = w^{n-2}(w\!+\!1) = w^n\,$ by $\rm\:w^2\! = w+1.\:$ We need to prove $\rm\:G(n)\ge F(n),\:$ i.e. $\rm\: H(n) = G(n)-F(n)\ge 0.\:$ $\rm\,H(n)\,$ also satisfies the recurrence, so an obvious induction proof shows: $ $ if $\rm\:H\:$ starts $\ge 0,\,$ i.e. $\rm\:H(0),H(1)\ge 0,\:$ then $\rm\,H\,$ stays $\rm\:\ge 0,\:$ i.e. $\rm\:H(n)\ge 0\:$ for all $\rm\:n\ge 0,\,$

since $\rm\ \ H(n\!-\!2),\ H(n\!-\!1)\ge 0\ \ \Rightarrow\ \ H(n) = H(n\!-\!2)+H(n\!-\!1) \ge 0 $

The inductive proof works because the recursion relation is an increasing function of the prior values. So any solution whose initial values are $\ge 0$ is increasing for $\rm\,n\ge 2,\:$ so $\rm\:f(n)\ge f(1)\ge 0.$