# Alternating Sum and Difference of Binomial Coefficients for Given n

## Theorem

$\displaystyle \forall n \in \Z: \sum_{i \mathop = 0}^n \left({-1}\right)^i \binom n i = \delta_{n 0}$

where:

$\displaystyle \binom n i$ is a binomial coefficient
$\delta_{n 0}$ denotes the Kronecker delta.

### Corollary

$\displaystyle \sum_{i \mathop \in \Z} \left({-1}\right)^i \binom n i = \delta_{n 0}$

## Proof 1

We have by definition of vacuous summation that:

$\displaystyle \forall n \in \Z: n < 0: \sum_{i \mathop = 0}^n \binom n 1 = 0$

Then from Zero Choose Zero:

$\displaystyle \sum_{i \mathop = 0}^0 \binom 0 0 = 1$

For $n > 0$:

 $\displaystyle \sum_{i \mathop = 0}^n \left({-1}\right)^i \binom n i$ $=$ $\displaystyle \binom n 0 + \sum_{i \mathop = 1}^{n - 1} \left({-1}\right)^i \binom n i + \left({-1}\right)^n \binom n n$ $\displaystyle$ $=$ $\displaystyle \binom n 0 + \sum_{i \mathop = 1}^{n - 1} \left({-1}\right)^i \left({\binom {n - 1} {i - 1} + \binom {n - 1} i}\right) + \left({-1}\right)^n \binom n n$ Pascal's Rule $\displaystyle$ $=$ $\displaystyle \binom n 0 - \binom {n - 1} 0 + \left({-1}\right)^{n - 1} \binom {n - 1} {n - 1} + \left({-1}\right)^n \binom n n$ as the series telescopes

We note:

$\dbinom n 0 = \dbinom {n - 1} 0 = 1$

so:

$\dbinom n 0 - \dbinom {n - 1} 0 = 0$

$\left({-1}\right)^{n - 1} \dbinom {n - 1} {n - 1} = - \left({-1}\right)^n \dbinom n n = - \left({-1}\right)^n$

so:

$\left({-1}\right)^{n - 1} \dbinom {n - 1} {n - 1} + \left({-1}\right)^n \dbinom n n = 0$

Hence the result.

$\blacksquare$

## Proof 2

We have by definition of vacuous summation that:

$\displaystyle \forall n \in \Z: n < 0: \sum_{i \mathop = 0}^n \binom n 1 = 0$

Then from Zero Choose Zero:

$\displaystyle \sum_{i \mathop = 0}^0 \binom 0 0 = 1$

Let $n > 0$.

From the Binomial Theorem, we have that:

$\displaystyle \forall n \in \Z_{\ge 0}: \left({x + y}\right)^n = \sum_{i \mathop = 0}^n \binom n i x^{n - i} y^i$

Putting $x = 1, y = -1$, we get:

 $\displaystyle 0$ $=$ $\displaystyle \left({1 - 1}\right)^n$ which holds for all $n > 0$ $\displaystyle$ $=$ $\displaystyle \sum_{i \mathop = 0}^n \binom n i 1^{n - i} \left({-1}\right)^i$ $\displaystyle$ $=$ $\displaystyle \sum_{i \mathop = 0}^n \left({-1}\right)^i \binom n i$

$\blacksquare$

## Proof 3

We have by definition of vacuous summation that:

$\displaystyle \forall n \in \Z: n < 0: \sum_{i \mathop = 0}^n \binom n 1 = 0$

Then from Zero Choose Zero:

$\displaystyle \sum_{i \mathop = 0}^0 \binom 0 0 = 1$

Let $n > 0$.

The assertion can be expressed:

$\displaystyle \sum_{i \mathop \le n} \left({-1}\right)^i \binom n i = 0$ for all $n > 0$

as $\dbinom n i = 0$ when $i < 0$ by definition of binomial coefficient.

$\displaystyle \sum_{i \mathop \le n} \left({-1}\right)^i \binom r i = \left({-1}\right)^n \binom {r - 1} n$

Putting $r = n$ we have:

$\displaystyle \sum_{i \mathop \le n} \left({-1}\right)^i \binom n i = \left({-1}\right)^n \binom {n - 1} n$

As $n - 1 < n$ it follows from the definition of binomial coefficient that:

$\dbinom {n - 1} n = 0$

$\blacksquare$