# Proof for $\sum_{i=0}^n \frac{n \choose i}{{2n-1} \choose i} = 2$.

I stumbled upon this strange equivalence for all integers $$n>0$$: $$$$\sum_{i=0}^n \frac{n \choose i}{{2n-1} \choose i} = 2 \\$$$$ And tried numerous other integer triples $$(a,b,c)$$ to see if: $$\sum_{i=0}^n \frac{an \choose i}{{bn+c} \choose i}$$ Was ever constant for all $$n$$, but could not find any. I am wondering how to prove the case for $$(a,b,c)=(1,2-1)$$, and how to find other triplets.

My attempt: I do not know many equivalences in combinatorics, but I began with: $$\frac{n \choose i}{{2n} \choose i} - \frac{n \choose {i+1}}{{2n} \choose i+1} = \frac{n!(2n-i)!}{(n-i)!2n!} - \frac{n!(2n-i-1)!}{(n-i-1)!2n!}$$ Mostly because I see a $$2n-1$$ appear, but am not sure if this is correct, and am not quite sure how to pick apart the right hand side further if it is.

## 2 Answers

From the hockey stick identity we have $$\begin{eqnarray*} \sum_{i=0}^{n} \binom{2n-i-1}{n-1} = \binom{2n}{n} = 2 \binom{2n-1}{n}. \end{eqnarray*}$$ This can be rearranged to give your identity.

Alternatively, using the Beta function $$\begin{eqnarray*} \binom{2n-1}{i} ^{-1} = 2n \int_0^1 t^i (1-t)^{2n-i-1} dt. \end{eqnarray*}$$ Substituting this gives $$\begin{eqnarray*} \sum_{i=0}^{n} \binom{n}{i} \binom{2n-1}{i}^{-1} & = & 2n \int_0^1 \sum_{i=0}^{n} \binom{n}{i} t^i (1-t)^{2n-i-1} dt \\ & = & 2n \int_0^1 \left( 1+ \frac{t}{1-t} \right)^n (1-t)^{2n-1} dt \\ & = & 2n \int_0^1 (1-t)^{n-1} dt = \color{red}{2}. \\ \end{eqnarray*}$$ And this method might be more useful when trying to generalise your identity.

In general, for any integers $$n,k\ge 0$$ are, we have
$$\boxed{\sum_{i=0}^n \frac{\binom{n}{i}}{\binom{n+k}i}=\frac{n+k+1}{k+1}.}$$ Your problems is the special case $$k=n-1$$.

To see this, imagine you have a shuffled deck with $$n$$ black cards and $$k$$ red cards. You deal cards from the top until you get a red card. What is exepcted number of cards dealt?

Letting $$X$$ be the number of cards dealt, then $$E[X]=\sum_{i=0}^\infty P(X>i)=\sum_{i=0}^n \frac{\binom{n}{i}}{\binom{n+k}i}$$ because the event $$\{X>i\}$$ occurs if the first $$i$$ cards are all chosen from the $$n$$ black cards, out of a total of $$\binom{n+k}{i}$$ ways to choose the first $$i$$ cards.

On the other hand, the $$k$$ red cards divide the deck into $$k+1$$ sections. Each black card is equally likely to fall in each section, so the probability a particular black card is in the top section is $$\frac1{k+1}$$. Therefore, the expected number of black cards in the top section is $$n\cdot \frac1{k+1}$$, so the expected number of cards dealt is $$E[X]=1+\frac{n}{k+1}=\frac{n+k+1}{k+1}.$$