proof by induction $2^n \leq 2^{n+1}-2^{n−1}-1$

Question

My question is prove by induction for all $n\in\mathbb{N}$, $2^n \leq 2 ^{n+1}-2^{n−1}-1$

My proof

$1+2+3+4+....+2^n \leq 2^{n+1}-2^{n−1}-1$

Assume $n=1$,$1 ≤ 2$

Induction step

Assume statement is true for $n=k$, show true for $n=k + 1$

$1+2+3+4+....+2^k+2^k+1 ≤ 2 ^{k+1} ​​ −2^{k−1} ​​ - 1$

$2^{k+1} - 2^{k-1} -1 + 2^{k+1} ≤ 2^{k+1} - 2^{k-1} -1$

$4^{k+1} -2^{k-1} -1 ≤ 2^{k+1} - 2^{k-1} -1$

I do not know how to proceed from here, and i am confused because it seems to me this is not true.

Answer 1

In the case that $n=1$ we have $$2 \leq 2^2 - 2^0 - 1 \iff 2 \leq 2$$ which is true. Now, assuming that $$2^k \leq 2^{k+1} - 2^{k-1} - 1$$ holds. We proceed by multiplying our inductive hypothesis above by $2$ to get $$2 \cdot 2^{k} \leq 2(2^{k+1} - 2^{k-1} - 1)$$ Which simplifies to $$2^{k+1} \leq 2^{k+2} - 2^{k} - 2 \leq 2^{k+2} - 2^{k} - 1$$

So we get by transitivity that $$2^{k+1} \leq 2^{k+1 + 1} - 2^{k + 1 -1} - 1$$

So your statement is true by the principle of Mathematical Induction.

Answer 2

since $$ 2^{n+1} = 2^n + 2^n $$ and $$ 2^n - 2^{n-1} = 2^{n-1} $$ your statement, simplified, requires that: $$ 2^{n-1} \ge 1 $$ clearly this is true for $n=1$...

Answer 3

Alternatively, we could prove it directly without induction: \begin{align*} 2^{n + 1} - 2^{n - 1} - 1 &= (2^n + 2^n) - 2^{n - 1} - 1 \\ &= 2^n + (2^{n - 1} + 2^{n - 1}) - 2^{n - 1} - 1 \\ &= 2^n + 2^{n - 1} - 1 \\ &\geq 2^n + 2^{1 - 1} - 1 &\text{since } n \in \mathbb N \implies n \geq 1 \\ &= 2^n \end{align*} as desired. $~~\blacksquare$