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!
 A: 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$.
A: 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).
A: I apologize for digging this up.  I just saw a nice combinatorial proof by AnotherJohnDoe in another thread, but for some reason, he deleted his answer, and that thread was locked.  Here is the argument.

Consider a set $S$ of $n$ elements. Then, the number of subsets of $S$ equals $2^n$.  This is greater than or equal to the number of single-element subsets plus the empty set.

