Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

3 Answers

up vote 7 down vote accepted

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

share|improve this answer
1  
You mean "... is $d!$" instead of $n!$. –  martini Sep 20 '12 at 12:00
1  
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
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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