# 8.3: Using Generating Functions to Solve Recursively-Defined Sequences

- Page ID
- 60112

At last, we are ready to apply the mechanics we’ve introduced in this chapter, to find an explicit formula for the \(n^{\text{th}}\) term of a recursively-defined sequence.

This method is probably most easily understood using examples.

Example \(\PageIndex{1}\)

Consider the recursively-defined sequence: \(a_0 = 2\), and for every \(n ≥ 1\), \(a_n = 3a_{n−1} − 1\). Find an explicit formula for an in terms of \(n\).

**Solution**

The generating function for this sequence is \(a(x) = \sum_{i=0}^{\infty} a_ix^i \).

Now, we are going to use the recursive relation. We know that \(a_n = 3a_{n−1} − 1\), or, by rearranging this, \(a_n - 3a_{n−1} = −1\). Thus, if we could get the coefficient of \(x^n\) to look like \(a_n −3a_{n−1}\), we could use the recursive relation to replace this by \(−1\). Right now, the coefficient of \(x^n\) is \(a_n\), and the only place \(a_{n−1}\) shows up is as the coefficient of \(x^{n−1}\). But if we multiply \(a(x)\) by \(x\), then \(a_{n−1}x^{n−1}\) becomes \(a_{n−1}x^n\), so if we also multiply by \(−3\), we get a coefficient of \(−3a_{n−1}\) for \(x^n\) in \(−3xa(x)\). Now add this to \(a(x)\). This may be easier to see as written below:

\( \begin{equation} \begin{split} a(x)&= a_0 &+ a_1x &+a_2x^2 &+... &+ a_mx^m &+ ...\\ −3xa(x)&= &−3a_0x &−3a_1x^2 &−... &−3a_{m-1}x^m &-... \\ \therefore (1 − 3x)a(x)&= a_0 &−x &−x^2 &−... &−x^m &−... \end{split} \end{equation} \)

We see that this gives

\((1 − 3x)a(x) = 3 − (1 + x + x^2 + x^3 + . . .)\),

and we know that

\(1 + x + x^2 + x^3 + . . . = \dfrac{1}{(1 − x)}\),

so \((1 − 3x)a(x) = 3 − \dfrac{1}{(1 − x)}\). Dividing through by \(1 − 3x\) gives

\(a(x) = \dfrac{3}{1 − 3x} - \dfrac{1}{(1 − x)(1 − 3x)} \)

Now it’s time to apply what we learned in the preceding sections of this chapter. The denominator is already factored, so we can immediately apply the method of partial fractions to the second fraction. If

\(\dfrac{-1}{(1 − x)(1 − 3x)} = \dfrac{A}{1 − x} + \dfrac{B}{1 − 3x} = \dfrac{A(1 − 3x) + B(1 − x)}{(1 − 3x)(1 − x)} \),

then \(A + B = −1\) and \(−3A − B = 0\), so \(B = −3A\), which gives \(−2A = −1\), so \(A = \dfrac{1}{2}\) and \(B = -\dfrac{3}{2}\). Thus,

\(a(x) = \dfrac{3}{1 − 3x} + \dfrac{\dfrac{1}{2}}{1-x} - \dfrac{\dfrac{3}{2}}{1-3x} = \dfrac{\dfrac{1}{2}}{1-x} + \dfrac{\dfrac{3}{2}}{1-3x} \)

The coefficient of \(x^n\) in the first of these terms is \(\dfrac{1}{2}\), while in the second term, the coefficient of \(x^n\) is \((\dfrac{3}{2})3^n\). Thus, \(a_n = \dfrac{1}{2} + (\dfrac{3}{2})3^n\). Since our generating function began with \(a_0x^0\), this formula applies for every \(n ≥ 0\).

When going through so much algebra, it’s easy to make a mistake somewhere along the way, so it’s wise to do some double-checking. For a recursively-defined sequence, if the formula you work out gives the correct answer for the first three or four terms of the sequence, then it’s very likely that you’ve done the calculations correctly. Let’s check the first three terms of this one. We know from our initial condition that \(a_0 = 2\), and our new formula gives

\(a_0 = \dfrac{1}{2} + (\dfrac{3}{2})3^0 = \dfrac{1}{2} + \dfrac{3}{2} = 2\)

Using the recursive relation, we should have \(a_1 = 3(2) − 1 = 5\), and our formula gives

