Sum of Binomial Coefficients over Upper Index
(Redirected from Sum of k Choose m up to n)
Jump to navigation
Jump to search
Theorem
Let $m \in \Z$ be an integer such that $m \ge 0$.
Then:
\(\ds \sum_{j \mathop = 0}^n \binom j m\) | \(=\) | \(\ds \binom {n + 1} {m + 1}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dbinom 0 m + \dbinom 1 m + \dbinom 2 m + \cdots + \dbinom n m = \dbinom {n + 1} {m + 1}\) |
where $\dbinom j m$ denotes a binomial coefficient.
Proof 1
Proof by induction:
For all $n \in \N$, let $\map P n$ be the proposition:
- $\ds \sum_{k \mathop = 0}^n \binom k m = \binom {n + 1} {m + 1}$
Basis for the Induction
$\map P 0$ says:
- $\dbinom 0 m = \dbinom 1 {m + 1}$
When $m = 0$ we have by definition:
- $\dbinom 0 0 = 1 = \dbinom 1 1$
When $m > 0$ we also have by definition:
- $\dbinom 0 m = 0 = \dbinom 1 {m + 1}$
This is our basis for the induction.
Induction Hypothesis
Now we need to show that, if $\map P r$ is true, where $r \ge 0$, then it logically follows that $\map P {r + 1}$ is true.
So this is our induction hypothesis:
- $\ds \sum_{k \mathop = 0}^r \binom k m = \binom {r + 1} {m + 1}$
Then we need to show:
- $\ds \sum_{k \mathop = 0}^{r + 1} \binom k m = \binom {r + 2} {m + 1}$
Induction Step
This is our induction step:
\(\ds \sum_{k \mathop = 0}^{r + 1} \binom k m\) | \(=\) | \(\ds \sum_{k \mathop = 0}^r \binom k m + \binom {r + 1} m\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \binom {r + 1} {m + 1} + \binom {r + 1} m\) | Induction Hypothesis | |||||||||||
\(\ds \) | \(=\) | \(\ds \binom {r + 2} {m + 1}\) | Pascal's Rule |
So $\map P r \implies \map P {r + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
- $\ds \forall m, n \in \Z, m \ge 0, n \ge 0: \sum_{k \mathop = 0}^n \binom k m = \binom {n + 1} {m + 1}$
$\blacksquare$
Proof 2
\(\ds \sum_{0 \mathop \le j \mathop \le n} \binom j m\) | \(=\) | \(\ds \sum_{0 \mathop \le m + j \mathop \le n} \binom {m + j} m\) | Translation of Index Variable of Summation | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{-m \mathop \le j \mathop < 0} \binom {m + j} m + \sum_{0 \mathop \le j \mathop \le n - m} \binom {m + j} m\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 0 + \sum_{0 \mathop \le \mathop j \mathop \le n - m} \binom {m + j} m\) | Definition of Binomial Coefficient: negative lower index | |||||||||||
\(\ds \) | \(=\) | \(\ds \binom {m + \left({n - m}\right) + 1} {m + 1}\) | Rising Sum of Binomial Coefficients | |||||||||||
\(\ds \) | \(=\) | \(\ds \binom {n + 1} {m + 1}\) |
$\blacksquare$
Sources
- 1992: Larry C. Andrews: Special Functions of Mathematics for Engineers (2nd ed.) ... (previous) ... (next): $\S 1.2.4$: Factorials and binomial coefficients: $1.34$
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: $\text{E} \ (11)$