<s>[INST] Can someone explain this proof to me for $2n < 2^n - 1? \,\, n >= 3$ Prove $2n < 2^n - 1;n \geq 3$
Prove for $n = 3$
$2\cdot 3 < 2^6 - 1$
$6 < 7$
Prove for $n \mapsto n + 1$
 $$2(n + 1) = 2n + 2$$
   $$< 2^n - 1) + 2$$
 $$= 2^n + 1$$ 
$$< 2^n + 2^n - 1$$
 $$ = 2^{n + 1} - 1$$
Can someone explain this proof to me? I get lost on the third step: $2^n + 1$ and I don't understand how this shows that $2n < 2^n − 1$
 [/INST] Your inductive hypothesis is that $2n < 2^n - 1$.
If the inductive hypothesis holds, then by adding 2 to both sides, you find that $$(2n) + 2 <  (2^n - 1) + 2$$
On the left hand side, $2n + 2$ is equal to $2(n+1)$.
On the right hand side, $(2^n -1) + 2  = 2^n + 2 - 1 < 2^{n} + 2^{n} - 1 = 2^{n+1} - 1$.
And putting them together proves what you wanted to show:
$$2(n+1) < 2^{n+1} - 1$$
</s>