Sum of Binomial Coefficient products

Question

I am trying to prove that

$$\sum\limits_{y=0}^d \frac{{2x \choose y} {2d-2x \choose d-y} }{2d \choose d} = x $$

So far, I have tried using induction on $d$ but I am having trouble using the inductive hypothesis since the $d$ appears in the summation term as well. Does anyone have a more intuitive way of tackling this problem?

Answer 1

I provide two answers and you may decide if they could be considered as intuitive. The first answer is a geometrically based combinatorial proof the second is based upon Egorychev's formal residual calculus for power series (and may also be considered intuitive if you like to play with generating functions).

• First answer using lattice pathes:

The number $\binom{n}{k}$ can be considered as the number of lattice pathes of length $n$ containing $k$ horizontal $(1,0)$-steps and $n-k$ vertical $(0,1)$-steps.

This is valid because there are $\binom{n}{k}$ choices to select $k$ steps in horizontal direction leaving the remaining $n-k$ steps for the vertical direction.

Let's apply this approach to the identity:

\begin{align*} \sum\limits_{y=0}^d\binom{2x}{y}\binom{2d-2x}{d-y}=\binom{2d}{d}\tag{1} \end{align*}

We consider lattice pathes starting at $(0,0)$ with length $2d$ containing $d$ $(1,0)$-steps and $d$ $(0,1)$-steps. These pathes are all within a square with sides of length $d$. The number of these pathes is $$\binom{2d}{d}$$ To interpret the left hand side of (1) we select an $x$ with $0\leq x\leq d$ and partition the $\binom{2d}{d}$ pathes as follows: For each path we consider the head of length $2x$, i.e. the first $2x$ steps of the path and the corresponding tail of length $2d-2x$. Now we partition the pathes according to the number $y$ of horizontal $(1,0)$ -steps in the head.

The number of sub-pathes (heads) with length $2x$ having $y$ $(1,0)$-steps is

$$\binom{2x}{y}$$

For each of these sub-pathes we can choose a sub-path of length $2d-2x$ (tail) with $d-y$ horizontal steps to get a complete path with length $2d$ from $(0,0)$ to $(d,d)$.

So, the number of all pathes from $(0,0)$ to $(d,d)$ with head of length $2x$ containing $y$ horizontal steps is

$$\binom{2x}{y}\binom{2d-2x}{d-y}$$

Since $y$ may vary between $0$ and $2x$ provided $d-y \geq 0$ we get $0 \leq y \leq d$ and

the number $\binom{2d}{d}$ of all pathes from $(0,0)$ to $(d,d)$ is according to this partition: $$\sum\limits_{y=0}^d\binom{2x}{y}\binom{2d-2x}{d-y}$$

And here's the

• Second answer using Egorychevs formal residual calculus for power series

This powerful technique is based upon Cauchys residue theorem and was introduced by G.P. Egorychev (Integral Representation and the Computation of Combinatorial Sums) to compute binomial identies.

\begin{align*} \sum_{y=0}^{d}&\binom{2x}{y}\binom{2d-2x}{d-y}\\ &=\sum_{y=0}^{\infty}\binom{2x}{y}\binom{2d-2x}{d-y}\tag{1}\\ &=\sum_{y=0}^{\infty}\mathop{res}_u\frac{(1+u)^{2x}}{u^{y+1}} \mathop{res}_w\frac{(1+w)^{2d-2x}}{w^{d-y+1}}\tag{2}\\ &=\mathop{res}_w\frac{(1+w)^{2d-2x}}{w^{d+1}}\sum_{y=0}^{\infty}w^y\mathop{res}_u\frac{(1+u)^{2x}}{u^{y+1}}\tag{3}\\ &=\mathop{res}_w\frac{(1+w)^{2d-2x}}{w^{d+1}}(1+w)^{2x}\tag{4}\\ &=\mathop{res}_w\frac{(1+w)^{2d}}{w^{d+1}}\\ &=\binom{2d}{d} \end{align*}

Comment:

• In (1) the limit is changed without affecting the sum, since only $0$ is added.

• In (2) the residual calculus of formal power series is applied for each binomial coefficient.

• In (3) there is some rearrangement to prepare the application of the substitution rule which is used in (4)

You may want to have a look at my answer to this question to read a small introductory note to this technique.

Answer 2

Consider \begin{align} S_{m} = \sum_{k=0}^{m} \binom{2x}{k} \binom{2m-2x}{m-k} \end{align} for which it can be seen as the following. \begin{align} S_{m} &= \sum_{k=0}^{m} \binom{2m-2x}{m} \frac{(-m)_{k}(-2x)_{k}}{k! (m-2x+1)_{k}} \\ &= \binom{2m-2x}{m} {}_{2}F_{1}(-m, -2x; m-2x+1; 1) \\ &= \binom{2m-2x}{m} \frac{(m-2x)! (2m)!}{(2m-2x)! m!} \\ &= \binom{2m}{m}. \end{align} From this it is seen that \begin{align} \sum_{k=0}^{m} \frac{\binom{2x}{k} \binom{2m-2x}{m-k}}{\binom{2m}{m}} = 1. \end{align}