\(a_1 = \dfrac{1}{2} + (\dfrac{3}{2})3^1 = \dfrac{1}{2} + \dfrac{9}{2} = 5\)

Finally, the recursive relation gives \(a_2 = 3(5) − 1 = 14\), while our formula gives

\(a_2 = \dfrac{1}{2} + (\dfrac{3}{2})3^2 = \dfrac{1}{2} + \dfrac{27}{2} = 14\)

You can see the benefit to having an explicit formula if you were asked to work out \(a_{100}\). Clearly, it’s much easier to determine \(\dfrac{1}{2} + (\dfrac{3}{2})3^{100}\) than to apply the recursive relation one hundred times.

Let’s look at one more example, where the recursive relation involves more than one previous term.

Example \(\PageIndex{2}\)

Consider the recursively-defined sequence: \(b_0 = 1\), \(b_1 = 0\), \(b_2 = 1\), and for every \(n ≥ 3\), \(b_n = b_{n−1} − 2b_{n−3}\). Find an explicit formula for \(b_n\) in terms of \(n\).

**Solution**

The generating function for this sequence is

\(b(x) = \sum_{i=0}^{\infty} b_ix^i\).

Again, we’ll use the recursive relation, which we rearrange as

\(b_n - b_{n−1} + 2b_{n−3} = 0\)

for every \(n ≥ 3\). We want to end up with a polynomial in which the coefficient of \(x^m\) looks like \(b_m − b_{m−1} + 2b_{m−3}\), so that we’ll be able to use the recursive relation to replace this by \(0\). In order to do this, we’ll take \(b(x)\) (to get the \(b_mx^m\) piece), minus \(xb(x)\) (to get the \(−b_{m−1}x^m\) piece), plus \(2x^3 b(x)\) (to get the \(+2b_{m−3}x^m\) piece).

The result looks like:

\( \begin{equation} \begin{split} b(x)&= b_0 &+ b_1x &+b_2x^2 &+b_3x^3 &+... &+ b_mx^m &+ ...\\ −xb(x)&= &−b_0x &−b_1x^2 &-b_2x^3 &−... &−b_{m-1}x^m &-... \\ +2x^3b(x)&= & & &+2b_0x^3 &+... &+ 2b_{m-3}x^m &+ ... \\ \therefore (1 − x + 2x^3)b(x)&= b_0 &+(b_1 − b_0)x &+(b_2 − b_1)x^2 &+0x^3 &+... &+0x^m &+... \end{split} \end{equation} \)

We see that this gives

\((1 − x + 2x^3)b(x) = 1 + (−1)x + 1x^2\)

Dividing through by \(1 − x + 2x^3\) gives

\(b(x) = \dfrac{1 − x + x^2}{1 − x + 2x^3}\).

If we want to be able to do anything with this, we need to factor the denominator. Although we don’t have a general method for factoring cubic polynomials, in this case it’s not hard to see that \(−1\) is a zero of the polynomial (because \(1 − (−1) + 2(−1)^3 = 0)\), and hence \(x + 1\) is a factor of the polynomial. You will not be expected to factor cubic polynomials yourself in this course, so we won’t review polynomial long division, but if you recall polynomial long division, you can use it to determine that

\(1 − x + 2x^3 = (1 + x)(2x^2 − 2x + 1)\).

In any case, you can multiply the right-hand side out to verify that it is true.

Now it’s time to use the factoring formula, with \(a = 2\), \(b = −2\), and \(c = 1\), to factor \(2x^2 − 2x + 1\). This gives

\(2x^2 − 2x + 1 = 1 \left( 1 - \dfrac{2+ \sqrt{4-8}}{2}x \right)\left( 1 - \dfrac{2- \sqrt{4-8}}{2}x \right) = (1 − (1 + i)x) (1 − (1 − i)x) \).

Having factored

\(1 − x + 2x^3 = (1 + x)(1 − (1 + i)x)(1 − (1 − i)x)\),

we now apply the method of partial fractions to split this up into three separate pieces.

If

\( \begin{equation} \begin{split} \dfrac{1 − x + x^2}{1 − x + 2x^3} &= \dfrac{A}{1 + x} + \dfrac{B}{1 − (1 + i)x} + \dfrac{C}{1 − (1 − i)x} \\ &= \dfrac{A(2x^2 − 2x + 1) + B(1 + x)(1 − (1 − i)x) + C(1 + x)(1 − (1 + i)x)}{1 − x + 2x^3} \end{split} \end{equation} \)

