4
$\begingroup$

I stumbled upon this strange equivalence for all integers $n>0$: \begin{equation} \sum_{i=0}^n \frac{n \choose i}{{2n-1} \choose i} = 2 \\ \end{equation} 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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.