Alternating Sum and Difference of r Choose k up to n/Proof 1
Jump to navigation
Jump to search
Theorem
- $\ds \sum_{k \mathop \le n} \paren {-1}^k \binom r k = \paren {-1}^n \binom {r - 1} n$
Proof
| \(\ds \sum_{k \mathop \le n} \paren {-1}^k \binom r k\) | \(=\) | \(\ds \sum_{k \mathop \le n} \binom {k - r - 1} k\) | Negated Upper Index of Binomial Coefficient | |||||||||||
| \(\ds \) | \(=\) | \(\ds \binom {-r + n} n\) | Sum of r+k Choose k up to n | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {-1}^n \binom {r - 1} n\) | Negated Upper Index 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: $(18)$