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?
Best Answer
Assume that:
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$