# Proof by induction steps [duplicate]

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?

## marked as duplicate by 6005, Adam Hughes, quid♦, Moishe Kohan, NamasteJan 8 '15 at 0:15

• $2^k+2^k = 2\times2^k = 2^{k+1}$ – Frank Vel Oct 7 '14 at 18:09
• @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 – smac89 Oct 7 '14 at 18:10
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.