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.