Sum over k of n+k Choose 2 k by 2 k Choose k by -1^k over k+1
Jump to navigation
Jump to search
Theorem
Let $n \in \Z_{\ge 0}$.
Then:
- $\ds \sum_k \binom {n + k} {2 k} \binom {2 k} k \frac {\paren {-1}^k} {k + 1} = \sqbrk {n = 0}$
where:
- $\dbinom {n + k} {2 k}$ etc. are binomial coefficients
- $\sqbrk {n = 0}$ is Iverson's convention.
Proof 1
| \(\ds \) | \(\) | \(\ds \sum_k \binom {n + k} {2 k} \binom {2 k} k \frac {\left({-1}\right)^k} {k + 1}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_k \binom {n + k} k \binom n k \frac {\left({-1}\right)} {k + 1}\) | Product of $\dbinom r m$ with $\dbinom m k$ | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_k \binom {n + k} k \binom {n + 1} {k + 1} \frac {\left({-1}\right)^k} {n + 1}\) | Factors of Binomial Coefficient | |||||||||||
| \(\ds \) | \(=\) | \(\ds \frac 1 {n + 1} \sum_{k \mathop \ge 0} \binom {n + k} n \binom {n + 1} {k + 1} \left({-1}\right)^k\) | Symmetry Rule for Binomial Coefficients and rearranging | |||||||||||
| \(\ds \) | \(=\) | \(\ds -\frac 1 {n + 1} \sum_{k \mathop \ge 1} \binom {n - 1 + k} n \binom {n + 1} k \left({-1}\right)^k\) | Translation of Index Variable of Summation | |||||||||||
| \(\ds \) | \(=\) | \(\ds -\frac 1 {n + 1} \sum_{k \mathop \ge 0} \binom {n - 1 + k} n \binom {n + 1} k \left({-1}\right)^k + \frac 1 {n + 1} \binom {n - 1} n\) | separating out the case where $k = 0$ | |||||||||||
| \(\ds \) | \(=\) | \(\ds -\frac 1 {n + 1} \left({-1}\right)^{n + 1} \binom {n - 1} {-1} + \frac 1 {n + 1} \binom {n - 1} n\) | Sum over $k$ of $\dbinom r k \dbinom {s + k} n (-1)^{r - k}$ | |||||||||||
| \(\ds \) | \(=\) | \(\ds \frac 1 {n + 1} \binom {n - 1} n\) | as $\dbinom {n - 1} {-1} = 0$ | |||||||||||
| \(\ds \) | \(=\) | \(\ds \left[{n = 0}\right]\) | as $\dbinom {n - 1} n = 1 \iff n = 0$ |
$\blacksquare$
Proof 2
| \(\ds \) | \(\) | \(\ds \sum_k \binom {n + k} {2 k} \binom {2 k} k \frac {\left({-1}\right)^k} {k + 1}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_k \binom {n + k} k \binom n k \frac {\left({-1}\right)} {k + 1}\) | Product of $\dbinom r m$ with $\dbinom m k$ | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_k \binom {n + k} k \binom {n + 1} {k + 1} \frac {\left({-1}\right)^k} {n + 1}\) | Factors of Binomial Coefficient | |||||||||||
| \(\ds \) | \(=\) | \(\ds \frac 1 {n + 1} \sum_k \binom {- \left({n + 1}\right)} k \binom {n + 1} {k + 1}\) | Negated Upper Index of Binomial Coefficient | |||||||||||
| \(\ds \) | \(=\) | \(\ds \frac 1 {n + 1} \binom {n + 1 - \left({n + 1}\right)} {n + 1 - 1 + 0}\) | Sum over $k$ of $\dbinom r {m + k} \dbinom s {n + k}$ | |||||||||||
| \(\ds \) | \(=\) | \(\ds \frac 1 {n + 1} \binom 0 n\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \left[{n = 0}\right]\) | Definition of Binomial Coefficient |
$\blacksquare$