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.

Compute the limit:

$$\lim_{n\to\infty} \sum_{k=0}^n \frac {\dbinom{n}{k}}{\dbinom{2n-1}{k}}$$

Here i tried to give some k values to the sum hoping to see a possible pattern, but i didn't figure out any such a pattern. I wonder if there is an easy way to solve such a limit.

share|improve this question
    
Here i tried to give some k values to the sum hoping to see a possible pattern, but i didn't figure out any such a pattern... This is odd since each sum equals exactly $2$, see my comment to Brian's answer. –  Did May 26 '12 at 7:28
    
@Didier: i couldn't even imagine that for all k the sum will remail the same. I was thinking that it's going to change after more values going to oo. Since it's a limit there one expects to use some specific limit tools in order to find the answer. –  Chris's sis May 26 '12 at 7:44
    
The point is that you write i tried... hoping to see a possible pattern but that as soon as one tries anything, the pattern becomes obvious. So, what did you try? –  Did May 26 '12 at 7:47
    
@Didier: i just gave some specific values to k, k=0, k=1, k=2 but i think this wasn't a good way ... though and let n unchanged. At first i did it with n unchanged and after Brian's remark, i used it properly. The binomials are the things that entangle me at most. I make a lot of mistakes here. –  Chris's sis May 26 '12 at 7:52
    
If i used the Brian's remark for another proof then i shoud use induction, isn't it? I need to prove that if P(n) is true then P(n+1) is true. Is there any other way or just induction? –  Chris's sis May 26 '12 at 8:06
add comment

1 Answer 1

up vote 8 down vote accepted

First expand the fraction:

$$\frac {\dbinom{n}{k}}{\dbinom{2n-1}{k}}=\frac{n!k!(2n-1-k)!}{k!(n-k)!(2n-1)!}=\frac{n!(2n-1-k)!}{(n-k)!(2n-1)!}=\frac{n!}{(2n-1)!}\cdot\frac{(2n-1-k)!}{(n-k)!}\;.$$

Thus,

$$\begin{align*} \lim_{n\to\infty} \sum_{k=0}^n \frac {\dbinom{n}{k}}{\dbinom{2n-1}{k}}&=\lim_{n\to\infty}\frac{n!}{(2n-1)!}\sum_{k=0}^n\frac{(2n-1-k)!}{(n-k)!}\\\\ &=\lim_{n\to\infty}\frac{n!}{(2n-1)!}\sum_{k=0}^n\frac{(n-1+k)!}{k!}\\\\ &=\lim_{n\to\infty}\frac{n!(n-1)!}{(2n-1)!}\sum_{k=0}^n\frac{(n-1+k)!}{k!(n-1)!}\\\\ &=\lim_{n\to\infty}\binom{2n-1}{n}^{-1}\sum_{k=0}^n\binom{n-1+k}{n-1}\\\\ &=\lim_{n\to\infty}\binom{2n-1}{n}^{-1}\binom{2n}n\\\\ &=\lim_{n\to\infty}\frac{n!(n-1)!(2n)!}{(2n-1)!n!^2}\\\\ &=\lim_{n\to\infty}\frac{2n}n\\\\ &=2\;. \end{align*}$$

Note that the sum is $2$ for all $n>0$, so the limits in the problem statement and the calculation are superfluous, though I discovered this only at the end of the calculation, when it came as a pleasant surprise. If I wanted to present a polished version of the argument, I would go back and remove ‘$\lim\limits_{n\to\infty}$’ everywhere that it appears.

Added: This result has a rather nice interpretation. The $k=0$ term in the summation is always $1$, so we’ve shown that $$\sum_{k=1}^n\frac{\dbinom{n}k}{\dbinom{2n-1}k}=1$$ for $n>0$. Now imagine that you have a box of $2n-1$ marbles, identical save for their color: $n$ are black, and $n-1$ are white. You perform $n$ independent experiments $E_1,\dots,E_n$ determining the values of $n$ random variables $X_1,\dots,X_n$ respectively. $E_k$ consists in drawing a random sample of $k$ marbles from the box; the experiment is a success if the sample consists entirely of black marbles, in which case $X_k=1$; otherwise, if the sample contains at least one white marble, $X_k=0$. Clearly $$\Bbb E(X_k)=\mathrm{Pr}(X_k=1)=\frac{\dbinom{n}k}{\dbinom{2n-1}k}\;.$$ Now let $X=\sum\limits_{k=1}^nX_k$, the number of successes in the $n$ experiments taken together. Then

$$\Bbb E(X)=\sum_{k=1}^n\Bbb E(X_k)=\sum_{k=1}^n\frac{\dbinom{n}k}{\dbinom{2n-1}k}=1\;,$$

meaning that on average we can expect one success among the $n$ experiments.

(This would be even nicer if I could see a good intuitive reason to expect one success on average!)

share|improve this answer
    
I don't mean to be pedantic, but did you mean $(n-k)!$ or $n-k!$ on the first line? –  E.O. May 26 '12 at 7:12
    
@E.O.: $n-k!$ was definitely a typo; thanks. –  Brian M. Scott May 26 '12 at 7:14
1  
Here is an explanation for the one success in average result. First, drawing the $2n-1$ marbles one by one without replacement and considering the number of black marbles before the first white marble appears, yields the same expectation. Second, add a white marble in the bag, imagine this new marble is drawn at time $0$ and decorate the discrete circle of size $2n$ by the colors of the marbles according to the order which they appeared in. This yields $n$ black intervals with total length $n$, separated by $n$ white marbles. .../... –  Did May 26 '12 at 8:50
1  
.../... By exchangeability each interval has the same average length, hence this average length must be $1$ and you are done. –  Did May 26 '12 at 8:52
3  
By the same reasoning, for every positive integers $a$, $b$ and $n$, $$\sum\limits_{k=1}^{an}\frac{{an\choose k}}{{(a+b)n-1\choose k}}=\frac{a}b.$$ –  Did May 26 '12 at 9:15
show 17 more comments

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.