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?
 A: 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}$$
A: 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$.
A: 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.
