\documentclass[12 pt, letterpaper]{article}
\usepackage{amssymb}

\title{TJUSAMO Practice 12 - Generating Functions}
\author{PDiao06}
\date{\today}

\begin{document}

\maketitle

Generating functions are cool and are one of the most clever counting things
ever.

\section{What Are They?}

The generating function of a sequence $(a_n))_{n=0}^{\infty}$ is defined as:
$$f(x) = \sum_{n=0}^{\infty}a_n x^n$$

Where the $a_i$s are complex numbers.
Think of them as infinite polynomials that are really just clever data 
structures.  They allow you to somehow manipulate the infinite sequence of
non-closed form numbers in a closed form.  We can add them and multiply them
as polynomials and associativity, commutativity, lack of zero divisors, and 
multiplicative inverses(except when $a_0 = 0$), all hold. Be careful though, as
usual, things relating to infinity can cause trouble.  At least we don't have 
to worry about convergence, we never really evaluate at an $x$, we are more
interested in the symbolic organization of the coefficients.

\section{Some Examples}

Here are the most essential examples in contest math.

\begin{itemize}

\item \textbf{Geometric Sequence}
$$ \frac{a_0}{1-r*x} = a_0 + a_0*r*x + a_0*r^2*x^2 + \cdots$$

\item\textbf{Binomial Coefficients}
You guys all know the binomial theorem, but we can generalize to complex 
numbers. We define the generating function:
$$(1+x)^c = \sum{n=0}^{\infty}{c \choose n}x^n$$
Using this definition we can quickly show that:
$$(1+x)^c(1+x)^d = (1+x)^{c+d}$$  
Also, we can examine the gneerating funcion $f(x) = \frac{1}{(1-x)^{-m-1}}$, 
here $m$ is an integer.  We can compute the coefficient of $x^n$ to be:
$$(-1)^n{-m-1 \choose n} = {n + m \choose m}$$
Since all polynomials $p(x)$ can be expressed as a linear combination of 
polynomials of the form ${n + m \choose m}$, we can compute the generating 
function for the sequence of numbers $a_n = p(n)$.

\item\textbf{Linear Recursion}

Given a linear recursion $a_{n+k} = b_1a_{n+k-1} + b_2a_{n+k-2} + \cdots 
+ b_ka_n$ , we can find an easy formula using generating function.  Consider:
$$f(x)(1-b_1x - b_2x^2 - \cdots - b_kx^k)$$
All the coefficents of terms at least $x^n$ must cancel out due to the linear
recursion.  Thus this thing is going to equal some $p(x)$, where it has a degree
less than $n$.  Thus we can conclude that we can use partial fractions to split
it up into polynomials of the form we can compute (namely the geometric series).
This formula really is related to the roots of the polynomial 
$1-b_1x - b_2x^2 - \cdots - b_kx^k$ and can then be solved using linear algebra
on the first couple of initial terms.  This is often the easiest way to find it.

\item \textbf{Partitions}
Let $\pi(n)$ denote the number of unordered paritions of $n$.  Then we can 
assign $a_n = \pi(n)$ and find it's corresponding generating function $\Pi(x)$.
$$\Pi(x) = \prod_{k=1}^{\infty}(1 + x^k + x^{2k} + \cdots) = \prod_{k=1}^{\infty}\frac{1}{1-x^k}$$
\end{itemize}

\section{Problems}
\begin{enumerate}

\item Find an explicit formula for the Fibonacci Numbers.

\item (WOOT) Show that the number of partitions of n that have no number 
repeated equals the number of partitions of n that have only odd numbers.

\item (MOSP 2005) Compute the coefficient of $x^21$ in the expansion of:
$$(x + x^2 + x^3 + x^4 + x^5 + x^6)^6$$

\item (MOSP 2005) Let $n$ be a postivie integer, and let
$$f(x) = \sum_{k=0}^{n}{n \choose k}^2(1+x)^{2n-2k}(1-x)^{2k}$$
Show that the coefficient of $x^{2m-1}$ in $f(x)$ is 0 for all positive integers
$m$.

\item (MOSP 2005) Express 
$$\sum_{k=0}^{n}(-1)^n{n \choose k}^2$$
in closed form.

\end{enumerate}

\end{document}