# Using induction to prove an exponential lower bound for the Fibonacci sequence

The Fibonacci sequence $$F_0, F_1, F_2,...,$$ 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\geq2^{0.5n}$$ for $$n\geq 6$$

So far I have done the basis step plugging in $$6$$ and getting $$8$$ in return. Next I do the inductive step now I have $$F_{k+1}=F_k+F_{k-1}$$ and use the $$F_n\geq2^{0.5n}$$ they gave me I end up with $$2^{\frac{n}{2}}+2^{\frac{n-1}{2}}$$ at which point I get stuck I try and simplify the expression but what I end up with is different from the solutions. Can someone walk me throught this proof and explain how to do it please?

It is almost finished. But for the induction to work, we also need to verify the inequality for $n=7$.

After that, all we need to do is to prove that $$2^{\frac{n}{2}}+2^{\frac{n-1}{2}}\gt 2^{\frac{n+1}{2}}.$$ Equivalently, we want to show that $$1+2^{-1/2} \gt 2^{1/2}.$$ Calculator!

• why is the inequality sign flipped? – notamathwiz Oct 1 '13 at 6:48
• We want to prove that $F_{n+1} \gt 2^{(n+1)/2}$. We know that $F_n\gt 2^{n/2}$ and $F_{n-1}\gt 2^{(n-1)/2}$. So $F_{n+1}\gt 2^{n/2}+2^{(n-1)/2}$. If we can prove that this sum is $\gt 2^{(n+1)/2}$, we will have the result. – André Nicolas Oct 1 '13 at 6:52
• also when i try and verify 7 i dont get the right answer $2^{7/2}$ = 11.31 not 13 as it should – notamathwiz Oct 1 '13 at 6:56
• This is consistent with the desired result. We want to prove that $F_n\gt 2^{n/2}$. And indeed $13=F_7\gt 2^{7/2}\approx 11.3$. – André Nicolas Oct 1 '13 at 6:59
• You are welcome. That's what MSE is about. – André Nicolas Oct 1 '13 at 7:30

Hint: $2^{\frac{n}{2}} + 2^{\frac{n-1}{2}} < 2^{\frac{n}{2}} + 2^{\frac{n}{2}}$.

Induct on n:

Base case, n=6: $$F_6 >= 2^{0.5n}$$ $$13 >= 2^3$$

Inductive assumptions: $$F_n >= 2^{0.5n}$$ $$F_{n-1} >= 2^{0.5(n - 1)}$$ $$n > 6$$

Recursive case: $$F_{n+1} >= 2^{0.5(n + 1)}$$ $$F_n + F_{n - 1} >= 2^{0.5n} \cdot 2^{0.5}$$ $$\text{by the first inductive assumption, }$$ $$\text{and both factors on the right being no less than 1}$$ $$\text{the above is implied by:}$$ $$F_{n - 1} >= 2^{0.5}$$ $$\text{For } n > 6, 2^{0.5(n - 1)} >= 2^{0.5}$$ $$\text{so the above is implied by}$$ $$F_{n - 1} >= 2^{0.5(n - 1)}$$ $$\text{which is the second inductive assumption. QED.}$$