Sum over k of m Choose k by k minus m over 2
Jump to navigation
Jump to search
Theorem
- $\ds \sum_{k \mathop = 0}^n \binom m k \paren {k - \dfrac m 2} = -\dfrac m 2 \binom {m - 1} n$
where $\dbinom m k$ etc. are binomial coefficients.
Proof
\(\ds \sum_{k \mathop = 0}^n \binom m k \paren {k - \dfrac m 2}\) | \(=\) | \(\ds \sum_{k \mathop = 0}^n k \binom m k - \dfrac m 2 \sum_{k \mathop = 0}^n \binom m k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop = 0}^n m \binom {m - 1} {k - 1} - \dfrac m 2 \sum_{k \mathop = 0}^n \binom m k\) | Factors of Binomial Coefficient | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac m 2 \sum_{k \mathop = 0}^n \paren {2 \binom {m - 1} {k - 1} - \binom m k}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac m 2 \sum_{k \mathop = 0}^n \paren {2 \binom {m - 1} {k - 1} - \paren {\binom {m - 1} {k - 1} + \binom {m - 1} k} }\) | Pascal's Rule | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac m 2 \sum_{k \mathop = 0}^n \paren {\binom {m - 1} {k - 1} - \binom {m - 1} k}\) | simplifying | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac m 2 \paren {\binom {m - 1} {-1} - \binom {m - 1} n}\) | as the series telescopes | |||||||||||
\(\ds \) | \(=\) | \(\ds -\dfrac m 2 \binom {m - 1} n\) | Definition of Binomial Coefficient for negative lower index |
$\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: $(38)$