2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you! It makes sense to me to the point where you recognize that the series is the hypergeometric function. However, could you explain in a bit more details how the hypogeometric series is reduced after the second last equality? (Where you go from 2F1 to the fraction without a sum) Also I cannot figure out how to rewrite from the second last line to the last line. Do you have any hints? $\endgroup$ – Risen_Tinra Mar 20 '15 at 14:19

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.