Generating Functions

A generating function is a (possibly infinite) polynomial whose coefficients correspond to terms in a sequence of numbers $a_n.$ Due to their ability to encode information about an integer sequence, generating functions are powerful tools that can be used for solving recurrence relations. Techniques such as partial fractions, polynomial multiplication, and derivatives can help solve the recurrence relations.

An ordinary generating function is one of the form $f(x) = \displaystyle\sum_{n=0}^{\infty}a_n x^n,$ which will be put to good use for the types of problems we are interested in.

How many ways are there to make a sum of $10,$ using exactly one element from each of the following two sets: $\{2, 3, 6, 7\}$ and $\{ 3, 4, 5, 8\}?$

---

Consider the two polynomials $x^2 + x^3 + x^6 + x^7$ and $x^3 + x^4 + x^5 + x^8$. Note that for the first polynomial, the coefficient of $x^n$ is the number of ways of making a sum of $n$ using one element from the first set, and similarly for the second polynomial. For example, the coefficient of $x^4$ in the second polynomial is $1$, and there is $1$ way of making a sum of $4$ using only one element from the second set.

Now consider the product of the polynomials:

$$\big(x^2 + x^3 + x^6 + x^7\big) \big(x^3 + x^4 + x^5 + x^8\big).$$

Before we expand out this product, let us consider what the coefficient of $x^n$ means in the polynomial product: it represents the number of ways of making a sum of $n$ taking exactly one number from each set. The expansion of the product is

$$\begin{aligned} \big(x^2 + x^3 + x^6 + x^7\big)\big(x^3 + x^4 + x^5 + x^8\big) = x^5+2 x^6+2 x^7+x^8+x^9+3 x^{10}+3 x^{11}+x^{12}+x^{14}+x^{15}. \end{aligned}$$

Note that the coefficient of $x^n$ is $0$ for $n > 15$, since we cannot make a sum greater than $15$ using one from each set. The same goes for $n < 5$.

When $n = 10$, the coefficient is $3$. This means that there are $3$ ways of making $10$. If we expand the product fully using the distributive formula, we see that the three $x^{10}$ terms come from the products of $x^2$ with $x^8$, $x^6$ with $x^4$, and $x^7$ with $x^3$. $_\square$

The idea of attaching meaning to the coefficient of $x^n$ without attaching any meaning at all to $x$ is the idea of a generating function. A generating function encodes the numbers of objects using formal power series, which are polynomials with (possibly) infinitely many terms (of integer powers).

Note: The term formal is used because this is an algebraic concept, not an analytic concept.

In the above example, we could have simply counted the number of ways of making $10$ by inspection. However, generating functions are incredibly more useful if the polynomials may be expressed in a more compact form (such as using the geometric series sum), and then multiplication may lead to cancellation and an easier calculation.

Find the generating function for the face value of 1 die. Find the generating function for the sum of faces values of 2 dice.

---

For a standard six-sided die, there is exactly 1 way of rolling each of the numbers from 1 to 6. Hence, we can encode this as the power series $R_1(x) = x^1 + x^2 + x^3 + x^4 + x^5 + x^6$. The exponents represent the value rolled on the die, and the coefficients represent the number of ways this value can be attained.

For rolling 2 dice, we could likewise list out the possible sums, and arrive at

$$R_2 (x) = x^2 + 2x^3 + 3x^4 + 4x^5 + 5x^6 + 6x^7 + 5x^8 + 4x^9 + 3x^{10} + 2x^{11} + x^{12}.$$

A more direct method is to realize (from above) that $R_2(x) = [R_1(x) ]^2$, hence we can calculate it directly without having to count each individual term. $_\square$

How many solutions in non-negative integers does the equation $a + b + c = 20$ have?

---

First, we look at a more general question of finding the number of solutions in non-negative integers to the equation $a + b + c = n$. Since the value of $a$ can be any non-negative integer $0,1,2,3, \ldots, i , \ldots$ (see note below), we can represent this as the generating function

$$A(x) = 1 + x + x^2 + \cdots + x^i + \cdots .$$

We have the same generating function for the possible values of $b$ and $c$. So our generating function for the number of solutions is $A(x) \times B(x) \times C(x) = [A(x)]^3$. However, finding this product could be extremely tedious.

