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
    *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.2012-05-26
  • 0
    @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.2012-05-26
  • 0
    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?2012-05-26
  • 0
    @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.2012-05-26
  • 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
    I don't mean to be pedantic, but did you mean $(n-k)!$ or $n-k!$ on the first line?2012-05-26
  • 0
    @E.O.: $n-k!$ was definitely a typo; thanks.2012-05-26
  • 0
    Does the above show that each sum is exactly $2$? If so, the proof could omit any mention of limits.2012-05-26
  • 0
    It does, and the proof could; I chose to cast it in a form corresponding to the question, but I probably should add a note pointing out explicitly that the limits were irrelevant.2012-05-26
  • 0
    @Brian M. Scott: nice proof and very relevant remark about the fact that for all $n>0$ the limit is 2. Thanks.2012-05-26
  • 0
    @Chris: Yeah, thanks. In a meantime I got the trick.2012-05-26
  • 0
    @Brian M. Scott: in order to use your remark i should use induction, isn't it?2012-05-26
  • 0
    @Chris: No induction is needed: the calculation (without the limits) is valid for arbitrary $n>0$.2012-05-26
  • 0
    My advice would be to get rid of the limits altogether. Imagine somebody asking a proof that the asymptotic proportion of *even* primes is less than the asymptotic proportion of *odd* primes. Now, this is a true fact but I guess you would rather answer with a stronger statement...2012-05-26
  • 0
    @Brian M. Scott: how may i prove that it is true for all n>0? My teacher may ask me to prove that it's true.2012-05-26
  • 0
    @Chris: Exactly as I did: just remove ‘$\lim\limits_{n\to\infty}$’ everywhere it appears. You’ll need to be prepared to justify two things: the step that m.woj asked about, and the step $\sum_{k=0}^n\binom{n-1+k}{n-1}=\binom{2n}n$. Everything else is very straightforward.2012-05-26
  • 0
    @Brian M. Scott: you're right. OK.2012-05-26
  • 0
    @Didier: I don’t think that the two cases are really parallel, and in any case I *have* made the stronger statement in here.2012-05-26
  • 0
    @Brian M. Scott: is there any simple way to prove your last identity, or do you know a link where i may see more details about it? Maybe i did it at school but i really can't remember any of it. Anyway, i'm searching right now for it ...2012-05-26
  • 0
    @Chris: It’s not hard to prove by induction; see *Hockey Stick Pattern* [here](http://www.cut-the-knot.org/arithmetic/combinatorics/PascalTriangleProperties.shtml). A combinatorial argument is also possible. There are $\binom{2n}n$ ways to choose $n$ numbers from $\{1,\dots,2n\}$. Alternatively, if the largest of the $n$ numbers is $n+k$, where $0\le k\le n$, there are $\binom{n-1+k}{n-1}$ ways to pick the $n-1$ smaller numbers. Summing over $k$ must give the total number of ways, or $\binom{2n}n$.2012-05-26
  • 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. .../...2012-05-26
  • 1
    .../... By exchangeability each interval has the same average length, hence this average length must be $1$ and you are done.2012-05-26
  • 0
    OK. Thanks guys. Your ideas here are great! Now it's time to ponder a while over them in order to clarify for myself all things written down here.2012-05-26
  • 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.$$2012-05-26
  • 0
    @Didier: too-good-to-be-true! :-)2012-05-26
  • 0
    And finally, the formula which implies all the others and which is easy to prove by induction over $n$: $$\sum_{k=0}^n\frac{{n\choose k}}{{n+m-1\choose k}}=\frac{n+m}{m}.$$2012-05-26
  • 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