1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Have you tried Stirling's approximation? $\endgroup$
    – S. Carnahan
    Jun 12, 2010 at 7:50
  • 1
    $\begingroup$ Surely this is homework question. I did a course this year and that was the first question on the first problem sheet. $\endgroup$
    – alext87
    Jun 12, 2010 at 7:55
  • $\begingroup$ I did try Stirling's approximation but am unable to get this expression. $\endgroup$
    – Vagabond
    Jun 12, 2010 at 8:29
  • $\begingroup$ 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). $\endgroup$ Jun 12, 2010 at 8:38

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 ? $\endgroup$
    – Vagabond
    Jun 12, 2010 at 11:01
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 12, 2010 at 11:06
4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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... :-) $\endgroup$ Jun 14, 2010 at 8:09
  • $\begingroup$ Wadim, I couldn't agree more - they are both easy and standard indeed. $\endgroup$ Jun 14, 2010 at 9:17
  • $\begingroup$ Vladimir, I have a special smile for this: $\dddot\smile$ $\endgroup$ Jun 14, 2010 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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