We instead transform $A(x)$ into the rational function $\frac{1}{1-x}$, which we recognize from the sum of a geometric progression. Thus, we are interested in $[A(x)]^3 = \frac{1}{(1-x)^3}$. This can be expanded using the negative binomial theorem, which gives

$$\frac{1}{(1-x)^3} = {2 \choose 2} + {3 \choose 2} x + { 4 \choose 2 } x^2 + \cdots + { i+2 \choose 2 } x^ i + \cdots.$$

Therefore, the answer when $n=20$ is given by ${ 22 \choose 2 }$. This agrees with what we know from the stars and bars method. $_\square$

Note: It might be confusing why we allow $a$ to be any non-negative integer, even those which are larger than $n$, which clearly would not lead to a solution. Consider what would happen if we let $a = n+1$ or $a = n+2$ or any larger integer: In the final product of polynomials, the exponents of these terms would be larger than $n,$ so they will not contribute to the term we want, which has exponent $n.$

The question below can be solved by stars and bars, but it is tedious. We can solve it using generating functions.

Try this too:

We begin by studying the problem of solving homogeneous linear recurrence relations using generating functions. In general, a recurrence relation for the numbers $\{c_i\}_{i=1}^{\infty}$ is a way of expressing $c_n$ in terms of $k$ previous terms in the sequence, for some positive integer $k.$ A homogeneous linear recurrence relation is a relation of the form $c_n + q_1c_{n-1} + q_2c_{n-2} + \cdots +q_kc_{n-k} = 0.$ It is linear because each term has only a single monomial of the form $c_i$ and it is homogeneous because the righthand side is 0. If the right-hand side was a non-zero function of $n,$ then it would be nonhomogeneous. To fully solve a recurrence relation, we require initial values for the first $k$ terms, where this $k$ is the same as the one in the definition.

Find $c_n$ explicitly where

$$c_n -3c_{n-2} - 2c_{n-3} = 0, \mbox{ for } n \geq 3$$

and $c_2 =12 , c_1=5, c_0 =5.$

---

Consider the generating function

$$c(x) = c_0 + c_1 x + c_2 x^2 + c_3 x^3 + \cdots.$$

Now, since we are given that $c_n - 3 c_{n-2} - 2 c_{n-3} = 0$, let's consider the function $2x^3 c(x) + 3 x^2 c(x) - c(x) :$

$$\begin{array} { r l l l r l l l l l } 2 x^3 c(x) & = & & & & + 2 c_0 x^3 & + 2c_1 x^4 & + \cdots \\ + 3 x^2 c(x) & = & & & 3 c_0 x^2 & + 3 c_1 x^3 & + 3c_2 x^4 & + \cdots \\ - c(x) & = & - c_0 & - c_1 x & - c_2 x^2 & - c_3 x^3 & - c_4 x^4 & - \cdots \\ \hline & = & - c_0 & -c_1 x & + (3c_0 - c_2) x^2 & + 0 & + 0 & + 0 \ldots \\ & = & -5 & -5x &+ 3x^2. &&& \\ \end{array}$$

Hence, we get $\big( 2x^3 + 3x^2 - 1 \big) c(x) = -5 - 5 x + 3 x^2 ,$ which gives

$$c(x) = \frac{ -5 -5x + 3x^2 } { 2x^3 + 3x^2 - 1 } = - \frac{3}{2x-1} + \frac{3}{x+1} - \frac{1}{(x+1)^2 }.$$

Thus, by the negative binomial theorem or Taylor series, we can expand each of these terms, to conclude that

$$c(x) = \sum_{n=0}^{\infty} \big[ 3 \times 2^n - (-1)^n (n - 2) \big] x^n.$$

Thus, $c_n = 3 \times 2^n - (-1)^n (n - 2)$. $_\square$

Let us generalize the above example. Suppose we have a sequence $c_0, c_1, c_2, \ldots$ of numbers that satisfy the recurrence relation $c_k + q_1 c_{k-1} + q_2c_{k-2}+ \cdots + q_dc_{k-d} = 0.$ Then the terms of the recurrence are the coefficients of a generating function given by some rational function $f(x) = p(x) /q(x).$ In particular,

$$f(x) = \sum\limits_{k=0}^{\infty} c_kx^k = \frac{m_0 + m_1x + m_2x^2 + \cdots+m_j}{1+q_1x + q_2x^2 + \cdots + q_dx^d},$$

where we have $j+1$ initial terms $c_0,c_1,\ldots ,c_k$ and the $m_i$'s are defined as

