# What is $\lim\limits_{n\to\infty} \frac{n^d}{ {n+d \choose d} }$?

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

-
I think the limit sould exist and is a function of $d$. Because the denominator is $\sim n^d$ when $n\rightarrow \infty$ – Seyhmus Güngören Sep 20 '12 at 11:59

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

-
You mean "... is $d!$" instead of $n!$. – martini Sep 20 '12 at 12:00
I think there is a little mistake here. – Seyhmus Güngören Sep 20 '12 at 12:02
The denominator in the product should be $n+j$. – celtschk Sep 20 '12 at 12:15
Thanks guys, I've corrected. – Davide Giraudo Sep 20 '12 at 12:26

$$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})(\frac{n}{n})\ldots(\frac{n}{n})$

$d\,!\,(\frac{n}{n+1})(\frac{n}{n+2})\ldots(\frac{n}{n+d})<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$$

-