Sum of k Choose m up to n

From ProofWiki
Jump to: navigation, search


Theorem

Let $m, n \in \Z: m \ge 0, n \ge 0$.


Then:

$\displaystyle \sum_{k \mathop = 1}^n \binom k m = \binom {n + 1} {m + 1}$

where $\displaystyle \binom k m$ is a binomial coefficient.


Proof

Proof by induction:

For all $n \in \N$, let $\map P n$ be the proposition:

$\displaystyle \sum_{k \mathop = 0}^n \binom k m = \binom {n + 1} {m + 1}$


Basis for the Induction

$\map P 0$ says:

$\displaystyle \binom 0 m = \binom 1 {m + 1}$

When $m = 0$ we have by definition:

$\displaystyle \binom 0 0 = 1 = \binom 1 1$

When $m > 0$ we also have by definition:

$\displaystyle \binom 0 m = 0 = \binom 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:

$\displaystyle \sum_{k \mathop = 1}^r \binom k m = \binom {r + 1} {m + 1}$


Then we need to show:

$\displaystyle \sum_{k \mathop = 1}^{r + 1} \binom k m = \binom {r + 2} {m + 1}$


Induction Step

This is our induction step:

\(\displaystyle \sum_{k \mathop = 1}^{r+1} \binom k m\) \(=\) \(\displaystyle \sum_{k \mathop = 1}^r \binom k m + \binom {r + 1} m\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \binom {r + 1} {m + 1} + \binom {r + 1} m\) $\quad$ Induction Hypothesis $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \binom {r + 2} {m + 1}\) $\quad$ Pascal's Rule $\quad$

So $\map P r \implies \map P {r + 1}$ and the result follows by the Principle of Mathematical Induction.


Therefore:

$\displaystyle \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$


Alternative Proof

\(\displaystyle \sum_{k \mathop = 0}^n \binom k m\) \(=\) \(\displaystyle \sum_{0 \mathop \le m + k \mathop \le n} \binom {m + k} m\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{-m \mathop \le k \mathop < 0} \binom {m + k} m + \sum_{0 \mathop \le k \mathop \le n - m} \binom {m + k} m\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 0 + \sum_{0 \mathop \le k \mathop \le n - m} \binom {m + k} m\) $\quad$ as $\displaystyle \binom k m = 0$ for $k < 0, m \ge 0$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \binom {m + \left({n - m}\right) + 1} {n - m} = \binom {n + 1} {n - m}\) $\quad$ Sum of r+k Choose k up to n‎ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \binom {n + 1} {\paren {n + 1} - \paren {n - m} }\) $\quad$ Symmetry Rule for Binomial Coefficients‎ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \binom {n + 1} {m + 1}\) $\quad$ $\quad$

$\blacksquare$