Alternating Sum and Difference of Binomial Coefficients for Given n

From ProofWiki
Jump to navigation Jump to search

Theorem

$\ds \forall n \in \Z: \sum_{i \mathop = 0}^n \paren {-1}^i \binom n i = \delta_{n 0}$

where:

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


Corollary

$\ds \sum_{i \mathop \in \Z} \paren {-1}^i \binom n i = \delta_{n 0}$


Proof 1

We have by definition of vacuous summation that:

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

Then from Zero Choose Zero:

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


For $n > 0$:

\(\ds \sum_{i \mathop = 0}^n \paren{-1}^i \binom n i\) \(=\) \(\ds \binom n 0 + \sum_{i \mathop = 1}^{n - 1} \paren{-1}^i \binom n i + \paren{-1}^n \binom n n\)
\(\ds \) \(=\) \(\ds \binom n 0 + \sum_{i \mathop = 1}^{n - 1} \paren{-1}^i \paren{\binom {n - 1} {i - 1} + \binom {n - 1} i} + \paren{-1}^n \binom n n\) Pascal's Rule
\(\ds \) \(=\) \(\ds \binom n 0 - \sum_{i \mathop = 1}^{n - 1} \paren{\paren{-1}^{i-1} \binom {n - 1} {i - 1} - \paren{-1}^i \binom {n - 1} i} + \paren{-1}^n \binom n n\)
\(\ds \) \(=\) \(\ds \binom n 0 - \paren{-1}^{1 - 1} \binom {n - 1} {1 - 1} + \paren{-1}^{n - 1} \binom {n - 1} {n - 1} + \paren{-1}^n \binom n n\) Telescoping Series/Example 1
\(\ds \) \(=\) \(\ds 1 - 1 + \paren{-1}^{n - 1} - \paren{-1}^{n - 1}\) Binomial Coefficient with Zero, Binomial Coefficient with Self
\(\ds \) \(=\) \(\ds 0\)

Hence the result.

$\blacksquare$


Proof 2

We have by definition of vacuous summation that:

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

Then from Zero Choose Zero:

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


Let $n > 0$.

From the Binomial Theorem, we have that:

$\ds \forall n \in \Z_{\ge 0}: \paren {x + y}^n = \sum_{i \mathop = 0}^n \binom n i x^{n - i} y^i$


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

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

$\blacksquare$


Proof 3

We have by definition of vacuous summation that:

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

Then from Zero Choose Zero:

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


Let $n > 0$.

The assertion can be expressed:

$\ds \sum_{i \mathop \le n} \paren {-1}^i \binom n i = 0$ for all $n > 0$

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


From Alternating Sum and Difference of r Choose k up to n we have:

$\ds \sum_{i \mathop \le n} \paren {-1}^i \binom r i = \paren {-1}^n \binom {r - 1} n$

Putting $r = n$ we have:

$\ds \sum_{i \mathop \le n} \paren {-1}^i \binom n i = \paren {-1}^n \binom {n - 1} n$

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

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

$\blacksquare$


Sources