Proof by induction steps

Question

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?

Answer 1

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.

Answer 2

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