# Binomial fraction sum to infinity

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.

-
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 the artist 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 the artist 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 the artist May 26 '12 at 8:06

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!)

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