Combinatorial identity with sum of binomial coefficients

Solution 1:

(New Answer, posted 28 Nov 2016)

Just had a quick look at this again, and noticed that there is a much shorter solution!

Using the subset-of-a-subset identity $\displaystyle\binom ab\binom bc=\binom ac\binom {a-c}{b-c}$, note that $$\begin{align}\binom {2n-1}n\binom nk&=\binom {2n-1}k\binom {2n-1-k}{n-k}\\ &=\binom {2n-1}k\binom {2n-1-k}{n-1}\end{align}$$ Cross-dividing and summing, $$\begin{align} \sum_{k=0}^n \frac {\displaystyle\binom nk}{\displaystyle\binom {2n-1}{k}} &=\sum_{k=0}^n\frac{\displaystyle\binom {2n-1-k}{n-1}}{\displaystyle\binom {2n-1}n}\\ &=\frac 1{\displaystyle\binom {2n-1}n}\sum_{r=0}^n\binom {n-1+r}{n-1}\qquad\qquad(r=n-k)\\ &=\frac{\displaystyle\binom {2n}n}{\displaystyle\binom {2n-1}n} \color{lightgray}{=\frac{(2n)(2n-1)(2n-2)\cdots (n+1)}{\qquad\; (2n-1)(2n-2)\cdots (n+1)n}}\\ &=\color{red}2 \end{align}$$ NB - No binomial coefficient expansion, no factorials!

(Original Answer, posted 26 Nov 2014)

$$\begin{align} \sum_{k=0}^{n}\frac{\Large\binom nk}{\Large\binom{2n-1}k} &=\sum_{k=0}^{n}\frac{n!}{k!(n-k)!}\cdot \frac{k!(2n-1-k)!}{(2n-1)!}\\ &=\frac{n!}{(2n-1)!}\cdot \color{green}{(n-1)!}\sum_{k=0}^{n}\frac{(2n-1-k)!}{\color{green}{(n-1)!}(n-k)!}\\[10pt] &=\frac{n!(n-1)!}{(2n-1)!}\sum_{k=0}^{n} {\binom {2n-1-k}{n-1}}\\[10pt] &={\binom{2n-1}n}^{-1}\sum_{r=0}^{n} \binom {n-1+r}{n-1}\qquad \small\text{(putting $r=n-k$)}\\[10pt] &={\binom{2n-1}n}^{-1}\binom{2n}{n}\\[10pt] &=\frac{(2n)^\underline{n}}{(2n-1)^\underline{n}} \color{gray}{=\frac{(2n)(2n-1)(2n-2)\cdots (n+1)}{\qquad\;\;\; (2n-1)(2n-2)\cdots (n+1)n}}\\[10pt] &=\frac{2n}{n}\\[10pt] &=2\qquad\blacksquare \end{align}$$

NB: Thanks for reading the answer above and for your upvotes! Please also see my other solution in a separate post below, which uses a different and possibly more direct approach.

Solution 2:

The identity $$\sum_{k=0}^n\frac{\binom nk}{\binom{2n-1}k}=2$$ holds for every positive integer $n$. The case $n=1$ is trivial. Here is a probabilistic proof for $n\ge2$.

Consider the following random experiment. An urn initially contains $n$ black balls and $n-1$ white balls. Balls are drawn one by one, without replacement, until a white ball is drawn. The random variable $X$ is the number of draws; its range of values is $\{1,2,\dots,n,n+1\}$. We will compute the expected value $E(X)$ in two different ways.

I. Clearly we have $$X=\sum_{k=0}^nX_k$$ where $$X_k=\begin{cases} 1\text{ if }X\gt k,\\ 0\text{ if }X\le k; \end{cases}$$ in other words, $X_k=1$ if there is no white ball in the first $k$ draws, meaning that a $(k+1)^{\text{st}}$ draw is needed. Thus we have $$E(X)=E(\sum_{k=0}^n X_k)=\sum_{k=0}^n E(X_k)=\sum_{k=0}^n P(X_k=1)=\sum_{k=0}^n\frac{\binom nk}{\binom{2n-1}k}.$$

II. Call the black balls $B_1,B_2,\dots,B_n$. Let $Y_i$ be the indicator variable which takes the value $1$ if the ball $B_i$ is drawn before any white ball is drawn, $0$ otherwise. Clearly the variable $X$ is equal to $1$ plus the number of black balls drawn, that is, $$X=1+\sum_{i=1}^nY_i$$ and so $$E(X)=1+\sum_{i=1}^nE(Y_i)=1+\sum_{i=1}^nP(Y_i=1)=1+\sum_{i=1}^n\frac1n=2.$$

More generally, for any integers $m,n\ge0$, the same argument (with $n$ black and $m$ white balls) shows that $$\sum_{k=0}^n\frac{\binom nk}{\binom{m+n}k}=1+\frac n{m+1}.$$

Solution 3:

It is easy to see that:

$$\sum\limits_{k=0}^1\frac{1\choose k}{1\choose k}= \frac{1\choose 0}{1\choose 0}+\frac{1\choose 1}{1\choose 1}=2$$

Now, if you can show that:

$$\sum_{k=0}^n \frac{\dbinom{n}{k}}{\dbinom{2n-1}{k}}=2\implies \sum_{k=0}^{n+1} \frac{\dbinom{n+1}{k}}{\dbinom{2n+1}{k}}=2$$

Then you have a proof by induction.

Solution 4:

I wouldn't usually post another answer, but the approach here is quite different so I hope this will be excused.

$$\begin{align} &\large\sum_{k=0}^n\frac{\Large\binom nk}{\Large\binom{2n-1}k}\\[10pt] &=\large\sum_{k=0}^n\frac{n^\underline{k}}{k!}\cdot \frac{k!}{(2n-1)^\underline{k}}\\[10pt] &=\large{\sum_{k=0}^n}\frac{n^\underline{k}}{(2n-1)^\underline{k}}\\[10pt] &=1+\frac n{2n-1}+\frac{n(n-1)}{(2n-1)(2n-2)}+\cdots+\frac{n(n-1)\cdots3\cdot 2\cdot 1}{(2n-1)(2n-2)\cdots (n+2)(n+1)n}\\[10pt] &=1+\frac n{2n-1}\left(1+\frac{n-1}{2n-2}\left(1+\cdots \left(1+\frac 3{n+2}\left(1+\frac 2{n+1}\color{blue}{\left(1+\frac 1n\right)} \right)\right)\right)\right)\\[10pt] &=1+\frac n{2n-1}\left(1+\frac{n-1}{2n-2}\left(1+\cdots \left(1+\frac 3{n+2}\color{blue}{\left(1+\frac 2{n}\right)} \right)\right)\right)\\[10pt] &=1+\frac n{2n-1}\left(1+\frac{n-1}{2n-2}\left(1+\cdots \color{blue}{\left(1+\frac 3n\right)}\right)\right)\\[10pt] &=\cdots\\[10pt] &=1+\frac n{2n-1}\color{blue}{\left(1+\frac{n-1}{n}\right)}\\[10pt] &=\color{blue}{1+\frac n{n}}\\[10pt] &=2\qquad\qquad \blacksquare\\[10pt] \end{align}$$