# Prove by mathematical induction: $n < 2^n$ [duplicate]

Step 1: prove for $n = 1$

1 < 2

Step 2:

$n+1 < 2 \cdot 2^n$

$n < 2 \cdot 2^n - 1$

$n < 2^n + 2^n - 1$

The function $2^n + 2^n - 1$ is surely higher than $2^n - 1$ so if

$n < 2^n$ is true (induction step), $n < 2^n + 2^n - 1$ has to be true as well.

Is this valid argumentation?

## marked as duplicate by GNUSupporter 8964民主女神 地下教會, paf, Namaste, José Carlos Santos, Ethan BolkerMay 13 '18 at 23:52

Yes. Your method works. Alternate: $$n + 1 < 2n < 2 \cdot 2^n = 2^{n+1},$$ as desired.

• You state that n+1<2n. But this isn't true for n=0. What am I missing? – aidandeno Jul 24 '15 at 15:30
• This proves the results for all $n > 0$. – Ahaan S. Rungta Jul 24 '15 at 18:10

$$n+1<n+n<2^n+2^n=2^{n+1}$$

• Beaten by 35 seconds! – Ahaan S. Rungta Oct 21 '13 at 15:57
• @AhaanRungta :-) – bateman Oct 21 '13 at 15:58
• Thank you. I'll give the answer to @AhaanRungta though, because he answered the question. – user45045 Oct 21 '13 at 16:00
• Thanks! Bateman beat me to it, so I'll give him an upvote. :) Also, Grant, you didn't give me the check mark (accepted answer). :P – Ahaan S. Rungta Oct 21 '13 at 16:01
• @Grant: bateman answered the question in the title, which should be arguably more important than anything you ask in the text (unless explictly said otherwise). – Marek Oct 21 '13 at 16:02

We want to show that $k+1 < 2^{k+1}$, from the original equation, replacing $n$ with $k$: $$k + 1 < 2^k + 1$$ Thus, one needs to show that: $$2^k + 1 < 2^{k + 1}$$ to complete the proof.

We know that $1 < 2^k$ for $k ≥ 1$. Adding $2^k$ to both sides: $$2^k + 1 < 2^k + 2^k = 2^{k+1},$$ which shows that $n < 2^n$.