Fibonacci: prove the following theorem: define the Fibonacci sequence $\left\{ a_n\right\}_{n=0}^{\infty}$ by $a_0=a_1=1$ and for integers $k>1$, $a_k=a_{k-1}+a_{k-2}$. Then, for each integer $n$, $a_n\geq \left(\displaystyle\frac{3}{2}\right)^{n-2}$

Alright here is what I have so far.

(Basis Step)

$a_0 = 1 \geq 4/9 $

$a_1 = 1 \geq 2/3 $

(Inductive Hypothesis)

Fix $m\geq2$ and assume $a_n\geq \left(\displaystyle\frac{3}{2}\right)^{n-2}$ for all n greater than m.

Based on this definition $a_m=a_{m-1}+a_{m-2}$, we than have $a_{m-1} \geq \left(\displaystyle\frac{3}{2}\right)^{m-1-2}$ and $a_{m-2} \geq \left(\displaystyle\frac{3}{2}\right)^{m-2-2}$.

$a_m=a_{m-1}+a_{m-2} \geq \left(\displaystyle\frac{3}{2}\right)^{m-1-2} + \left(\displaystyle\frac{3}{2}\right)^{m-2-2}$.


Alright that is what I have so far. I know that I have to use some algebraic manipulation to $\left(\displaystyle\frac{3}{2}\right)^{m-1-2} + \left(\displaystyle\frac{3}{2}\right)^{m-2-2}$ so that it looks like $\left(\displaystyle\frac{3}{2}\right)^{m-2}$.

However, I don't know how. My professor told me to factor out a $\left(\displaystyle\frac{3}{2}\right)^{m-2-2}$, but I don't know how it would look like.


This factors as $\left( \frac{3}2 \right)^{m-4} \left( 1+\frac{3}2 \right) = \left( \frac{3}2 \right)^{m-4} \left( \frac{5}2 \right) > \left( \frac{3}2 \right)^{m-2}$.

  • $\begingroup$ Oh so there is no way that I can make it look like $\left(\displaystyle\frac{3}{2}\right)^{m-2}$ then huh? $\endgroup$ – KawaiiExpert Apr 25 '14 at 0:24
  • $\begingroup$ See edit please. $\endgroup$ – Sandeep Silwal Apr 25 '14 at 0:25
  • $\begingroup$ $a_m=a_{m-1}+a_{m-2} \geq \left(\displaystyle\frac{3}{2}\right)^{m-1-2}$ + $\left(\displaystyle\frac{3}{2}\right)^{m-2-2} = \left(\displaystyle\frac{3}{2}\right)^{m-4}(1+(3/2))$=$\left(\displaystyle\frac{3}{2}\right)^{m-4}*(5/2) > \left(\displaystyle\frac{3}{2}\right)^{m-2}$ $\endgroup$ – KawaiiExpert Apr 25 '14 at 0:33

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.