Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag
Mathematics-Online course: Prepcourse Mathematics - Basics - Combinatorics

Identities for Binomial Coefficients

[previous page] [next page] [table of contents][page overview]
We have the following identities for binomial coefficients:

$ \bullet$ $ \displaystyle 2^n $ $ =$ $ \displaystyle \sum_{k=0}^n \binom{n}{k} $,
$ \bullet$ $ \displaystyle 0 $ $ =$ $ \displaystyle \sum_{k=0}^n \binom{n}{k} (-1)^k\,,\quad n \geq 1 $,
$ \bullet$ $ \displaystyle \binom{n}{k} $ $ =$ $ \displaystyle \sum\limits_{i=0}^k \binom{n-k-1+i}{i}\,,\quad k < n $,
$ \bullet$ $ \displaystyle \binom{n}{k} $ $ =$ $ \displaystyle \sum\limits_{i=0}^{n-k} \binom{k-1+i}{i}\,,\quad k > 0 $.

(Authors: Höllig/Hörner/Walter)
The first two identities follow directly from the binomial theorem,

$\displaystyle (a+b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k}b^k \,, $

choosing $ a=b=1$ and $ a=-b=1$ respectively.

The third identity follows by repeated application of the recursion formula:

$\displaystyle \binom{n}{k}$ $\displaystyle =$ $\displaystyle \binom{n-1}{k} + \binom{n-1}{k-1}$  
  $\displaystyle =$ $\displaystyle \binom{n-1}{k} + \binom{n-2}{k-1} + \binom{n-2}{k-2}$  
  $\displaystyle =$ $\displaystyle \ldots$  
  $\displaystyle =$ $\displaystyle \binom{n-1}{k} + \binom{n-2}{k-1} + \ldots + \binom{n-k-1}{0}$  
  $\displaystyle =$ $\displaystyle \sum\limits_{i=0}^k \binom{n-k-1+i}{i} \,.$  

Substituting $ (n-k) \leftrightarrow k$ in this equation, we obtain the fourth identity.

Alternatively, the last two identities can be verified using summation paths in Pascal's triangle as is illustrated in the figure.

\includegraphics[width=0.7\linewidth]{pic_pascal}

(Authors: Höllig/Hörner/Walter)
[previous page] [next page] [table of contents][page overview]
  automatically generated 10/23/2009