<s>[INST] proof by induction $2^n \leq 2^{n+1}-2^{n−1}-1$ 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.
 [/INST] 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. 
</s>