Generating Function

I just got asked a question that could be solved by generating function, while I was not familiar with it. So I did some research and found out that generating function is a powerful tool in combinatorics and probability theory. Below are some notes that I jotted after reading openmathbooks.org.

A generating function is a formal power series whose coefficients correspond to a sequence of numbers. It is often used to encode sequences and to manipulate them algebraically. The idea is to represent a infinite sequence with a single function. Let say we have a sequence,

$$1, 2, 3, 4, \ldots$$

We can represent it with a infinite series:

$$f(x) = 1 + 2x + 3x^2 + 4x^3 + \ldots,$$

where $|x| \leq 1$ is a variable, this called the generating series of the sequence. If the series converges, i,e,

$$g(x) = 1 + 1 + 1 + 1 + \ldots = \frac{1}{1-x},$$

such a function is called a generating function. The coefficients of the series are the terms of the sequence, and the variable $x$ encodes the position of the term in the sequence.

Examples

We can make use of the know generating functions to find the generating function of other sequences. Below are some examples:

Switch $x \to -x$ in the series, we get:

$$\frac{1}{1 + x} = 1 - x + x^2 - x^3 + \ldots \quad \text{which generates} \quad 1, -1, 1, -1, \ldots.$$

If $x \to 3x$,

$$\frac{1}{1 - 3x} = 1 + 3x + 9x^2 + 27x^3 + \ldots \quad \text{which generates} \quad 1, 3, 9, 27, \ldots.$$

What about a sequence like $2, 4, 10, 28, \ldots$? It is just like

$$(1 + 0) + (1 + 3)x + (1 + 9)x^2 + (1 + 27)x^3 + \ldots = \frac{1}{1 - 3x} + \frac{1}{1 - x}.$$

If we replace $x$ with $x^2$ in the series of odd number, we get:

$$\frac{1}{1 - x^2} = 1 + x^2 + x^4 + x^6 + \ldots \quad \text{which generates} \quad 1, 0, 1, 0, 1, \ldots.$$

Similarly,

$$\frac{1}{1 - x} - \frac{1}{1 - x^2} = x + x^3 + x^5 + x^7 + \ldots \quad \text{which generates} \quad 0, 1, 0, 1, 0, \ldots.$$

We can also take the derivative of the generating function,

$$\frac{d}{dx} \left( \frac{1}{1 - x} \right) = \frac{1}{(1 - x)^2} = 1 + 2x + 3x^2 + 4x^3 + \ldots \quad \text{which generates} \quad 1, 2, 3, 4, \ldots.$$

What if we are interest as the sequence of the odd number? Assume its generating function as $A$

$$\begin{align*} A &= 1 + 3x + 5x^2 + 7x^3 + \ldots \\ xA &= 1x + 3x^2 + 5x^3 + \ldots \\ (1 - x)A &= 1 + 2x + 2x^2 + 2x^3 + \ldots \\ &= 1 + \frac{2x}{1 - x} \\ \implies A &= \frac{1}{1 - x} + \frac{2x}{(1 - x) ^ 2} \\ \end{align*}$$

Recurrence Relations

Generating functions can also be used to solve recurrence relations. For example, consider the Fibonacci sequence:

$$F_i = F_{i-1} + F_{i-2}, \quad F_0 = 1, \quad F_1 = 1.$$

The generating function for the Fibonacci sequence can be derived as follows:

TBC.