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?

  • 2
    $\begingroup$ $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. $\endgroup$ – rogerl Jun 29 '15 at 15:03

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.