# Factoring for Strong Induction for Fibonacci Sequence

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

Break

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}$.
• Oh so there is no way that I can make it look like $\left(\displaystyle\frac{3}{2}\right)^{m-2}$ then huh? – KawaiiExpert Apr 25 '14 at 0:24
• $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}$ – KawaiiExpert Apr 25 '14 at 0:33