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

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?

• Use LaTex please!!! – barak manos Sep 1 '15 at 18:25

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

• where does the $2^.5$ *2 come from? – C1116 Sep 1 '15 at 18:41
• The factor of $\sqrt 2$ is $\;2^{\tfrac{n-1}2}+2^{\tfrac{n-1}2}$. – Bernard Sep 1 '15 at 18:46
• "This answer was flagged as low-quality because of its length and content." – Alex M. Sep 1 '15 at 18:54
• @Alex M: How that? Is it too short? Is it false? – Bernard Sep 1 '15 at 18:58
• As a reviewer I got to review your post as a "low-quality" one. Of course, I voted not to delete it. I was not the one who flagged it. Maybe there is some automatic procedure that the MSE software uses to identify potentially poor answers? A similar thing happend a few months ago with an answer of Bill Dubuque. It was perfectly fine, but I guess that its terseness confused somebody (or some algorithm). Just a note, so that you know and not be surprised if your (perfectly valid) answer gest deleted. – Alex M. Sep 1 '15 at 19:05

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

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