Sum over k of n+k Choose m+2k by 2k Choose k by -1^k over k+1
Theorem
Let $m, n \in \Z_{\ge 0}$.
Then:
- $\ds \sum_k \binom {n + k} {m + 2 k} \binom {2 k} k \frac {\paren {-1}^k} {k + 1} = \binom {n - 1} {m - 1}$
where $\dbinom {n + k} {m + 2 k}$ and so on are binomial coefficients.
Proof 1
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$
Proof 2
Let:
- $\ds S := \sum_k \binom {n + k} {m + 2 k} \binom {2 k} k \frac {\paren {-1}^k} {k + 1}$
Then:
| \(\ds \binom {2 k + 1} {k + 1}\) | \(=\) | \(\ds \binom {2 k} k \frac {2 k + 1} {k + 1}\) | Factors of Binomial Coefficient | |||||||||||
| \(\ds \leadsto \ \ \) | \(\ds \binom {2 k} k\) | \(=\) | \(\ds \binom {2 k + 1} {k + 1} \frac {k + 1} {2 k + 1}\) | |||||||||||
| \(\ds \) | \(=\) | \(\ds \binom {2 k + 1} k \frac {k + 1} {2 k + 1}\) | Symmetry Rule for Binomial Coefficients |
Also:
| \(\ds \binom {n + k} {m + 2 k}\) | \(=\) | \(\ds \paren {-1}^{n + k - m - 2 k} \binom {-\paren {m + 2 k + 1} } {n + k - m - 2 k}\) | Moving Top Index to Bottom in Binomial Coefficient | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {-1}^{n - m - k} \binom {- m - 2 k - 1} {n - m - k}\) |
Reassembling $S$:
- $\ds S = \sum_k \binom {1 + 2 k} k \binom {-m - 2 k - 1} {n - m - k} \frac {\paren {-1}^{n - m} } {1 + 2 k}$
- $\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \paren {n - k} } {n - k} \frac r {r - t k} = \binom {r + s - t n} n$
Making the following substitutions:
- $r \gets 1$
- $t \gets -2$
- $n \gets n - m$
we obtain:
| \(\ds s + 2 \paren {n - m - k}\) | \(=\) | \(\ds - m - 2 k - 1\) | ||||||||||||
| \(\ds \leadsto \ \ \) | \(\ds s\) | \(=\) | \(\ds m - 2 n - 1\) | |||||||||||
| \(\ds \leadsto \ \ \) | \(\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \paren {n - k} } {n - k} \frac r {r - t k}\) | \(=\) | \(\ds \sum_{k \mathop \ge 0} \binom {1 + 2 k} k \binom {- m - 2 k - 1} {n - m - k} \frac 1 {1 + 2 k}\) |
Thus:
| \(\ds S\) | \(=\) | \(\ds \paren {-1}^{n - m} \sum_k \binom {1 + 2 k} k \binom {- m - 2 k - 1} {n - m - k} \frac 1 {1 + 2 k}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {-1}^{n - m} \binom {1 + \paren {m - 2 n - 1} + 2 \paren {n - m} } {n - m}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {-1}^{n - m} \binom {- m} {n - m}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \binom {n - 1} {n - m}\) | Negated Upper Index of Binomial Coefficient | |||||||||||
| \(\ds \) | \(=\) | \(\ds \binom {n - 1} {m - 1}\) | Symmetry Rule for Binomial Coefficients |
$\blacksquare$