# Summation over a product of binomial coefficients

Question: I can't figure out why the following equality is true

$\sum_\limits{k=a-b-c}^{d} (-1)^k \binom{d}{k}\binom{k+b+c}{a} = (-1)^d \binom{b+c}{a-d}$

How can this be shown? (In the book it just says that the summation is accomplished by elementary means.)

Attempt: I tried setting $d=a-b-c+n$ so there will be $n$ terms in the summation. Using the briefer notation $x=a-b-c$, I get the LHS \begin{align} \sum_\limits{k=x}^{x+n} (-1)^k \binom{d}{k}\binom{k+b+c}{a} = & (-1)^{x}\binom{x+n}{x}\binom{a}{a} + (-1)^{x+1}\binom{x+n}{x+1}\binom{a+1}{a} + \\ & \dots + (-1)^{x+i}\binom{x+n}{x+i}\binom{a+i}{a} + \dots + \\ & (-1)^{x+n-1}\binom{x+n-1}{x+n}\binom{a+n-1}{a} \\ = & \sum_\limits{i=0}^{n-1} (-1)^{x+i} \binom{x+n}{x+i}\binom{a+i}{a} \end{align} and then I get stuck. I can't recognize it as being of the form of some of the normal products or summations of binomial coefficents.

I can verify the equation if I put in numbers or just make n=1 or n=2 or similar. So I thought of using induction to prove it. However with the $n$ in $\binom{x+n}{x+i}$ part, I am not sure that if it is possible. I thought of maybe using the relation $\binom{n}{k} k = n \binom{n-1}{k-1}$ but I can't see that making sense.

Since $b$ and $c$ always appear together, the solution can be simplified visually by putting $n=b+c$.
\begin{align} \sum_{k=a-b-c}^{d}(-1)^k {d\choose k}{k+b+c\choose a}&= \sum_{k=a-n}^{d}(-1)^k {d\choose k}{k+n\choose a} \qquad \qquad \quad \;\;\text{putting n=b+c}\\ &=\sum_{k=a-n}^{d}(-1)^k {d\choose k}{k+n\choose k+n-a}\\ &=\sum_{k=a-n}^{d}(-1)^{k+k+n-a} {d\choose k}{-a-1\choose k+n-a} \qquad \text{using upper negation}\\ &=(-1)^{n-a}\sum_{k=a-n}^{d} {d\choose d-k}{-a-1\choose k+n-a}\\ &=(-1)^{n-a}{d-a-1\choose d+n-a} \qquad \qquad \qquad \quad \text{using Vandermonde}\\ &=(-1)^{n-a+(d+n-a)}{n\choose d+n-a} \qquad \qquad \;\text{using upper negation}\\ &=(-1)^d {n\choose a-d}\\ &=(-1)^d {b+c\choose a-d}\qquad \blacksquare \end{align}
Consider the series \begin{align} S = \sum_{k=a-b-c}^{d} (-1)^k \binom{d}{k}\binom{k+b+c}{a} \end{align} The following is the reduction of this series. \begin{align} S &= \sum_{k=0}^{d - a + b + c} (-1)^{k+a - b - c} \binom{d}{k+a-b-c} \binom{k+a}{a} \\ &= (-1)^{a - b -c} \, \frac{d! (a-b-c)!}{(d-a+b+c)!} \, \sum_{k=0} \frac{(-1)^{k} (a+1)_{k} }{ k! \, (a-b-c+1)_{k} (d-a+b+c+1)_{-k}} \\ &= (-1)^{a - b -c} \, \frac{d! (a-b-c)!}{(d-a+b+c)!} \, \sum_{k=0} \frac{(a+1)_{k} (a-d-b-c)_{k}}{k! \, (a-b-c+1)_{k} } \\ &= (-1)^{a - b -c} \, \frac{d! (a-b-c)!}{(d-a+b+c)!} \, {}_{2}F_{1}(a+1, a-b-c-d; a-b-c+1; 1) \\ &= (-1)^{a - b -c} \, \frac{d! (a-b-c)!}{(d-a+b+c)!} \, \frac{ (a-b-c)! (a-b-c)! (d-a-1)!}{d! \, (-b-c-1)! (d-a+b+c)!} \\ &= (-1)^{d} \binom{b+c}{a-d}. \end{align} The term $(a)_{k}$ is called the Pochhammer symbol and ${}_{2}F_{1}$ is the hypergeometric function.