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?

Solution 1:

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

Solution 2:

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