$$\begin{array}{l} m_0 = c_0\\ m_1 = c_1 + q_1c_0\\ m_2 = c_2 + q_1c_1 + q_2c_0. \end{array}$$

We can use this to solve for $c_k$ explicitly by finding the roots of the denominator and taking the partial fractions decomposition of the rational function. We can solve for the coefficient of $c_k$ by applying the negative binomial theorem to each term. As such, we can conclude as follows:

For a recurrence relation with form as described above, we define the characteristic polynomial of the recurrence to be

$$x^k + q_1x^{k-1} + \cdots + q_{x-1}x + q_k.$$

Suppose our characteristic polynomial has roots $\alpha_i$ with multiplicity $m_i$ for $i = 1,, \ldots, j.$ Then the general solution to the recurrence relation is

$$\small c_n = \left(a_{1,1} + a_{1,2}n + \cdots + a_{1,m_1}n^{m_1-1}\right)\alpha_1^n + \cdots + \left(a_{j,1} + a_{j,2}n + \cdots + a_{j,m_j}n^{m_j-1}\right)\alpha_j^n.$$

The constants $a_{1,1}, a_{1,2}, \ldots, a_{j,m_j}$ are chosen to satisfy the initial conditions.

Notice that the total number of these constants is $k,$ which is why we need $k$ initial values.

The change from a homogeneous to a non-homogeneous recurrence relation is that we allow the right-hand side of the equation to be a function of $n$ instead of $0.$ So our recurrence relation is

$$c_n + q_1c_{n-1} + q_2c_{n-2} + \cdots +q_kc_{n-k} = f(n).$$

Even with such a small change, the solutions become much more complicated.

Find $c_n,$ where

$$c_n -3c_{n-2} - 2c_{n-3} = 4n - 2, \mbox{ for } n \geq 3$$

and $c_2 = 12, c_1 = 5, c_0 = 5$.

---

Consider the generating function

$$c(x) = c_0 + c_1 x + c_2 x^2 + c_3 x^3 + \cdots.$$

Now, since we are given that $c_n - 3 c_{n-2} - 2 c_{n-3} = 4n-2$, let's consider the function $2x^3 c(x) + 3 x^2 c(x) - c(x):$

$$\begin{array} { r l l l r l l l l l } 2 x^3 c(x) & = & & & & + 2 c_0 x^3 & + 2c_1 x^4 & + &\cdots \\ + 3 x^2 c(x) & = & & & 3 c_0 x^2 & + 3 c_1 x^3 & + 3c_2 x^4 & + &\cdots \\ - c(x) & = & - c_0 & - c_1 x & - c_2 x^2 & - c_3 x^3 & - c_4 x^4 & - &\cdots \\ \hline & = & - 5 & -5 x & +3 x^2 & - 10 x^3 & -14 x^4 & - &\cdots \\ \end{array}$$

Hence, we get $( 2x^3 + 3x^2 - 1 ) c(x) = -7 + x + 9 x^2 + \frac{2}{1-x} - \frac{4}{(1-x)^2}$. This gives us

$$\begin{aligned} c(x) & = \frac{ -7 + x + 9 x^2 + \frac{2}{1-x} - \frac{4}{(1-x)^2} } { 2x^3 + 3x^2 - 1 } \\ & = \frac{101} { 18(1+x) } + \frac{ 65}{ 9 (1-2x) } - \frac{1}{3 (1+x)^2 } - \frac{5}{2 (1-x) } - \frac{1}{(1-x)^2 }. \end{aligned}$$

Thus, by the negative binomial theorem or Taylor series, we can expand each of these terms, to conclude that

$$\small c_n = \frac{101}{18} \times (-1)^n + \frac{65}{9} \times 2^n - \frac{1}{3} \times (n+1) \times (-1)^n - \frac{5}{2} \times 1^n - 1 \times (n+1) \times (1) ^ n. \ _\square$$

Note: The typical approach to solving such a problem is to observe that if $a_n$ and $b_n$ are sequences that satisfy the recurrence, then $d_n = a_n - b_n$ satisfies the recurrence $c_n + q_1c_{n-1} + q_2c_{n-2} + \cdots +q_kc_{n-k} = 0.$ Note that this is the homogeneous version of the given recurrence which is easily solved. Hence, we just need to find a particular instance $a_n$, and add it to the general form for $c_n$.

