# Alternating Sum and Difference of r Choose k up to n

## 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$