# bound for binomial coefficients

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

-
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 dx.doi.org/10.1007/s11139-006-0075-1 (see also arXiv.org/abs/math/0304021) 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

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.

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

-
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 (mathoverflow.net/questions/25855). 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