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?
 A: 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$
A: 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$$
A: 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}
A: 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.
A: 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$.
