MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How can one show $\displaystyle\frac{(m+n-1)!}{m ! (n-1)!}\leq \left[\frac{e (m+n-1)}{n}\right]^{n-1}$ ?

share|cite|improve this question
Have you tried Stirling's approximation? – S. Carnahan Jun 12 '10 at 7:50
Surely this is homework question. I did a course this year and that was the first question on the first problem sheet. – alext87 Jun 12 '10 at 7:55
I did try Stirling's approximation but am unable to get this expression. – Vagabond Jun 12 '10 at 8:29
The first and obvious approach is to use induction on $n$. In (see also I had a similar estimate; there however the deal was bout the beta-integral. So, if you take the reciprocal of both sides you can use the estimate from that paper (it's quite sharp). – Wadim Zudilin Jun 12 '10 at 8:38
up vote 4 down vote accepted

Denote the quotient of the right and left hand sides, $$ f(m,n)=\biggl(\frac{e(m+n-1)}n\biggr)^{n-1}\bigg/\binom{m+n-1}m. $$ Then $f(m,1)=1$ for all $m\in\mathbb N$ and $$ \frac{f(m,n+1)}{f(m,n)} =\frac{e}{\biggl(1+\dfrac1n\biggr)^n}\cdot\biggl(1+\frac1{m+n-1}\biggr)^{n-1} > 1, $$ that is, $$ f(m,n+1)> f(m,n)>\dots> f(m,2)> f(m,1)=1. $$ This proves the required inequality.

share|cite|improve this answer
Thankyou, but I am still rather curious to know how one arrives at such an inequality ? Supposing I dont know this bound and am interested to find a bound, ( I cannot use induction then). I suppose there has to be a way to get a good bound. Is there ? – Vagabond Jun 12 '10 at 11:01
The main property of the binomial coefficients is that the quotients of consecutive terms is rational in both parameters. Then you try to approximate this quotient by a simpler function... Another source of extimates for the binomials is Stirling's formula for the gamma function (mentioned above by Scott). Then one can use the beta integral (which is the reciprocal of a binomial coefficient) and do the estimates for it. – Wadim Zudilin Jun 12 '10 at 11:06

Another immediate proof can be obtained from $$ \frac{(m+n-1)!}{m!}\le(m+n-1)^{n-1} $$ (which is obvious) and $$ \left(\frac{n}{e}\right)^{n-1}\le(n-1)! $$ which after multiplying by $n$ and taking logs becomes $$ n\log(n)-n+1\le\sum_{k=2}^{n}\log(k) $$ which is immediate as the RHS is an obvious upper bound for $$ \int_1^n\log(x)\,dx=(x\log(x)-x)|_1^n=n\log(n)-n+1. $$

share|cite|improve this answer
Thankyou, this was easy. – Vagabond Jun 14 '10 at 6:45
Vladimir, this OP is the 2nd one when our solutions are compared from the "easyness" point of view ( The two solutions are equally easy and equally standard... :-) – Wadim Zudilin Jun 14 '10 at 8:09
Wadim, I couldn't agree more - they are both easy and standard indeed. – Vladimir Dotsenko Jun 14 '10 at 9:17
Vladimir, I have a special smile for this: $\dddot\smile$ – Wadim Zudilin Jun 14 '10 at 12:02

Your Answer


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.