Use induction to prove that $F_n \ge \sqrt 2 ^n$ for $n \ge 6$

Question

The Fibonacci sequence $F_0, F_1, F_2,\dots$ is defined by the rule $F_0=0, \ F_1=1, \ F_n = F_{n−1} + F_{n−2}$.

Use induction to prove that $F_n \ge \sqrt 2 ^n$ for $n \ge 6$.

So for the base case:

$F_6 = 8 \ge 2^{\frac 6 2} = 8$

$F_7 = 13 \ge 2^{\frac 7 2} = 11.31$

By definition: $F_{n+1} = F_n + F_{n-1} \ge \sqrt 2 ^n + \sqrt 2 ^{n-1}$.

This is as far as I could get and I'm not sure where to go from here. Any ideas?

Answer 1

$$2^{\tfrac n2}+2^{\tfrac{n-1}2}=(2^{\tfrac12}+1)2^{\tfrac{n-1}2}>2\cdot2^{\tfrac{n-1}2}=2^{\tfrac{n+1}2}.$$

Answer 2

This is one possible way to finish: $$2^{.5n} + 2^{.5(n-1)} = 2^{.5n}(1 + 2^{-.5}) \\ \geq 2^{.5n}\cdot 1.5 \geq 2^{.5n}\cdot 2^{.5} = 2^{.5(n+1)}$$ where the inequalities come from $1+\sqrt{1/2} \geq 1.5 \geq \sqrt2$.

Answer 3

Apart from the algebraic manipulations that lead to the desired conclusion, which you already have received a couple of answers about, I recommend you to be a bit careful with the wording of induction type proofs like this.

It's very good that you explicitly wrote down the base cases needed for the proof. However, the line "By definition, $F_{n+1}=F_n + F_{n-1} \geqslant 2^{\frac n 2}+2^\frac{n-1}2$" is a bit careless.

A better way to formulate this is to be very explicit with the inductive step and how the induction hypothesis comes into the picture. You need to show that you understand the principle of induction. Example,

Induction hypothesis: Assume that $F_k \geqslant 2^{\frac k 2}$ holds for all $k \geqslant 6$.

Now, we need to prove that $F_{k+1} \geqslant 2^{\frac {k+1}2}$ under the above assumption. And indeed, $F_{k+1} = F_k + F_{k-1}\underbrace{\geqslant 2^{\frac k 2}+2^{\frac {k-1} 2}}_{\text{induction hypothesis}} = \ldots \geqslant 2^\frac{k+1}2$

(The $\ldots$ above corresponds to what the other answers have handled.)

Also note that this proof uses strong induction, since you assume that the hypothesis holds for all values up to $k$ rather than just a single arbitrary $k$.