# Proof by induction: $n$th Fibonacci number is at most $2^n$

I'm trying to find the proof by induction of the following claim: For all $n\in\mathbb N$, $\operatorname{fibonacci}(n) \le 2^n$

My Proof:

### Base case: $n = 1$

$\operatorname{fibonacci}(1) \le 2^ 1$ is $1 \le 2$, true.

Base case holds

### Inductive Hypothesis:

Assume true for $n = k$: $\operatorname{fibonacci}(k) \le 2^k$

Show True for $\operatorname{fibonacci}(k+1) \le 2^{k+1}$

$$\operatorname{fibonacci}(k) * k \le 2^k k$$ $$\operatorname{fibonacci}(k) \le 2^{k+1}$$ I get stuck here

Any help?

• Try using strong induction, i.e. assume $F_k \le 2^k$ for all $k \le n$ and then prove that $F_{n+1} = F_n + F_{n-1} \le 2^{n+1}$. – JimmyK4542 Aug 12 '14 at 5:13
• is it possible through simple induction, because we have not been introduced to "strong induction" ? @JimmyK4542 – user3343972 Aug 12 '14 at 5:16
• Actually, if you know that all fibbonacci numbers are increasing, you can say $F_{n+1} = F_n + F_{n-1} \le F_n + F_n = 2F_n$. – JimmyK4542 Aug 12 '14 at 5:18
• for instance, f(n) = f(n-1) + f(n -2), can I sub in k+1 for n and get to f(k) + f(k-1)? @JimmyK4542 – user3343972 Aug 12 '14 at 5:20
• @user36829 How is this a duplicate? That's a different problem. – user147263 Aug 12 '14 at 5:24

Assume that:

All Fibonacci numbers are positive. $(\star)$

Then observe that: \begin{align*} \text{fibonacci}(k + 1) &= \text{fibonacci}(k) + \text{fibonacci}(k - 1) \\ &< \text{fibonacci}(k) + \text{fibonacci}(k - 1) + \text{fibonacci}(k - 2) &\text{by }(\star)\\ &= \text{fibonacci}(k) + \text{fibonacci}(k) \\ &= 2 \cdot \text{fibonacci}(k) \\ &\leq 2 \cdot 2^{k} &\text{by the ind. hypothesis} \\ &= 2^{k + 1} \end{align*} as desired. $~~\blacksquare$

• This proof silently assumes that k >= 2. But the other cases can be done by hand. – Blaisorblade Jan 19 at 12:39

It is clear in the base case that $F_1\le 2^1$ and $F_2\le 2^2$. Then in the inductive step we see that \begin{align} F_n &= F_{n-1}+F_{n-2}\\ &\le 2^{n-1} + 2^{n-2}\\ &= 2^{n-2}(2 + 1)\\ &\le 2^{n-2}(4)\\ &=2^n. \end{align}

• Don't we need P(k+1) -> 2^k+1 at the end of the proof? @fahrbach – user3343972 Aug 12 '14 at 14:20
• Not really, but we need some sort of advancement with the indices. We could have written $F_{n+1} = F_{n} + F_{n-1}$ instead, but the idea is the same. Notice in this answer that we prove the hypothesis for $F_3$, then $F_4$, etc. – fahrbach Aug 12 '14 at 15:51

For the first term, we have $$F_1=1<2^1$$ Now assume the statement is true for $F_n$, the $nth$ Fibonacci term i.e. $$F_n\le2^n$$ Then, we have for $F_{n+1}$ $$F_{n+1}=F_n+F_{n-1}$$ Since this is a strictly increasing sequence, we know that $$F_n>F_{n-1}$$ and since $$2F_n=F_n+F_n$$ we also have that $$2F_n>F_n+F_{n-1}$$ We already know (by assumption) that $$F_n\le2^n$$ $$\Rightarrow 2F_n\le2^{n+1}$$ Combining these inequalities, we have $$2^{n+1}\ge2F_n>F_{n+1}$$ $$\Rightarrow2^{n+1}\ge F_{n+1}$$ $$\Rightarrow F_n\le2^n$$

For $n = 1$, see that it holds: $1 = F_1 < 2^1$.

Assume that $F_k < 2^k$. Since $F_{k+1} = F_k + F_{k - 1} < 2^k + 2^{k - 1} < 2^{k + 1}$, as desired.

Consider the more general problem: For which $a,b>0$ do we have $F(n) \le ab^n$ ?

The natural induction argument goes as follows: $$F(n+1) = F(n)+F(n-1) \le ab^n + ab^{n-1} = ab^{n-1}(b+1)$$ This argument will work iff $b+1 \le b^2$ (and this happens exactly when $b \ge \phi$).

So, in your case, you can take $a=1$ and you only have to check that $b+1 \le b^2$ for $b=2$, which is immediate.

This only takes care of the induction step. You still need the base cases, $n=0$ and $n=1$, and so we need $a\ge0$ and $ab\ge1$.