then this gives us three equations:

\(2A − B(1 − i) − C(1 + i) = 1\)

(from the coefficient of \(x^2\));

\(−2A + B(1 − (1 − i)) + C(1 − (1 + i)) = −1\)

(from the coefficient of \(x\)); and \(A + B + C = 1\) (from the constant term). The second of these simplifies to \(−2A + iB − iC = −1\).

The algebra can be done in different ways and gets a bit ugly, but these three equations can be solved, resulting in \(A = \dfrac{3}{5}\), \(B = \dfrac{(2 − i)}{10}\), \(C = \dfrac{(2 + i)}{10}\).

Thus,

\(\dfrac{1 − x + x^2}{1 − x + 2x^3} = \dfrac{\dfrac{3}{5}}{1 + x} + \dfrac{\dfrac{(2-i)}{10}}{1 − (1 + i)x} + \dfrac{\dfrac{(2+i)}{10}}{1 − (1 − i)x} \).

The coefficient of \(x^n\) in the first of these terms is \((\dfrac{3}{5})(−1)^n\); in the second, it is \((\dfrac{(2−i)}{10}))(1+ i)^n\), and in the third, it is \((\dfrac{(2 + i)}{10})(1 − i)^n\).

We conclude that for every \(n ≥ 0\), we have

\(b_n = \dfrac{3}{5} (-1)^n + \dfrac{2-i}{10}(1+i)^n + \dfrac{2+i}{10}(1-i)^n \).

It is somewhat surprising that these formulas involving complex numbers will always work out (when \(n\) is an integer) to be not only real numbers, but integers! Once again, we should check this formula for several values of \(n\) to ensure we haven’t made errors in our calculations along the way.

From the initial conditions, \(b_0 = 1\). Our formula gives

\(b_0 = \dfrac{3}{5} + \dfrac{(2 − i)}{10} + \dfrac{(2 + i)}{10} = 1\).

From the initial conditions, \(b_1 = 0\). Our formula gives

\(b_1 = -\dfrac{3}{5} + \dfrac{2 − i}{10} (1 + i) + \dfrac{2 + i}{10} (1 - i) = -\dfrac{3}{5} + \dfrac{(3 + i)}{10} + \dfrac{(3 - i)}{10} = 0\).

Finally, the initial conditions gave \(b_2 = 1\), and our formula gives

\(b_2 = \dfrac{3}{5} + \dfrac{2 − i}{10} (2i) + \dfrac{2 + i}{10} (2i) = \dfrac{3}{5} + \dfrac{(2i + 1)}{5} + \dfrac{(2i - 1)}{5} = 1\).

We could continue, but this is sufficient verification to inspire reasonable confidence.

We now have a general method that we can apply to solve normal linear recursive relations:

## Method:

1) Rearrange the recurrence relation into the form

\[h_n − a_1h_{n−1} − a_2h_{n−2} − . . . − a_kh_{n−k} = f(n)\]

for some function \(f(n)\). Let

\[a(x) = 1 − a_1x − a_2x^2 − . . . − a_kx^k\]

2) Define the generating function

\[h(x) = h_0 + h_1x + h_2x^2 + . . . .\]

3) Find a linear combination of the generating function so that the coefficient of \(x^m\) is \(f(m)\) for every m greater than or equal to some \(i ≥ k\):

\[ \begin{equation} \begin{split} h(x)&= h_0 &+ h_1x &+h_2x^2 &+h_3x^3 &+... &+ h_ix^i &+ ...\\ −a_1xh(x)&= &−a_1h_0x &−a_1h_1x^2 &-a_1h_2x^3 &−... &−a_1h_{i-1}x^i &-... \\ −a_2x^2h(x)&= & &−a_2h_0x^2 &−a_2h_1x^3 &+... &−a_2h_{i-2}x^i &+ ... \\ . & & & & & & . & \\ . & & & & & & . & \\ . & & & & & & . & \\ −a_kx^kh(x)&= & & & & &−a_kh_{i−k}x^i &+ ... \\ \therefore a(x)h(x)&= h_0 &+(h_1 − a_1h_0)x &+(h_2 − a_1h_1 − a_2h_0)x^2 &+... &... &+f(i)x^i &+... \end{split} \end{equation} \]

