Induction to prove Fibonacci's sequence grows exponentially fast How to solve this using induction?
Use induction to prove that
$F_n\ge2^{\frac n2}\;,\;$ for $n\ge6\;.$
$F_0=0\;,\;F_1=1\;,\;F_n=F_{n-1}+F_{n-2}\;.$
 A: There are three steps to any induction problem.
Step 1, prove your base cases. In this case, first show that $F(n)\geq 2^\frac n2$ when $n=6$ (i.e. $F(6)\geq 2^3=8$). Working out $F(6)$ suffices here. Since the recursive definition is based on two prior cases ($F(n)=F(n-1)+F(n-2)$, there are two terms on the RHS), you also need a second base case, the next one along, here that is $n=7$, so show that $F(7)\geq 2^\frac 72$ (Hint: square this number to find its approximate numerical value)
Step 2, Assume that the property holds true for a given $k,k+1$. That is, assume $F(k)\geq 2^\frac k2, F(k+1)\geq 2^{\frac{k+1}{2}}\tag1$
Step 3: Use this to prove the statement holds for the next case, i.e. that $(1)$ implies that $$F(k+2)=F(k+1)+F(k)\geq 2^{\frac{k+2}{2}}$$
A: $F_6=8\ge2^{\frac62}\;.$
$F_7=13\ge\sqrt{2^7}=2^{\frac72}\;.$
Now, for $\;n\ge8\;,$ we suppose that $\;F_{n-2}\ge2^\frac{n-2}{2},\;F_{n-1}\ge2^\frac{n-1}{2}$ and prove that $\;F_n\ge2^\frac n2.$
$F_n=F_{n-1}+F_{n-2}\ge2^{\frac{n-1}{2}}+2^{\frac{n-2}{2}}=2^{\frac{n-2}{2}}\big(\sqrt 2+1\big)\ge$
$\ge2^{\frac n2-1}\cdot 2=2^{\frac n2}.$
Hence, by induction on $n$, it follows that
$F_n\ge2^\frac n2\quad$ for all $\;n\ge6\;.$
