I am currently in the process of learning how to prove statements
by induction. For the most part, I understand but I am at most
clueless when it comes to prove some inequalities.
For example, I am having a hard time proving that:
$n < 2^n$ is true. (Even if it's clear that it is indeed true!)
In the induction step, I am stuck with:
$n + 1 < 2^{n + 1}$
I don't know what would be the assumption I should make from this
statement.
Anyone could point me in the right direction?
Thanks!
Answer
Hint $\ $ First prove by induction this lemma: an increasing function stays $\ge$ its initial value, i.e. $\rm\:f(n\!+\!1)\ge f(n)\:\Rightarrow\:f(n)\ge f(0).$ Now apply this lemma to the function $\rm\:f(n) = 2^n\! - n,\:$ which is increasing by $\rm\:f(n\!+\!1)-f(n) = 2^n\!-1 \ge 0.\:$ Thus, by the lemma, $\rm\:f(n)\ge f(0) = 1,\:$ so $\rm\:2^n > n.$
Remark $\ $ Note that we reduce the proof to the same inequality as in Will's answer: $\rm\:2^n \ge 1$ (which, itself, may require an inductive proof, depending on the context). But here we've injected the additional insight that the inductive proof of the inequality can be viewed as a special case of the inductive proof of the inequality that an increasing function stays $\ge$ its initial value - which lends much conceptual insight into the induction process. Further, by abstracting out the lemma, we now have a tool that can be reused for analogous inductive proofs (and this simple tool often does the job - see my many prior posts on telescopy for further examples and discussion).
No comments:
Post a Comment