Proving $2^n\leq 2^{n+1}-2^{n-1}-1$ for all $n\geq 1$ by induction

Question

I am trying to prove that for every element of $\mathbb{N}$, that $2^n \leq 2^{n+1} - 2^{n-1} - 1.$ I started by showing that initial case, of $n=1$, is true. Then I proceed to the inductive step by assuming that for some $k$ in $\mathbb{N}$, $2^k \leq 2^{k+1} - 2^{k-1} - 1$. Then, for $n=k+1$, $2^{k+1} \leq 2^{k+2} - 2^{k} - 1$. Is this sufficient to prove the statement by induction or do I have to expand the exponentials to rearrange the inequality in a different way?

Answer 1

Here is the meat of the inductive proof: \begin{align} 2^{k+1} &= 2\cdot 2^{k}\tag{by definition}\\[0.5em] &\leq 2\cdot(2^{k+1}-2^{k-1}-1)\tag{by inductive hypothesis}\\[0.5em] &= 2^{k+2}-2^k-2\tag{expand}\\[0.5em] &\leq 2^{k+2}-2^k-1. \end{align} Does that make sense?

Answer 2

Hint:

$$2^{k+1}=2\cdot 2^k\leq 2(2^{k+1}-2^{k-1}-1)$$

and use the inequality $k\lt k+1~\forall~k\in\Bbb{R}$

Can you continue?

Answer 3

Your proof is not sufficient. You've only proved that it's true for $n=1$ and assumed the claim is true for $n=k$. Those two itself are not enough to automatically say $n=k+1$: you have to use the assumption from $n=k$ to build and prove that the claim is also true for $n=k+1$.