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

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\on}[1]{\operatorname{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ $\ds{\bbox[5px,#ffd]{}}$ $\ds{\color{#44f}{\left.\sum_{i = 0}^{n}{\ds{n \choose i} \over \ds{2n - 1 \choose i}}\right\vert_{n = 0}} = {\Large 1}}$

---

\begin{align} & \color{#44f}{\left.\sum_{i = 0}^{n}{\ds{n \choose i} \over \ds{2n - 1 \choose i}} \right\vert_{n\ \in\ \mathbb{N}_{\,\geq\, 1}}} = \ \sum_{i = 0}^{n}{n \choose i} {\Gamma\pars{i + 1}\Gamma\pars{2n - i} \over \Gamma\pars{2n}} \\[5mm] = & \ 1 + \sum_{i = 1}^{n}{n \choose i}i\ {\Gamma\pars{i}\Gamma\pars{2n - i} \over \Gamma\pars{2n}} \\[5mm] = & \ 1 + \sum_{i = 1}^{n}{n \choose i}i \int_{0}^{1}t^{i - 1}\,\,\pars{1 - t}^{2n - i - 1} \,\,\,\dd t \\[5mm] = & \ 1 + \int_{0}^{1}{\pars{1 - t}^{2n - 1} \over t}\,\,\,\, \overbrace{\sum_{i = 1}^{n}{n \choose i}i \pars{t \over 1 - t}^{i}\,\,} ^{\ds{nt\pars{1 - t}^{-n}}}\,\,\,\dd t \\[5mm] = & \ 1 + n\int_{0}^{1}\pars{1 - t}^{n - 1}\,\,\dd t = {\Large 2} \end{align} Therefore, $$ \color{#44f}{\left.\sum_{i = 0}^{n}{\ds{n \choose i} \over \ds{2n - 1 \choose i}} \right\vert_{n\ \in\ \mathbb{N}_{\,\geq\, 0}}} = \bbx{\color{#44f}{2 - \delta_{n0}}} $$