Enumerative Methods in Combinatorics

Example 1

The Fibonacci Sequence has a formal generating functions
defined by:

Hence

Proof

Thus

Alternatively:

Now use decomposition:

where and are roots of
Thus:

and now substitute back to the original formal power series

Example 2

The vector space over of all infinite sequences s.t.
has dimension and is spanned by

where and satisfy

Example 3

Let be prime.
Then there exists a subset of size in with no in a line.

Proof

Define
Suppose for contradiction are in a line in
Then

but this is the Vandermonde matrix so some of are the same.