How can one show $\displaystyle\frac{(m+n-1)!}{m ! (n-1)!}\leq \left[\frac{e (m+n-1)}{n}\right]^{n-1}$ ?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Have you tried Stirling's approximation? $\endgroup$– S. Carnahan ♦Commented 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$– alext87Commented Jun 12, 2010 at 7:55
-
$\begingroup$ I did try Stirling's approximation but am unable to get this expression. $\endgroup$– VagabondCommented 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$– Wadim ZudilinCommented Jun 12, 2010 at 8:38
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.
answered Jun 12, 2010 at 10:14
-
$\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$– VagabondCommented 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$ Commented Jun 12, 2010 at 11:06
$\begingroup$
$\endgroup$
3
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. $$
answered Jun 12, 2010 at 12:06
-
$\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$ Commented Jun 14, 2010 at 8:09
-
$\begingroup$ Wadim, I couldn't agree more - they are both easy and standard indeed. $\endgroup$ Commented Jun 14, 2010 at 9:17
-
$\begingroup$ Vladimir, I have a special smile for this: $\dddot\smile$ $\endgroup$ Commented Jun 14, 2010 at 12:02