1
$\begingroup$

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?

3 Answers 3

4

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

  • 2
    Thanks J.M. :) I was missing my daily doze of math.stack.exchange for the last couple of months :)2011-10-17
4

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

1

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.