3
$\begingroup$

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.

  • 0
    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?2012-05-26

1 Answers 1

8

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

  • 0
    @ Didier: i suppose you replaced an by$n$and bn by m. But starting your summation from$0$it explains why you got there $\frac {a+b}{b}$, that is mainly $\frac{a}{b} + 1$, where$1$must the term you got for k=0. Nice work.2012-05-26