# Prove by induction that for the Fibonacci numbers $F(n)$ with $n \ge 6$, $F(n) \ge 2^{n/2}$

Prove by induction that $F(n) \ge 2^{n/2}$ for $n \ge 6$

I've done the following steps: 1) Base case: $F(6) = 8$, $2^{0.5 \cdot 6} = 8$, base case proved.

2) Induction: let's assume that $F(k) \ge 2^{0.5k}$ is true.

Now we need to prove that $F(k+1) \ge 2^{0.5(k+1)}$ is true either. Any ideas?

• $F(k+1) = F(k) + F(k-1)$, and after you show that $n=7$ works, you can use induction to give inequalities for each term on the RHS. – rogerl Jun 29 '15 at 15:03

## 2 Answers

Since Fibonacci numbers are difined by a second order recurrence equation, you should start with two base cases: $$F(7)=13>\sqrt{2^7}$$

Now, for $n\ge 8$, $$F(n+2)=F(n+1)+F(n)\ge\sqrt{2^n}+\sqrt{2^{n+1}}=\sqrt{2^n}(1+\sqrt 2)>2\sqrt{2^{n}}$$

Consider the more general problem: For which $a,b>0$ do we have $F(n) \ge ab^n$ ?

The natural induction argument goes as follows: $$F(n+1) = F(n)+F(n-1) \ge ab^n + ab^{n-1} = ab^{n-1}(b+1)$$ This argument will work iff $b+1 \ge b^2$ (and this happens exactly when $b \le \phi$).

So, in your case, you only have to check that $b+1 \ge b^2$ for $b=\sqrt 2$, which follows from $\sqrt 2 \ge 1$.

This only takes care of the induction step. You still need the base cases, $n=N$ and $n=N+1$; different $a,b$ will probably need different $N$.