Generating functions

It's time for some math! No, wait, come back!

Here's the teaser:

We have two normal six-sided dice. We roll both of them, and sum the number of pips. There is a certain probability that we get a 2, or a 3, or a 4, and so on all the way to 12. What we want is a new pair of six-sided dice with the exact same probabilities as the normal dice, but with different numbers of pips on the faces. Each side must have a positive integer number of pips. Can you create such a pair of dice?

I would not pose this as a lone puzzle, because it is rather difficult, and requires a specialized trick. That specialized trick is called generating functions. A generating function is a function that is related to a sequence of numbers. For example, consider the following sequence:

1, 1, 1, 1, 1, 1, ...

The above sequence generates the following function:

1 + x + x² + x³ + x⁴ + x⁵ + ...

Here's a slightly more complicated sequence and its generating function

1, 2, 3, 4, 5, 6, ...
1 + 2x + 3x² + 4x³ + 5x⁴ + 6x⁵ + ...

Essentially, you turn the sequence into the coefficients of an infinite polynomial.

We could leave the generating function in the form of a polynomial, but there's often a simpler way to express it. For example, take the generating function of the sequence {1, 1, 1, 1, 1, ...} We can simplify it with a bit of math.

Let H be the generating function of {1, 1, 1, 1, ...}
H = 1 + x + x² + x³ + x⁴ + x⁵ + ...
H*x = x + x² + x³ + x⁴ + x⁵ + x⁶ + ...
H - H*x = 1
H*(1-x) = 1
H = 1/(1-x)

Thus the sequence {1, 1, 1, 1, 1, ...} generates the function 1/(1-x).

Let's try the same for the sequence {1, 2, 4, 8, 16, ...}

Let G be the generating function of the sequence {1, 2, 4, 8, 16, ...}
G = 1 + 2x + 4x² + 8x³ + 16x⁴ + ...
G*2x = 2x + 4x² + 8x³ + 16x⁴ + 32x⁵ + ...
G - G*2x = 1
G*(1-2x) = 1
G = 1/(1-2x)

Thus the sequence {1, 2, 4, 8, 16, ...} generates the function 1/(1-2x).

You may be thinking, "That's nice, but what does that do for me?" Honestly, not a whole lot. But here's one problem you can solve.

Find an expression for the nth term of the Fibonacci sequence. In the Fibonacci sequence, the first two terms are {1,1}, and each term thereafter is the sum of the previous two terms.

We should first try to find the generating function of the Fibonacci sequence.

Let F be the generating function of the Fibonacci sequence {1, 1, 2, 3, 5, 8, 13, 21, ...}
F = 1 + x + 2x² + 3x³ + 5x⁴ + 8x⁵ + 13x⁶ + ...
F*x = x + x² + 2x³ + 3x⁴ +5x⁵ + 8x⁶ + ...
F*x² = x² + x³ + 2x⁴ +3x⁵ + 5x⁶ + ...
1 + F*x + F*x² = 1 + x + 2x² + 3x³ + 5x⁴ + 8x⁵ + 13x⁶ + ...
1 + F*x + F*x² = F
F = 1/(1-x-x²)

Good, now we've got the generating function: 1/(1-x-x²). We can actually simplify this a bit further. But to do this, we'll need some irrational numbers, which I'll just call A, B, and C. [See footnote for the actual values]*

1/(1-x-x²) = A/(1-Bx) - A/(1-Cx)

If I'm able to express the generating function as the sum of two other functions, that means I can also express the sequence as the sum of two other sequences. Makes sense? If you recall, the sequence {1, 2, 4, 8, 16, ...} generates the function 1/(1-2x). Similarly, we can prove that the sequence {1, B, B², B³, B⁴, ...} generates the function 1/(1-Bx). The fibonacci sequence is the sum of the following two sequences:

{1, 1, 2, 3, 5, 8, 13, 21, ...} = A*{1, B, B², B³, B⁴, ...} - A*{1, C, C², C³, C⁴, ...}

Thus, the nth term of the Fibonacci sequence is A*(B^n-1 - C^n-1). This is called Binet's formula for the Fibonacci sequence. Pretty cool?

Now, there are lots of other ways to find Binet's formula, and some of them are easier than this. But next time, we'll try to solve the dice problem, which is extremely difficult by any other method.

See the next page

[This is one of the things I learned at math camp. Well, *I* thought it was fascinating. My regards to the professor.]

*A is sqrt(1/5). B is the golden ratio, or 1/2 + sqrt(5)/2. C is 1/2 - sqrt(5)/2.