6
$\begingroup$

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

  • 0
    I 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 3

7

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

  • 0
    Thanks guys, I've corrected.2012-09-20
3

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

2

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 $