Sum over k of n+k Choose m+2k by 2k Choose k by -1^k over k+1/Proof 1

Theorem

$\ds \sum_k \binom {n + k} {m + 2 k} \binom {2 k} k \frac {\paren {-1}^k} {k + 1} = \binom {n - 1} {m - 1}$

Proof

From Sum over $k$ of $\dbinom {r - k} m \dbinom {s + k} n$:

$\ds \sum_{k \mathop = 0}^r \binom {r - k} m \binom {s + k} n = \binom {r + s + 1} {m + n + 1}$

Setting $r = n + k - 1$, $m = 2 k$, $s = 0$, $n = m - 1$ and using $j$ as the index variable, this gives us:

$\ds \sum_{j \mathop = 0}^{n + k - 1} \binom {n + k - 1 - j} {2 k} \binom j {m - 1} = \dbinom {n + k} {m + 2 k}$

This leads to:

$\ds \sum_k \binom {n + k} {m + 2 k} \binom {2 k} k \frac {\paren {-1}^k} {k + 1} = \sum_k \sum_{j \mathop = 0}^{n + k - 1} \binom {n + k - 1 - j} {2 k} \binom {2 k} k \binom j {m - 1} \frac {\paren {-1} } {k + 1}$

Note that the terms of the above are $0$ when $n \le j < n + k - 1$.

This means that $k \ge 1$.

So:

$0 \le n + k - 1 - j \le k - i < 2 k$

Thus the first binomial coefficient in the above will vanish.

The condition on the second summation can then be replaced by $0 \le j < n$.

After exchange of summation and application of Sum over $k$ of $\dbinom {n + k} {2 k} \dbinom {2 k} k \dfrac {-1^k} {k + 1}$ converts it into:

$\ds \sum_{0 \mathop \le j \mathop < n} \binom j {m - 1} \delta_{\paren {n \mathop - 1} \mathop j}$

where $\delta_{\paren {n \mathop - 1} \mathop j}$ denotes the Kronecker delta.

All terms are therefore $0$ except where $j = n - 1$.

Hence the result.

$\blacksquare$

Sources

• 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: Example $3$