What is $\lim\limits_{n\to\infty} \frac{n^d}{ {n+d \choose d} }$ in terms of $d$? Does the limit exist? Is there a simple upper bound interms of $d$?
What is $\lim\limits_{n\to\infty} \frac{n^d}{ {n+d \choose d} }$?
-
0I think the limit sould exist and is a function of $d$. Because the denominator is $\sim n^d$ when $n\rightarrow \infty$ – 2012-09-20
3 Answers
Write $\frac{n^d}{(n+d)!}d!n!=d!\prod_{j=1}^d\frac{n}{n+j}$ to see that the expected limit is $d!$.
-
0Thanks guys, I've corrected. – 2012-09-20
$n^d\frac{n!\,d\,!}{(n+d)!}=d\,!\,(\frac{n}{n+1})(\frac{n}{n+2})\ldots(\frac{n}{n+d})$
Note that the R.H.S. contains a finite number of terms ($=d$) each tending to 1.
Hence the limit is $d\,!$
To find an upper bound you can simply do this
$d\,!\,(\frac{n}{n+1})(\frac{n}{n+2})\ldots(\frac{n}{n+d})
$d\,!\,(\frac{n}{n+1})(\frac{n}{n+2})\ldots(\frac{n}{n+d})
So your upper bound is $d\,!$
Another Method (Just to show that it the sequence is convergent)
Let us treat the given term $n^d\frac{n!\,d\,!}{(n+d)!}$ as term of sequces $\{x_n\}$.
Since we have shown that the sequence is bounded, it will suffice to show that the sequence is monotonically increasing.
We will now show that it is monotonically increasing.
$\frac{n}{n+r}-\frac{m}{m+r}=\frac{r(n-m)}{(n+r)(m+r)}>0 \quad\forall\; n>m>0\quad \& \quad\forall r>0$
Let $n>m$
Then $n!>m!$ and each term $\frac{n}{n+r}>\frac{m}{m+r} \quad \forall r \in \{1, 2, \ldots ,d\}$, we have proved this above.
Hecne $x_n \gt m_m$ (as $a>a' \quad \& \quad b\gt b'\implies a.b>a'.b' \quad \forall a,a',b,b'>0$ )
If you want to see how a monotonically increasing sequence which is upper bounded is convergent go to this link.
You can use the Stirling approximation $ n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n\,, $
after writing your expression in the form
$ d!\frac{n^d n!}{(n+d)!} $
$ d!\frac{n^d n!}{(n+d)!} \sim d! \frac{n^d \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n }{\sqrt{2 \pi (n+d)} \left(\frac{n+d}{e}\right)^{n+d}}= d!\, {\rm e}^d \left(\frac{n}{n+d}\right)^{n} \left(\frac{n}{n+d}\right)^{d} \left(\frac{n}{n+d}\right)^{\frac{1}{2}}$
$ \rightarrow d! \,{\rm e}^d \, \,{\rm e}^{-d}\, 1.1 = d!\,, \quad n \rightarrow \infty $