# Combinatorial identity with sum of binomial coefficients

How to attack this kinds of problem? I am hoping that there will some kind of shortcuts to calculate this.

$$\sum_{k=0}^{38\,204\,629\,939\,869} \frac{\binom{38\,204\,629\,939\,869}{k}}{\binom{76\,409\,259\,879\,737}{k}}\,.$$

EDIT:

As I see, the numerator is $n \choose k$ and the denominator is ${2n-1} \choose k$, where $n =38\,204\,629\,939\,869$. i.e $$\sum_{k=0}^n {\frac {n \choose k} {{2n-1} \choose k}} = 2.$$

• Have you noticed that this is $\sum\limits_{k=0}^n \dfrac{\binom nk}{\binom {2n-1}k}$ for $n=38204629939869$? – ajotatxe Nov 26 '14 at 8:01
• Yes, sometimes after a posted the problem. :) – arindam mitra Nov 26 '14 at 8:02
• To begin with, you can take the $\frac{n!}{(2n-1)!}$ outside the $\sum$. – barak manos Nov 26 '14 at 8:03
• Indeed, after trying some examples with wolfram alpha it seems that this is a general equality $\sum_{k=0}^n \frac{\binom{n}{k}}{\binom{2n-1}{k}} = 2$ – GenericNickname Nov 26 '14 at 8:09
• We have $\displaystyle \frac{\binom{n}{k}}{\binom{2n}{k}} - \frac{\binom{n}{k+1}}{\binom{2n}{k+1}} = \frac{1}{2}\frac{\binom{n}{k}}{\binom{2n-1}{k}}$, thus the sum telescopes to $2$ .. – r9m Dec 6 '14 at 10:33

(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.

• Thank you, @r9m! And other upvoters too. It was fun deriving the proof:) – hypergeometric Nov 26 '14 at 9:10
• @hypergeometric On your line two inside the sum , did you mean $(n-k)!$ instead of $(2n-1)!$ ? – Display name Nov 26 '14 at 13:47
• @Why - Yes that's right! Thanks for pointing it out. Have edited it accordingly. – hypergeometric Nov 26 '14 at 14:34

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

• Can you please explain why $P(Y_i = 1) = \frac{1}{n}$? – shardulc says Reinstate Monica Apr 4 '16 at 7:19
• For the event $Y_i=1$ the only balls that matter are $B_i$ and the $n-1$ white balls. Each of these $n$ balls has the same probability of being drawn first, namely $1/n.$ In particular, the probability that $B_i$ is drawn before any of the white balls is $1/n.$ – bof Apr 4 '16 at 7:38
• A beautiful proof! – 6005 Jul 23 '16 at 21:03

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.

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}

According to the Gosper's algorithm (Maxima command

AntiDifference(binomial(n,k)/binomial(2*n-1,k),k),

also implemented in Mathematica and Maple): $${\frac {n \choose k} {{2n-1} \choose k}} = {{\left((k+1)-2n\right){{n}\choose{k+1}}}\over{n{{2n-1}\choose{k+1 }}}} -{{\left(k-2n\right){{n}\choose{k}}}\over{n{{2n-1}\choose{k}}}}$$ and the sum telescopes : $$\sum_{k=0}^n{\frac{n \choose k}{{2n-1} \choose k}} = \sum_{k=0}^n{{\left((k+1)-2n\right){{n}\choose{k+1}}}\over{n{{2n-1}\choose{k+1}}}} -{{\left(k-2n\right){{n}\choose{k+1}}}\over{n{{2n-1}\choose{k}}}}= {{\left(1-n\right){{n}\choose{n+1}}}\over{n{{2n-1}\choose{n}}}}- {{\left(-2n\right){{n}\choose{0}}}\over{n{{2n-1}\choose{0}}}}=0-(-2)$$