Because we are merely manipulating a theoretical construct, we can actually apply many function operations to the generating functions that we created. For example, we can multiply them together, or even integrate and differentiate them termwise!

Find a closed form for

$$c_n = \sum_{i=0}^n ( 2+i ) 2^{ n -i }.$$

---

This example is simple enough that we could brute force out the solution. However, in the spirit of this wiki, let's solve this using generating functions.

Define

$$c(x) = c_0 + c_1 x + c_2 x^2 + c_3 x^3 + \cdots.$$

First, notice that $c_n$ can be defined in the form of $\sum a_i \times b_{n-i}$, which is a convolution. This suggests that we should define the polynomials:

$$\begin{aligned} a(x) &= 2 + 3x + 4x^2 + \cdots + ( 2+i) x^i + \cdots \\ &= \frac{1}{ 1-x} + \frac{ 1}{ (1-x)^2} = \frac{ 2-x} { (1-x)^2 }, \\\\ b(x) &= 2^0 + 2^1 x + 2^2 x + \cdots + 2^i x^2 + \cdots \\ &= \frac{1}{1-2x}. \end{aligned}$$

Then, we have $c(x) = a(x) \times b(x)$. As such, by using the generating functions, we have

$$\begin{aligned} c(x) &= a(x) \times b(x)\\ & = \frac{ 2-x} { (1-x)^ 2 } \times \frac{1}{1-2x} \\ &= - \frac{3}{ 1-x} - \frac{1}{(1-x)^2 } + \frac{6}{ 1-2x}. \end{aligned}$$

Hence, $c_n = - 3 - (n +1) + 6 \times 2^n = 6 \times 2^n - n - 4$. $_\square$

When we have a generating function for a certain problem, we can manipulate it to solve other combinatorial problems.

Given some generating function $f(x) = a_0 + a_1x + a_2x^2 + \cdots$, we can shift its coefficients $m$ positions to the right by multiplying it with $x^m:$

$$x^mf(x) = a_0x^m + a_1x^{m+1} + a_2x^{m+2} + \cdots .$$

Using this technique of "shift method" gives us a clean solution to the following problem:

If you select exactly one element from $\{2, 3, 4, \dots \}$, how many ways are there to select a given number? Express your answer as a simplified generating function.

---

As per the problem in the introduction, we will get a generating function where each term $x^n$ for every value $n$ in the set has a coefficient of 1:

$$x^2 + x^3 + x^4 + \cdots .$$

This generating function is similar to the generating function in the introduction, except its coefficients have been shifted right by two spaces. Using this, we may express this generating function more succinctly as

$$x^2 \times \frac{1}{1-x} = \frac{x^2}{1-x}. \ _\square$$

Given some generating function $f(x) = a_0 + a_1x + a_2x^2 + \cdots$, we can scale its exponent by a factor of $m$ by composing it with the function $g(x) = x^m$:

$$f(x^m) = a_0 + a_1x^{m} + a_2x^{2m} + \cdots .$$

Here is an example of the scale method:

If you select exactly one element from the set of even numbers $\{0, 2, 4, \dots \}$, how many ways are there to select a given number?

Express your answer as a simplified generating function.

---

As per the problem in the introduction, we will get a generating function where each term $x^n$ for every even value $n$ has a coefficient of 1:

$$1 + x^2 + x^4 + \cdots .$$

This generating function is similar to the generating function in the introduction, except each exponent has been doubled. Using the scale method, we can get a simple expression for the generating function by using $\phi (x^2)$:

$$\phi (x^2) = \frac{1}{1-x^2}. \ _\square$$

1. Find $c_n$ explicitly, where $c_n - c_{n-1} - c_{n-2} = 0$ and $c_0 = 1, c_1 = 1.$
2. Find the general expression for $c_n$, where $c_n + 4c_{n-1} - 3c_{n-2} - 18c_{n-3} = n^2 - 3n + 5.$
3. Find the general expression for $c_n,$ where $c_n - c_{n-1}-c_{n-2} = 2\cdot 3^n.$
4. Find $c_n$ explicitly, where $c_n = c_{n-1}^2 \times c_{n-2}^3,$ $c_0 = 1, c_1 = 2.$ $($Hint: consider $d_n = \log c_n.)$
5. Show that $\displaystyle \sum_{k=0} ^ n { 2k \choose k } { 2 ( n-k) \choose n-k } = 4^n.$

Solution