Sum over k of n Choose k by p^k by (1-p)^n-k by Absolute Value of k-np
Jump to navigation
Jump to search
Theorem
Let $n \in \Z_{\ge 0}$ be a non-negative integer.
Then:
- $\ds \sum_{k \mathop \in \Z} \dbinom n k p^k \paren {1 - p}^{n - k} \size {k - n p} = 2 \ceiling {n p} \dbinom n {\ceiling {n p} } p^{\ceiling {n p} } \paren {1 - p}^{n - 1 - \ceiling {n p} }$
Proof
Let $t_k = k \dbinom n k p^k \paren {1 - p}^{n + 1 - k}$.
Then:
- $t_k - t_{k + 1} = \dbinom n k p^k \paren {1 - p}^{n - k} \paren {k - n p}$
Thus the stated summation is:
- $\ds \sum_{k \mathop < \ceiling {n p} } \paren {t_{k + 1} - t_k} + \sum_{k \mathop \ge \ceiling {n p} } \paren {t_k - t_{k + 1} } = 2 t_{\ceiling {n p} }$
$\blacksquare$
Historical Note
This result was stated by Abraham de Moivre in his $1730$ work Miscellanea Analytica for the case where $n p$ is an integer.
The general case was proved by Henri Poincaré in his Calcul des Probabilités of $1896$.
Sources
- 1730: A. de Moivre: Miscellanea Analytica
- 1896: H. Poincaré: Calcul des Probabilités
- 1991: Persi Diaconis and Sandy Zabell: Closed Form Summation for Classical Distributions: Variations on a Theme of De Moivre (Stat. Sci. Vol. 6: pp. 284 – 302) www.jstor.org/stable/2245429
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: Exercise $68$