2
$\begingroup$

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!

$\endgroup$
8
  • $\begingroup$ possible duplicate of Prove by mathematical induction that $2n ≤ 2^n$, for all integer $n≥1$? $\endgroup$
    – msteve
    Jul 14 '15 at 2:56
  • 1
    $\begingroup$ @msteve How is that a duplicate? Obviously $n<2n$, but that is not the same. $\endgroup$ Jul 14 '15 at 3:07
  • $\begingroup$ They're both proofs of virtually the same statement - at the very least it's worth pointing out that the other thread is there. $\endgroup$
    – msteve
    Jul 14 '15 at 3:09
  • $\begingroup$ @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. $\endgroup$ Jul 14 '15 at 3:10
  • 1
    $\begingroup$ @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. $\endgroup$ Jul 14 '15 at 3:13
5
$\begingroup$

$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.

$\endgroup$
4
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.