2

(Feller Volume 1, 2.12.12) Prove that for integers $0 < a <b$ $$\sum_{k=1}^a (-1)^{a-k} {a \choose k} {b+k \choose b+1} = {b \choose a-1}.$$

Hint: Using (12.4) show that (12.11) is a special case of (12.9).

(12.4) For any $a>0$, $${-a \choose k} = (-1)^k {a+k-1 \choose k}.$$ (12.9) For any positive integers $a, b, n,$ $$\sum_{v=0}^n {a \choose v}{b \choose n-v} = {a+b \choose n}.$$ (12.11) $$\sum_{v=0}^n {n \choose v}^2 = {2n \choose n}.$$

I can show that (12.11) is a special case of (12.9) by letting $a = b= n$. I am not sure why the author suggests us to use (12.4). Also, how does this help us to prove the original question? The right side of (12.4) looks similar with $(-1)^{a-k}{a \choose k}$ in the summation, so I replace $k$ by $a-k$ in the right side of (12.4), but it doesn't look helpful. I really appreciate if you give some help.

Will Orrick
  • 18,220
shk910
  • 3,599

2 Answers2

1

An elementary one:

$$\sum_{k=1}^a (-1)^{a-k} {a \choose k} {b+k \choose b+1}=\sum_{k=1}^a(-1)^{a-k}{a \choose k} {b+k \choose k-1}$$

$$=\sum_{k=1}^a(-1)^{a-1}{a \choose k} {-b-2 \choose k-1}=(-1)^{a-1}\sum_{k=1}^a{a \choose a-k} {-b-2 \choose k-1}$$

Now use Vandermonde's identity to get:

$$=(-1)^{a-1}\binom{a-b-2}{a-1}=\binom{b}{a-1}$$

Which is the claim.

0

The Feller text has a typo here. The hint should read "show that (12.13) is a special case of (12.9)" rather than "show that (12.11) is a special case of (12.9)". The equation (12.13) mentioned here is the identity to be proved. Another minor issue is that (12.9) is stated for positive integers, but the statement you will actually need to use requires that one of the integers be negative. The necessary generalization of (12.9) is indeed true, and Feller has another exercise where you are asked to prove that.

Will Orrick
  • 18,220