## Tuesday, February 14, 2006

### When In Doubt, Polynomialize! Topic: Generating Functions. Level: Olympiad.

Definition: A generating function is simply a polynomial (or a power series, since it is infinite) $\displaystyle P(x) = a_0+a_1x+a_2x^2+\cdots = \sum_{i=0}^{\infty} a_ix^i$ whose coefficients give the sequence $\displaystyle \{a_i\}_{i=0}^{\infty}$.

The following problem will describe an interesting use of generating functions.

--------------------

Problem: Given reals $A$ and $B$, find the closed form expression for a sequence satisfying the recurrence

$a_{n+1} = Aa_n+Ba_{n-1}$

for $n = 1,2,\ldots$ and $a_0 = 1$, $a_1 = A$.

Solution: Generating functions are in general useful tools for solving recurrences. It can get a bit ugly, but if you work through the algebra right, it comes out nicely.

First off, let $P(x) = a_0+a_1x+a_2x^2+\cdots$ be the generating function for the sequence.

Consider the following procedure:

Take the recurrence $a_{i+1} = Aa_i+Ba_{i-1}$ and multiply it by $x^i$. We now have $a_{i+1}x^i = Aa_ix^i+Ba_{i-1}x^i$. Sum these from $i = 1$ to infinity to get

$\displaystyle \sum_{i=1}^{\infty} a_{i+1}x^i = A\sum_{i=1}^{\infty} a_ix^i + B\sum_{i=1}^{\infty} a_{i-1}x^i$.

But notice that

$\displaystyle \sum_{i=1}^{\infty} a_{i+1}x^i = \frac{P(x)-a_0}{x}$, $\displaystyle A\sum_{i=1}^{\infty} a_ix^i = A(P(x)-a_0)$, and $\displaystyle B\sum_{i=1}^{\infty} a_{i-1}x^i = BxP(x)$.

Thus we have

$\frac{P(x)-a_0}{x} = A(P(x)-a_0)+BxP(x)$, or

$P(x) = \frac{a_0}{1-Ax-Bx^2}$.

This looks pretty nice, but how do we find the coefficients? Let $r$ and $s$ be the reciprocals of the roots of the quadratic $1-Ax-Bx^2 = 0$. We have $r+s = A$ and $rs = -B$ as well as $1-Ax-Bx^2 = (1-rx)(1-sx)$.

So $P(x) = \frac{a_0}{(1-rx)(1-sx)}$. Now set $a_0 = 1$ to simplify things (note that the result can easily be extended to any $a_0$ but it's just more convenient this way). Using the partial fraction decomposition, we obtain

$P(x) = \frac{1}{(1-rx)(1-sx)} = \frac{r}{(r-s)(1-rx)}-\frac{s}{(r-s)(1-sx)} = \frac{1}{r-s}\left(\frac{r}{1-rx}-\frac{s}{1-sx}\right)$.

Expanding using the sum of an infinite geometric series (ignore the restrictions on the ratio; it might diverge but as long as we don't actually evaluate $P(x)$ for any $x$ it's ok) to get

$P(x) = \frac{1}{r-s}(r+r^2x+r^3x^2+\cdots)-\frac{1}{r-s}(s+s^2x+s^3x^2+\cdots)$, or

$P(x) = \frac{1}{r-s}((r-s)+(r^2-s^2)x+(r^3-s^3)x^2+\cdots) = a_0+a_1x+a_2x^2+\cdots$

from which we can easily see that $a_n = \frac{1}{r-s}(r^{n+1}-s^{n+1})$. QED.

--------------------

Comment: This has some very nice results, including the famous Fibonacci Sequence, when $A = B = 1$. We have $r,s$ the reciprocals of the roots of $1-x-x^2 = 0$ which happen to be $\frac{1+\sqrt{5}}{2}$ and $\frac{1-\sqrt{5}}{2}$, giving the well-known closed form for that sequence.

--------------------

Practice Problem: Try your hand at the recurrence $a_{n+1} = a_n+a_{n-1}+a_{n-2}$ with $a_0 = a_1 = 1$.

#### 1 comment:

1. You could also use polynomial finite differences or whatev its called. For the practice problem it would be a cubic. Actually that problem is impossible since we don't know a_2. :D (or a_{-1})