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})

    ReplyDelete