Solving Linear Homogeneous Recurrence Relations with Generating Functions

Recall from the A Closed Form of the Fibonacci Sequence page that for the recursive definition of the Fibonacci numbers $f_n = f_{n-1} + f_{n-2}$ for $n \geq 3$ and with initial values $f_1 = f_2 = 1$ we were able to obtain a closed form for the sequence of Fibonacci numbers which we saw was:

(1)

\begin{align} \quad f_n = \frac{1}{\sqrt{5}} \left ( \left ( \frac{1 + \sqrt{5}}{2} \right )^{n} - \left (\frac{1 - \sqrt{5}}{2} \right )^{n} \right ) \end{align}

We used a generating function in order to derive this closed form that generates the Fibonacci numbers and in general, we can take any linear homogeneous recurrence relation and use generating functions to solve them similarly. The process is easy to apply but may be difficult to fully evaluate due to the necessity to find the roots of a possibly large polynomial or find a series representation of a generating function. Let's look at an example.

Consider the following linear homogeneous recurrence relation where $f_0 = 1$, $f_1 = 9$, and for $n \geq 2$:

(2)

\begin{align} \quad f_n = 6f_{n-1} - 9 f_{n-2} \\ \quad f_n - 6f_{n-1} + 9f_{n-2} = 0 \: (*) \end{align}

Let $F$ be the generating function for the sequence $(f_n)_{n=0}^{\infty} = (f_0, f_1, f_2, ...)$:

(3)

\begin{align} \quad F(x) = f_0 + f_1x + f_2x^2 + ... + f_nx^n + ... \end{align}

We want to somehow incorporate $(*)$ with regards to the generating function $F$. If we multiply $F$ by $6x$ and $F$ by $9x^2$ then:

(4)

\begin{align} \quad 6xF(x) = 6x(f_0 + f_1x + f_2x^2 + ... + f_nx^n + ...) \\ \quad 6xF(x) = 6f_0x + 6f_1x^2 + 6f_2x^3 + ... + 6f_nx^{n+1} + ... \end{align}

(5)

\begin{align} \quad 9x^2F(x) = 9x^2(f_0 + f_1x + f_2x^2 + ... + f_nx^n + ...) \\ \quad 9x^2F(x) = 9f_0x^2 + 9f_1x^3 + 9f_2x^4 + ... + 9f_nx^{n+2} + ... \end{align}

Now take $F(x) - 6xF(x) + 9x^2F(x)$:

(6)

\begin{align} \quad (1 - 6x + 9x^2)F(x) = f_0 + (f_1 - 6f_0)x + \underbrace{(f_2 - 6f_1 + 9f_0)}_{=0 \: \mathrm{from} \: (*)} x^2 + ... + \underbrace{(f_n - 6f_{n-1} + 9 f_{n-2})}_{=0 \: \mathrm{from} \: (*)}x^n + ...\\ \quad (1 - 6x + 9x^2)F(x) = f_0 + (f_1 - 6f_0)x \\ \quad (1 - 6x + 9x^2)F(x) = 1 + (9 -6)x \\ \quad (1 - 6x + 9x^2)F(x) = 1 + 3x \\ \quad F(x) = \frac{1 + 3x}{1 - 6x + 9x^2} \\ \quad F(x) = \frac{1 + 3x}{(3x - 1)^2} \\ \quad F(x) = \frac{1}{(3x - 1)^2} + \frac{3x}{(3x - 1)^2} \end{align}

Now recall that:

(7)

\begin{align} \quad \frac{1}{(1 - x)^2} = \frac{1}{(x - 1)^2} = \sum_{n=0}^{\infty} (n + 1)x^n \end{align}

Substituting $x$ for $3x$ gives us that:

(8)

\begin{align} \quad \frac{1}{(3x - 1)^2} = \sum_{n=0}^{\infty} (n + 1)(3x)^n \\ \quad \frac{1}{(3x - 1)^2} = \sum_{n=0}^{\infty} (n + 1)3^n x^n \: (**) \end{align}

Additionally:

(9)

\begin{align} \quad \frac{3x}{(3x - 1)^2} = 3x \sum_{n=0}^{\infty}(n + 1)3^nx^n \\ \quad \frac{3x}{(3x - 1)^2} = \sum_{n=0}^{\infty}(n + 1)3^{n+1}x^{n+1} \\ \quad \frac{3x}{(3x - 1)^2} = \sum_{n=0}^{\infty}n3^nx^n \: (***) \end{align}

Putting $(**)$ and $(***)$ together yields:

(10)

\begin{align} \quad F(x) = \sum_{n=0}^{\infty} (n + 1)3^n x^n + \sum_{n=0}^{\infty}n3^nx^n \\ \quad F(x) = \sum_{n=0}^{\infty} [(n+1)3^n + n3^n] x^n \\ \quad F(x) = \sum_{n=0}^{\infty} [(2n + 1)3^n]x^n \end{align}

Therefore $f_n = (2n + 1)3^n$ is the solution to this linear homogeneous recurrence relation with initial conditions $f_0 = 1$ and $f_1 = 9$.