0
$\begingroup$

If $F(n)$ is the Fibonacci Sequence, defined in the following way: $$ F(0)=0 \\ F(1)=1 \\ F(n)=F(n-1)+F(n-2) $$

I need to prove the following by induction:
$$F(n) \leq \bigg(\frac{1+\sqrt{5}}{2}\bigg)^{n-1} \quad \forall n \geq 0$$

I know how to prove the base cases and I know that the inductive hypothesis is "assume $F(n) \leq \bigg(\frac{1+\sqrt{5}}{2}\bigg)^{n-1} \quad \forall n \leq k, k \geq 0$".

For the inductive step, I need to show:
$$F(k+1) \leq \bigg(\frac{1+\sqrt{5}}{2}\bigg)^{k+1}$$

$F(k) + F(k-1) \leq \bigg(\frac{1+\sqrt{5}}{2}\bigg)^k$ -- by the definition of the Fibonacci sequence. $\bigg(\frac{1+\sqrt{5}}{2}\bigg)^{k-1} + \bigg(\frac{1+\sqrt{5}}{2}\bigg)^{k-2} \leq \bigg(\frac{1+\sqrt{5}}{2}\bigg)^k$ -- by the inductive hypothesis?

If I could show this last line then I could prove the overall question but I am unsure of how to prove this and that last line may not be correct. Any help would be greatly appreciated!

$\endgroup$
3
$\begingroup$

Hint: Let $\phi = \frac{1 + \sqrt{5}}{2}$. Note that $\phi$ satisfies $$ \phi^2 = \phi + 1 $$ (as you may verify using the quadratic formula, for example) and therefore for all $k$, $\phi^k = \phi^{k-1} + \phi^{k-2}$.

$\endgroup$
1
$\begingroup$

looks like you are most of the way there:

$F(k+1) = F(k)+F(k-1) \leq (\frac{1+\sqrt5}{2})^{k-1}+(\frac{1+\sqrt5}{2})^{k-2}$

$F(k+1) \leq (\frac{1+\sqrt5}{2})^{k-2}(1+\frac{1+\sqrt5}{2})$

You are home if: $1+\frac{1+\sqrt5}{2} \leq (\frac{1+\sqrt5}{2})^2$

$\endgroup$
0
$\begingroup$

$[(1+\sqrt {5})/2]^2=(1 +2*\sqrt {5}+5)/4=(6+2*\sqrt {5})/4=3+\sqrt {5} $

So

$F (k+1)=F (k)+F (k+1)\le [(1+\sqrt {5})/2]^{k-1} +[(1+\sqrt {k-2})/2]^{k-2} $

$=[(1+\sqrt {k-2})/2]^{k-2}([(1+\sqrt {5 })/2]+1)=[(1+\sqrt {5})/2]^{k-2}(3+\sqrt {5})/2$

$=[(1+\sqrt {5})/2]^{k-2}[(1+\sqrt {5})/2]^2=[(1+\sqrt {5})/2]^k $

$\endgroup$

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.