Sum over k of n+k Choose 2 k by 2 k Choose k by -1^k over k+1/Proof 2
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 \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$
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$