# Proof by induction - Being stuck before being able to prove anything!

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!

-
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

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

-

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

-
I'm not sure to understand where the $2^{k}$ + 1 < $2^{k}$ + $2^{k}$ comes from. – wwwe Dec 3 '12 at 5:27