0
$\begingroup$

This question already has an answer here:

Today in class, the instructor is trying to show that for $n \ge 0$, $n < 2^n$. And this are the steps he took:

First we assume the inductive hypothesis i.e. $0 < 2^0$, and this is true. Then to prove that for any arbitrary integer $k \ge 0$, $k < 2^k$. The proof proceeds as follows:

  1. Assume $k < 2^k$ is true for $k ge 0$.

  2. Show that $(k + 1) < 2 ^{k + 1}$.

  3. By induction hypothesis, $k < 2^k$ thus $k + 1 < 2^k + 1 < 2^k + 2^k = 2^{k + 1}$.

Thus by mathematical induction the result has been proven

My question now is how was step 3 derived? Where does the extra $2^k$ manifest from?

$\endgroup$

marked as duplicate by 6005, Adam Hughes, quid, Moishe Kohan, Namaste Jan 8 '15 at 0:15

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ $2^k+2^k = 2\times2^k = 2^{k+1}$ $\endgroup$ – Frank Vel Oct 7 '14 at 18:09
  • $\begingroup$ @fvel My question is in regards to the $2^k$ right before the '=' sign in that last step. The exponent trick there is obvious to me $\endgroup$ – smac89 Oct 7 '14 at 18:10
2
$\begingroup$

In step 3 he uses the induction hypothesis $k < 2^k$. With that you directly get $k+1 < 2^k +1$. Since $1 \leq 2^k$ for $k \geq 0$ (this is where the "extra" $2^k$ comes from) you get $2^k + 1 \leq 2^k +2^k$. Then finally he uses an exponent law to get the desired result.

$\endgroup$
0
$\begingroup$

You are to assume that n=k is true, and show that IF n=k+1 is also true, then your whole statement holds (if you've already shown that your first value is true, usually n=0). Imagine a domino effect.

What this means, is usually, you'll sub in what you found in your assumed term n=k, into your n=k+1 term to assist you into something that is obviously true if it's not immediately evident. This is what your teacher did, he used the inequality from the assumed n=k and included it to finalize the proof in n=k+1

$\endgroup$

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