So

\[h(x) = \dfrac{h_0 + (h_1 − a_1h_0)x + . . . + (h_{i−1} − a_1h_{i−2} + . . . + a_{k−1}h_{i−k})x^{i−1} + \sum_{n=i}^{\infty} f(n)x^n}{a(x)} \]

4) Factor \(a(x)\) (remember that you can use complex roots), and find a closed form for

\[\sum_{n=i}^{\infty} f(n)x^n \]

5) Use partial fractions to get expressions that we can expand using the generalised binomial theorem.

6) Make variable substitutions if necessary to get forms that look like

\[\dfrac{A}{(1 + y)^n}\]

7) Use the generalised binomial theorem to find \(h_n\), the coefficient of \(x^n\) in \(h(x)\).

Exercise \(\PageIndex{1}\)

For each of the following recursively-defined sequences, use the method of generating functions to find an explicit formula for the \(n^{\text{th}}\) term of the sequence.

- \(c_0 = 2\), \(c_1 = 0\), \(c_n = c_{n−1} + 2c_{n−2}\) for every \(n ≥ 2\).
- \(d_0 = 0\), \(d_1 = 1\), \(d_n = 2d_{n−2} + 1\) for every \(n ≥ 2\).
- \(e_0 = 2\), \(e_n = 3e_{n−1} − 2\) for every \(n ≥ 1\).
- \(f_0 = 1\), \(f_1 = 3\), and \(f_n = 4(f_{n−1} − f_{n−2})\) for every \(n ≥ 2\).
- \(g_0 = 2\), \(g_1 = 0\), and \(g_n = 2g_{n−1} − 2g_{n−2}\) for every \(n ≥ 2\).
- \(h_0 = \dfrac{1}{2}\) and \(h_n = 3h_{n−1} − \dfrac{1}{2}\) for every \(n ≥ 1\).
- \(i_0 = i_1 = 2\), \(i_2 = 0\), and \(i_n = 3i_{n−1} − 3i_{n−2} + i_{n−3}\) for every \(n ≥ 3\).
- \(j_0 = −1\), \(j_1 = 0\), and \(j_n = 2j_{n−1} + 3j_{n−2}\) for every \(n ≥ 2\).
- \( k_0 = 10\) and \(k_n = 11k_{n−1} − 10\) for every \(n ≥ 1\).

Exercise \(\PageIndex{2}\)

1) Let \(p_n\) denote the number of ways to build a pipe \(n\) units long, using segments that are either plastic or metal, and (for each material) come in lengths of \(1\) unit or \(2\) units. For example, \(p_1 = 2\) since we can use a \(1\)-unit segment that is either plastic or metal, and \(p_2 = 6\) since we can use either type of \(2\)-unit segment, or any of the \(22\) possible ordered choices of \(2\) segments each having a length of \(1\) unit. Define \(p_0 = 1\).

Determine a recurrence relation for \(p_n\). Give a combinatorial proof that your recurrence relation does solve this counting problem. Use your recurrence relation and the method of generating functions to find a formula for \(p_n\).

Hint: Your final answer should be

\(p_n = \dfrac{1}{2 \sqrt{3}} (1 + \sqrt{3})^{n+1} − \dfrac{1}{2 \sqrt{3}} (1 - \sqrt{3})^{n+1}\)

for every \(n ≥ 0\).]

2) Let \(s_n\) denote the number of lists of any length that have the fixed sum of \(n\), and whose entries come from \(\{1, 2, 3\}\). For example, \(s_2 = 2\) because \((1, 1)\) and \((2)\) are the only such lists; and \(s_4 = 7\) because the lists are \((3, 1)\), \((1, 3)\), \((2, 2)\), \((2, 1, 1)\), \((1, 2, 1)\), \((1, 1, 2)\), and \((1, 1, 1, 1)\). Define \(s_0 = 1\).

Determine \(s_1\), \(s_3\), and \(s_5\) by finding all possible lists. Give a combinatorial proof that \(s_n = s_{n−1} + s_{n−2} + s_{n−3}\) for every \(n ≥ 3\). Use this recurrence relation to show that the generating function \(S(x)\) for \(\{sn\}\) is \(\dfrac{1}{1−x−x^2−x^3}\)