2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ As an alternative, both sides count the number of solutions to the equation $$ n_1+n_2+\ldots+n_a=b+1 $$ in positive integers. $\endgroup$ May 27, 2020 at 5:41
  • $\begingroup$ And the identity holds for all $a\ge1$, $b\ge-1$. $\endgroup$ May 27, 2020 at 6:21
  • $\begingroup$ But the combinatorial proof is valid only for $b\ge0$. $\endgroup$ May 27, 2020 at 8:07

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .