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

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

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

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

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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