Prove that $n<2^n$ for every positive integer $n$.
$P(1): 1 < 2^1$
$n+1<2^n+1$ for induction hypothesis
$n+1<2^n+2^n$ I can't undertstand this passage (this is from my teacher's slide)
$n+1<(2)2^n$
$n+1<2^{n+1}$
$\endgroup$ 11 Answer
$\begingroup$Assume that $n<2^n$ is true.
We need to prove that $n+1<2^{n+1}$ is also true.
This is true because $n<2^n\Rightarrow n+1<2^n+1<2^n+2^n<2^n\times2=2^{n+1}$
($2^n>1$ for all $n\in\mathbb{Z^+}$)
$\endgroup$ 2
