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$
 A: It’s a proof by induction.
BASE CASE
Prove for n = 3
2(3) < 2^6 - 1
6 < 7
INDUCTIVE STEP
Assume:$2n < 2^n - 1$
Prove for n = n + 1
2(n + 1) = 2n + 2

here apply inductive hypotesis 
         < (2^(n) - 1) + 2

         = 2^(n) + 1

         < 2^(n) + 2^(n) - 1

         = 2^(n + 1) - 1

A: You need to prove that if it is true for $n$, then it is true for $n+1$.
Indeed, multiplying by $2$ and adding $1$,
$$2n<2^n-1\implies4n+1<2^{n+1}-1,$$ and as $2(n+1)<4n+1$,
$$2n<2^n-1\implies 2(n+1)<2^{n+1}-1.$$

As the property is true for $n=3$ (because $6<7$), it must be true for $n=4,n=5,n=6,\cdots$
I made the proof in a different order than in your post, but the principles are the same.
A: 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$$
A: The third step is just$$(2^n-1)+2=2^n+1.$$This is so because $-1+2=1$. Is this what was causing trouble?
A: This type of proof is called mathematical induction where you test the inequality for $n= 3$ and assume that it is true for some $n$ and then use the assertion to prove for $n+1$. and hence go on to prove the claim.
What you are seeing is the induction proof where the author uses the inequality of $n$ to prove for $n+1$
A: This is a simple induction.
For the start we set n=3. We see, that $2\cdot 3<2^3-1$, since $6<7$.
Our assumtion is not, that for arbitrary $n\in\mathbb{N}$ holds the inequality $2n<2^n-1$.
For the inductive step, we have to conclude, that when the assumtion holds, it has to hold for $n+1$. 
$n\mapsto n+1$
$2(n+1)=2n+2\stackrel{assumption}{<} 2^n+2$ [From the assumtion we know, that $2n<2^n$].
Since $n\geq 3$ it is $2<2^n-1$. This is obvious. So we stipulate further:
$2^n+2<2^n+2^n-1=2\cdot 2^{n}-1=2^{n+1}-1$
QED
A: 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}$. 

