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

Question

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?

Answer 1

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}

Answer 2

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$

Answer 3

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

Answer 4

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.

Answer 5

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