<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] The inductive step: assuming that $2n < 2^n - 1$, show that $2(n+1) < 2^{n+1} - 1$.


*

*$2(n+1) = 2n + 2\qquad$distribution

*$2n + 2 < (2^n -1) + 2\qquad$ by the inductive hypothesis that $2n < 2^n -1$. (Just add two to both sides of inductive hypothesis to see that this is true.)

*$(2^n -1) + 2 = 2^n -1 + 2 = 2^n + 1\qquad$ Remove parentheses

*$2^n + 1 < 2^n + 2^n + 1\qquad$ Adding $2^n$ makes it larger.

*$2^n + 2^n + 1 = 2^{n+1} + 1\qquad$ Because $2^n + 2^n = 2(2^n) = 2^{n+1}$. 

</s>