Sum over k of n+k Choose 2 k by 2 k Choose k by -1^k over k+1/Proof 1
Jump to navigation
Jump to search
Theorem
- $\ds \sum_k \binom {n + k} {2 k} \binom {2 k} k \frac {\paren {-1}^k} {k + 1} = \sqbrk {n = 0}$
Proof
\(\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$
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 $2$