17
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Have you noticed that this is $\sum\limits_{k=0}^n \dfrac{\binom nk}{\binom {2n-1}k}$ for $n=38204629939869$? $\endgroup$ – ajotatxe Nov 26 '14 at 8:01
  • $\begingroup$ Yes, sometimes after a posted the problem. :) $\endgroup$ – arindam mitra Nov 26 '14 at 8:02
  • 2
    $\begingroup$ To begin with, you can take the $\frac{n!}{(2n-1)!}$ outside the $\sum$. $\endgroup$ – barak manos Nov 26 '14 at 8:03
  • $\begingroup$ 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$ $\endgroup$ – GenericNickname Nov 26 '14 at 8:09
  • $\begingroup$ 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$ .. $\endgroup$ – r9m Dec 6 '14 at 10:33
23
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ Can you please explain why $P(Y_i = 1) = \frac{1}{n}$? $\endgroup$ – shardulc says Reinstate Monica Apr 4 '16 at 7:19
  • 1
    $\begingroup$ 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.$ $\endgroup$ – bof Apr 4 '16 at 7:38
  • $\begingroup$ A beautiful proof! $\endgroup$ – 6005 Jul 23 '16 at 21:03
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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) $$

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