Next: Special Sequences of Integers Up: Selection and Binomial Coefficients Previous: Selections   Contents

## Some more identities

Proposition 8.5.3

Proof. For: choosing a -subset is the same as choosing an -subset to reject.

Proposition 8.5.4

Proof. This is trivial if or , so assume and . Choose a special element in the -set. Any -subset will either contain this special element (there are such) or not contain it (there are such).

In fact

Proposition 8.5.5

Proof. Trivial if , so let . Both sides are polynomials of degree and are equal on all elements of and so are equal as polynomials as a consequence of the Fundamental Theorem of Algebra. This is the polynomial argument''.

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

Proposition 8.5.6

Proof. If or then both sides are zero. Assume . Assume (the general case follows by the polynomial argument). This is choosing a -subset contained in an -subset of a -set''.

Proposition 8.5.7

Proof. We may assume and . This is choosing a -team and its captain''.

Proposition 8.5.8

Proof. For

and so on.

A consequence of this is that , which is obtained by multiplying the previous result by . This can be used to sum .

Proposition 8.5.9

Proof. We can replace by and by and so we may assume that . So we have to prove:

Take an -set and split it into an -set and an -set. Choosing an -subset amounts to choosing a -subset from the -set and an -subset from the -set for various .

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