Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
2  
Internal monologue: How shall I use the assumption that $2^k \gt k$ to prove $2^{k+1}\gt k+1$. Well, $2^{k+1}=2\cdot 2^k$. If I know $2^k\gt k$, then I know $2^{k+1}\gt 2k$. Can I show that $2k\ge k+1$? That would do it. But of course $2k\ge k+1$ (if $k\ge 1$). OK, let's write it up. –  André Nicolas Dec 3 '12 at 4:23
add comment

2 Answers

up vote 2 down vote accepted

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).

share|improve this answer
add comment

Let $P(n)$ be the statement that $n<2^n$. Since $1<2^1$, we have that $P(1)$ is true.

Suppose $P(k)$ is true for some positive integer $k$. Then $k<2^k$, so that $k+1<2^k+1<2^k+2^k=2^{k+1}$. Hence $P(k+1)$ is true.

It follows that $P(n)$ is true for all positive integers $n$.

share|improve this answer
    
I'm not sure to understand where the $2^{k}$ + 1 < $2^{k}$ + $2^{k}$ comes from. –  wwwe Dec 3 '12 at 5:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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