next up previous contents
Next: Special Sequences of Integers Up: Selection and Binomial Coefficients Previous: Selections   Contents

Some more identities

Proposition 8.5.3  

$\displaystyle \binom{n}{k} = \binom{n}{n-k} \qquad n \in \mathbb{N}_0, k \in \mathbb{Z}
$

Proof. For: choosing a $ k$-subset is the same as choosing an $ n-k$-subset to reject. $ \qedsymbol$

Proposition 8.5.4  

$\displaystyle \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \qquad n \in \mathbb{N}_0, k \in \mathbb{Z}
$

Proof. This is trivial if $ n < 0$ or $ k \le 0$, so assume $ n \ge 0$ and $ k > 0$. Choose a special element in the $ n$-set. Any $ k$-subset will either contain this special element (there are $ \binom{n-1}{k-1}$ such) or not contain it (there are $ \binom{n-1}{k}$ such). $ \qedsymbol$

In fact

Proposition 8.5.5  

$\displaystyle \binom{x}{k} = \binom{x-1}{k-1} + \binom{x-1}{k} \qquad k \in \mathbb{Z}
$

Proof. Trivial if $ k < 0$, so let $ k \ge 0$. Both sides are polynomials of degree $ k$ and are equal on all elements of $ \mathbb{N}_0$ and so are equal as polynomials as a consequence of the Fundamental Theorem of Algebra. This is the ``polynomial argument''. $ \qedsymbol$

This can also be proved from the definition, if you want to.

Proposition 8.5.6  

$\displaystyle \binom{x}{m} \binom{m}{k} = \binom{x}{k} \binom{x-k}{m-k} \quad m,k \in \mathbb{Z}.
$

Proof. If $ k < 0$ or $ m < k$ then both sides are zero. Assume $ m \ge k \ge 0$. Assume $ x = n \in \mathbb{N}$ (the general case follows by the polynomial argument). This is ``choosing a $ k$-subset contained in an $ m$-subset of a $ n$-set''. $ \qedsymbol$

Proposition 8.5.7  

$\displaystyle \binom{x}{k} = \frac{x}{k} \binom{x-1}{k-1} \qquad k \in \mathbb{Z}\setminus
\{ 0 \}
$

Proof. We may assume $ x = n \in \mathbb{N}$ and $ k > 0$. This is ``choosing a $ k$-team and its captain''. $ \qedsymbol$

Proposition 8.5.8  

$\displaystyle \binom{n+1}{m+1} = \sum_{k=0}^n \binom{k}{m}, \qquad m,n \in \mathbb{N}_0
$

Proof. For

$\displaystyle \binom{n+1}{m+1} = \binom{n}{m} + \binom{n}{m+1}
= \binom{n}{m} + \binom{n-1}{m} + \binom{n-1}{m+1}
$

and so on. $ \qedsymbol$

A consequence of this is that $ \sum_{k=1}^n k^{\underline{m}}
= \frac{1}{m+1} (n+1)^{\underline{m+1}}$, which is obtained by multiplying the previous result by $ m!$. This can be used to sum $ \sum_{k=1}^n k^m$.

Proposition 8.5.9  

$\displaystyle \binom{r+s}{m+n} = \sum_k \binom{r}{m+k} \binom{s}{n-k} \qquad r,s,m,n \in \mathbb{Z}
$

Proof. We can replace $ n$ by $ m+n$ and $ k$ by $ m+k$ and so we may assume that $ m=0$. So we have to prove:

$\displaystyle \binom{r+s}{n} = \sum_k \binom{r}{k} \binom{s}{n-k} \qquad r,s,n \in \mathbb{Z}.
$

Take an $ (r+s)$-set and split it into an $ r$-set and an $ s$-set. Choosing an $ n$-subset amounts to choosing a $ k$-subset from the $ r$-set and an $ (n-k)$-subset from the $ s$-set for various $ k$. $ \qedsymbol$


next up previous contents
Next: Special Sequences of Integers Up: Selection and Binomial Coefficients Previous: Selections   Contents
root 2002-06-10