4
$\begingroup$

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

  • 0
    IvyMike: Check out [this](http://en.wikipedia.org/wiki/Help:Displaying_a_formula) and [this](http://www.codecogs.com/latex/eqneditor.php) 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.2012-12-15
  • 2
    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$.2012-12-15
  • 0
    @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?2012-12-15
  • 0
    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$.2012-12-15
  • 0
    @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.2012-12-15

1 Answers 1

8

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

  • 0
    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.."?2012-12-15
  • 0
    @IvyMike It is the definition of ${n \choose r}$, which is equivalent to $_{n}C_{r}$.2012-12-15
  • 0
    @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.."2012-12-15
  • 0
    @IvyMike I'm puzzled by that, too. I can't find that identity within Wikipedia's page for binomial coefficients, and I don't see how he arrived at it.2012-12-15
  • 3
    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.2012-12-15
  • 2
    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!$.2012-12-15
  • 0
    @anon Thank you, anon. I should've considered the obvious: Checking the expansion! :-P2012-12-15
  • 0
    @Clayton I see..BTW mate, I believe Jacob anyways.Look at his credentials on this forum.He sure is a smart fellow and definitely knows better!!2012-12-15
  • 0
    @anon Thanks for making it simple.2012-12-15
  • 0
    @IvyMike Thanks for the vote of confidence. But I make mistakes like everyone else and it's always best to question any math you read. I also wrote the product formula in a somewhat non-standard manner.2012-12-15
  • 0
    @Jacob If you can write it in a standard form then it will all the better for those who find the non-standard form a bit hard to understand.2012-12-15