# Please prove that ${n\choose r} < (n+1)^r$. My induction-based proof is ugly!

I came across this inequality in the University of Missouri Youtube Channel lecture 38:

College Algebra - Lecture 38 - The Binominal Theorem

The professor asks us 1:01:00 into the video to prove that "$1001^{999} < 1000^{1000}$" and throws in the above inequality as a fact that we can use in our proof. Proving "$1001^{999} < 1000^{1000}$" using the assumption that ${n\choose r} < (n+1)^r$ is rather easy. But I don't want to accept it by rote that ${n\choose r} < (n+1)^r$. So I tried to prove it using induction for any value of $r$. I proved that the base case when $r=1$ is true. Then went on to prove that if it is true for any $r$, then it is true for $r+1$ as well. Although I proved it using induction, it's a really ugly and messy proof. So please give me a neat proof for this inequality. I am sure it would be very easy for any regular contributor in this forum. Thanks.

PS: Please bear with my wordiness at the moment. I just don't know yet how to format my text or use mathematical symbols on this forum (It will be nice of you if you can tell in passing where to learn the markup and formatting code for this forum).

-
IvyMike: Check out this and this to get some $\LaTeX$ experience. You should be able to click 'edit' on various answers and questions on MSE to see how others have formatted their posts. @Elias There are other ways of formatting binomial coefficients than as matrices. For instance, {n\choose r} or \binom{n}{r}. Also, often there is more to work on in a question than just formatting in the title - here, there was latex and spaces after punctuation in the body too that could be worked on. –  anon Dec 15 '12 at 18:13
There is a lot of slack in the inequality, except at $r=0$, where it fails. Expand $(1+n)^r$ using the Binomial Theorem. One of the terms is $\binom{n}{r}n^r$. So $\binom{n}{r}\le (1+n)^r/n^r$. –  André Nicolas Dec 15 '12 at 18:29
@Andre Lot of slack in the inequality?Now I am at a loss what to say.The professor in the video,Mr Richard Delaware of University of Missouri,is otherwise a meticulous fellow.Andre, do you mean this inequality doesn't hold true even in many cases when r is a number other than 0?It's not an identity?I should take it with a pinch of salt? –  Ivy Mike Dec 15 '12 at 18:36
I observed that the inequality fails at $r=0$, we get equality. But it definitely is true in all other cases. By "lots of slack" I meant that typically $\binom{n}{r}$ is much smaller than $(1+n)^r$. –  André Nicolas Dec 15 '12 at 18:38
@AndréNicolas Thanks for clarifying what you mean by "lots of slack".I felt you had doubt about the validity of the inequality itself.Now the whole thing is clear. –  Ivy Mike Dec 15 '12 at 19:06

Note that

$$\binom{n}{r}=\frac{n!}{(n-r)!r!}=\prod_{k=1}^{r} \frac{n-(r-k)}{k}.$$

So we have that

$$\binom{n}{r} \leq n\cdot (n-1)\cdots (n-r+1) < (n+1)^r.$$

-
Jacod, you see, I am not as bright as you assume!!So can you be kind enough to elaborate a little on how we get the first equation you gave..the one after "Note that.."? –  Ivy Mike Dec 15 '12 at 18:00
@IvyMike It is the definition of ${n \choose r}$, which is equivalent to $_{n}C_{r}$. –  000 Dec 15 '12 at 18:08
@Limitless I know that much friend...it's only notation for the same thing.But what I failed to grasp was how it was equated to the right most term involving k,r and n.The rightmost term in the equation after "Note that.." –  Ivy Mike Dec 15 '12 at 18:12
If you try to write out a few terms of the definition and the right-most side, you'll almost certainly see that they are equal. –  Clayton Dec 15 '12 at 18:14
The top of the product will be $n(n-1)\cdots(n-(r-1))$ which is $n!/(n-r)!$. The denominator of the product will be $(1+0)\cdots(1+(r-1))$ which is $r!$. –  anon Dec 15 '12 at 18:15