Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
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
2  
Welcome back. :) –  J. M. Oct 17 '11 at 16:45
2  
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$.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.