# Prove that for all $n$ in the natural numbers, $n(n - 1) < 2^n$

This seems like a fairly easy induction problem but I am a bit rusty. I have the first two steps -- that the statement holds for $n = 1$, and I am assuming that for $n = k$, $k(k - 1) < 2^k$.

Now for showing it holds for $n = k + 1$:

$$(k + 1)(k + 1 - 1) < 2^{k + 1}$$

$$k(k + 1) < 2^{k + 1}$$

$$k^2 + k < 2^{k + 1}$$

... here I am stuck. Can anyone point me in the right direction?

-

Hint: You have $k(k-1) < 2^k$ from induction hypothesis and you want to show that $k(k+1) < 2^{k+1}$. We have $$k(k+1) = k(k-1) \frac{k+1}{k-1}.$$ Note that $\forall k > 2$, we have $\frac{k+1}{k-1} \leq 2$. Hence, along with induction hypothesis, we get $$k(k+1) = k(k-1) \frac{k+1}{k-1} < 2^k \times 2 = 2^{k+1}$$

-
Thank you. Is it better in general to start from the induction hypothesis and work forwards when dealing with inequalities? – Matt Nashra Oct 17 '11 at 16:41
Welcome back. :) – J. M. Oct 17 '11 at 16:45
Thanks J.M. :) I was missing my daily doze of math.stack.exchange for the last couple of months :) – user17762 Oct 17 '11 at 16:48

Another solution is given by $2^n = (1 + 1)^n = \displaystyle{\sum_{k=0}^{n}}{n \choose k} = {n \choose 0} + {n \choose 1} +\ldots + {n \choose n} > 2{n \choose 2} = n(n - 1)$ para todo $n$.

-

HINT $\$ It's true for $\rm\:n = 0,1\:,\:$ so it suffices to show that $\rm\:f(n) = 2^n/(n\:(n-1)) > 1\:,\:$ for $\rm\:n \ge 2\:.\:$ Since $\rm\:f(2) = 2\:$ it suffices to show that $\rm\:f\:$ is increasing $\rm\:f(k+1) \ge f(k)\:$ for $\rm\:k\ge 3\:.\:$ Be we have $\rm\: 1 \le f(k+1)/f(k) = 2\:(k-1)/(k+1)\:$ $\iff$ $\rm\:k+1\: \le 2\ k-2\:$ $\iff$ $\rm\:k \ge 3\:.\ \$ QED

NOTE $\$ In effect we have proved that $\rm\:f(n)>1\:$ by rewriting it as a product of terms $> 1\:,\:$ a rather trivial induction. This is a prototypical example of (multiplicative) telescopy. You can find much further discussion of such telescopic products and sums in many of my prior posts on telescopy.

-