Alternating Sum and Difference of r Choose k up to n

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $r \in \R, n \in \Z$.

Then:

$\displaystyle \sum_{k \mathop \le n} \paren {-1}^k \binom r k = \paren {-1}^n \binom {r - 1} n$


Proof 1

\(\displaystyle \sum_{k \mathop \le n} \paren {-1}^k \binom r k\) \(=\) \(\displaystyle \sum_{k \mathop \le n} \binom {k - r - 1} k\) Negated Upper Index of Binomial Coefficient
\(\displaystyle \) \(=\) \(\displaystyle \binom {-r + n} n\) Sum of r+k Choose k up to n
\(\displaystyle \) \(=\) \(\displaystyle \paren {-1}^n \binom {r - 1} n\) Negated Upper Index of Binomial Coefficient

$\blacksquare$


Proof 2

The proof proceeds by induction.

For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:

$\displaystyle \sum_{k \mathop \le n} \paren {-1}^k \binom r k = \paren {-1}^n \binom {r - 1} n$


$\map P 0$ is the case:

\(\displaystyle \sum_{k \mathop \le 0} \paren {-1}^k \binom r k\) \(=\) \(\displaystyle \paren {-1}^0 \binom r 0\)
\(\displaystyle \) \(=\) \(\displaystyle 1\) Binomial Coefficient with Zero
\(\displaystyle \) \(=\) \(\displaystyle \paren {-1}^n \binom {r - 1} 0\) Binomial Coefficient with Zero

Thus $\map P 0$ is seen to hold.


Basis for the Induction

$\map P 1$ is the case:

\(\displaystyle \sum_{k \mathop \le 1} \paren {-1}^k \binom r k\) \(=\) \(\displaystyle \paren {-1}^0 \binom r 0 + \paren {-1}^1 \binom r 1\)
\(\displaystyle \) \(=\) \(\displaystyle 1 - r\) Binomial Coefficient with Zero, Binomial Coefficient with One
\(\displaystyle \) \(=\) \(\displaystyle \paren {-1}^1 \binom {r - 1} 1\) Binomial Coefficient with One

Thus $\map P 1$ is seen to hold.


This is the basis for the induction.


Induction Hypothesis

Now it needs to be shown that, if $\map P m$ is true, where $m \ge 1$, then it logically follows that $\map P {m + 1}$ is true.


So this is the induction hypothesis:

$\displaystyle \sum_{k \mathop \le m} \paren {-1}^k \binom r k = \paren {-1}^m \binom {r - 1} m$


from which it is to be shown that:

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


Induction Step

This is the induction step:

\(\displaystyle \sum_{k \mathop \le m + 1} \paren {-1}^k \binom r k\) \(=\) \(\displaystyle \sum_{k \mathop \le m} \paren {-1}^k \binom r k + \paren {-1}^{m + 1} \binom r {m + 1}\) Definition of Summation
\(\displaystyle \) \(=\) \(\displaystyle \paren {-1}^m \binom {r - 1} m + \paren {-1}^{m + 1} \binom r {m + 1}\)
\(\displaystyle \) \(=\) \(\displaystyle \paren {-1}^{m + 1} \paren {\binom r {m + 1} - \binom {r - 1} m }\)
\(\displaystyle \) \(=\) \(\displaystyle \paren {-1}^{m + 1} \binom {r - 1} {m + 1}\) Pascal's Rule

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


Therefore:

$\forall n \in \Z_{\ge 0}: \displaystyle \sum_{k \mathop \le n} \paren {-1}^k \binom r k = \paren {-1}^n \binom {r - 1} n$