# Proving $n \lt 2^n$ for $n\geq 1$ using induction

Very close to understanding this, hopefully. Via induction, I'm following a proof but can't understand one of the last steps.

Claim: $n < 2^n$ for natural numbers $n = 1, 2, 3,\ldots$

For step one, $n = 1$, this is obviously true:

$$1 < 2^1 = 1 < 2.$$

Next, assuming $n = k$, is true:

$$k < 2^k.$$

Next I must show that $k + 1 < 2^{k + 1}$ is true, to prove that all natural numbers are true. I begin with this:

$$k < 2^k\\ k + 1 < 2^k + 1$$

Since this is true, adding one more to the RHS is also going to be true:

$$k + 1 < 2^k + 2.$$

Here's where I don't get it. The proof I'm reading claims it's obvious that

$$2^k + 2 \leq 2^{k+1}.$$

Ok yeah, it seems like this is true, but are we certain? Substituting $k = 1$ and $k = 2$ does the trick, and it does seems reasonably intuitive that this would go on forever, but how is this a "formal" result?

From there the proof is completed by putting everything side by side, showing that $k + 1$ is less than all those intermediate steps, resulting in it also being less than $2^{k + 1}$, which makes sense, had I understood that last step!

Yes there are a number of questions similar to this one - couldn't quite find one for this particular glitch. Much thanks!

• possible duplicate of Prove by mathematical induction that $2n ≤ 2^n$, for all integer $n≥1$? Jul 14 '15 at 2:56
• @msteve How is that a duplicate? Obviously $n<2n$, but that is not the same. Jul 14 '15 at 3:07
• They're both proofs of virtually the same statement - at the very least it's worth pointing out that the other thread is there. Jul 14 '15 at 3:09
• @msteve Sure, I would give the link, but I wouldn't actually try to have the question closed because of the similarity. That doesn't seem reasonable. Jul 14 '15 at 3:10
• @msteve I didn't mean to come across as contentious if I did--I can see how such a vote would make sense, but I'm hoping OP will learn a thing or two about induction proofs here (writing up an answer right now). :) Cheers. Jul 14 '15 at 3:13

$2^{k+1}=2\cdot2^{k}=2^{k}+2^{k}$, which will be greater than $2^{k}+1$ so long as $2^{k}>1$. This is true for all values of $k$ you're considering.

Oddly enough, one of the most difficult things about induction problems is actually writing a clear induction proof. As such, I will provide a proof in the spirit of the template I provided a link to above. Hopefully it will clear up any confusion you may have on the matter.

Claim: For all $n\geq 1, n<2^n$.

Proof. For any integer $n\geq 1$, let $S(n)$ denote the statement $$S(n) : n<2^n.$$ Base step ($n=1$): $S(1)$ says that $1<2^1$, and this is true.

Inductive step $S(k)\to S(k+1)$: Fix some $k\geq 1$. Assume that $$S(k) : \color{green}{k<2^k}$$ holds. To be shown is that $$S(k+1) : \color{blue}{k+1<2^{k+1}}$$ follows. Beginning with the left side of $S(k+1)$, \begin{align} \color{green}{k}+1 &< \color{green}{2^k}+1\tag{by $S(k)$, the ind. hyp.}\\[0.5em] &< 2^k+2^k\tag{since $1<2^k$ for all $k\geq 1$}\\[0.5em] &= 2\cdot 2^k\tag{group like terms}\\[0.5em] &= \color{blue}{2^{k+1}}\tag{exponent law} \end{align} one arrives at the right side of $S(k+1)$, thereby showing $S(k+1)$ is also true, completing the inductive step.

Conclusion: By mathematical induction, the statement $S(n)$ is true for all $n\geq 1$. $\blacksquare$

Another approach: $2^1=2 >1$ and left hand side grows faster than R.H side after $x=1/2$, i.e., $\frac {d}{dx} 2^x = \frac {d}{dx} (e^{xln2})=ln2(2^x)> \frac {d}{dx}(x)=1$ for $n>1/2$

So $2^1>1$ , and $2^n$ grows faster than $n$ after $n=1$ ( after around $x=1/2$).