Solution for Hw 1, Prob 3 by Brian Kirklin
We use induction to prove $F_n \geq 2^{0.5n}$ for $n \geq 6$.
BASE CASE: (n = 6)\\ We see $F_6 = 8$ and $2^{0.5 * 6} = 2^3 = 8$. So $F_6 = 2^{0.5n}$.
INDUCTIVE STEP: Assume for $n \geq 6$ that $F_n \geq 2^{0.5n}$. We show\[F_{n+1} \geq 2^{0.5(n+1)},\]
for $n \geq 6$.
So we know $F_n \geq 2^{\frac{n}{2}}$. Then we also know
\[\sqrt{2}F_n \geq 2^{\frac{n + 1}{2}}.\]
By definition $F_{n-2} + F_{n - 1} = F_n$ and $F_{n-1} > F_{n-2}$ for $n \geq 6$. Hence $F_{n-1} > \frac{1}{2}F_n$. Now we know
\[2F_{n-1} > F_n\]
\[2F_{n-1} + 2F_n > 3F_n\]
\[2F_{n+1} > 3F_n\]
\[F_{n+1} > \frac{3}{2}F_n\]
NOTE: $\frac{3}{2} > \sqrt{2}$
\[F_{n+1} > \sqrt{2}F_n\]
Hence, \[F_{n+1} \geq 2^{\frac{n+1}{2}}\] as desired.
Link to this Page
