# Solving a recurrence relation using generating functions

My recurrence relation is D(n) = D(n 􀀀- 1) + D(n - 2) + 5(n -􀀀 1); with the initial conditions D(2),D(3) being 6, 17 respectively. The generating function G(z) for the sequence D(n) is given I don't know how i got this. Please can anyone give explanation for this?

Thank you.

## 2 Answers

Note that we can work backwards from $D(2)$ and $D(3)$ to discover what $D(1)$ and then $D(0)$ should be if the recurrence is to hold for $D(2)$ and $D(3)$ as well. We find that if $D(0)=0$ and $D(1)=1$, the recurrence does indeed yield $D(2)=6$ and $D(3)=17$, so we can simplify matters by taking $D(0)=0$ and $D(1)=1$ as initial conditions.

There are a couple of slightly different ways to proceed from this point; I prefer the one used in Graham, Knuth, & Patashnik, Concrete Mathematics. Assume that $D(n)=0$ for all $n<0$. Then the recurrence

$$D(n)=D(n-1)+D(n-2)+5(n-1)+5[n=0]+[n=1]\tag{1}$$

holds for all integers $n$, where the terms in square brackets are Iverson brackets. Multiply $(1)$ by $z^n$ and sum over $n$:

\begin{align*} \sum_nD(n)z^n&=\sum_nD(n-1)z^n+\sum_nD(n-2)z^n+5\sum_n(n-1)z^n+5+z\\\\ &=z\sum_nD(n-1)z^{n-1}+z^2\sum_nD(n-2)z^{n-2}+5\sum_nnz^n-5\sum_nz^n+5+z\\\\ &=z\sum_nD(n)z^n+z^2\sum_nD(n)z^n+\frac{5z}{(1-z)^2}-\frac5{1-z}+5+z\;. \end{align*}

If $G(z)=\sum_nD(n)z^n$, we can now write

$$G(z)=zG(z)+z^2G(z)+\frac{5z}{(1-z)^2}-\frac5{1-z}+5+z$$

and collect terms in $G(z)$ on the lefthand side of the equation to get

$$(1-z-z^2)G(z)=\frac{5z}{(1-z)^2}-\frac5{1-z}+5+z\;.$$

As a quick check, note that

\begin{align*} \frac{5z}{(1-z)^2}&-\frac{5}{1-z}+5+z\\ &=5(z+2z^2+3z^3+\ldots)-5(1+z+z^2+\ldots)+5+z\\ &=5(2z^2+3z^3+4z^4+\ldots)-5(z^2+z^3+z^4+\ldots)+z\\ &=z+5z^2+10z^3+15z^4+\ldots\;, \end{align*}

agreeing nicely with

\begin{align*} (1-z-z^2)G(z)&=(1-z-z^2)(z+6z^2+17z^3+38z^4+\ldots)\\ &=z+5z^2+10z^3+15z^4+\ldots\;. \end{align*}

Thus,

$$G(z)=\frac1{1-z-z^2}\left(5+z-\frac5{1-z}+\frac{5z}{(1-z)^2}\right)\;.$$

This is not equal to your

$$\frac1{1-z-z^2}\left(6+11z+\frac{15z^2}{1-z}+\frac{5z^3}{(1-z)^2}\right)\;,$$

as you can check by noting that the constant term when you expand

$$6+11z+\frac{15z^2}{1-z}+\frac{5z^3}{(1-z)^2}$$

is $6$, not $0$.

If you change your function to

$$\frac1{1-z-z^2}\left(6z^2+11z^3-\frac{5z^2}{1-z}+\frac{5z^3}{(1-z)^2}\right)\;,$$

you get the generating function for the $D$ sequence with $D(0)$ and $D(1)$ arbitrarily set to $0$; if you change it to

$$\frac1{1-z-z^2}\left(6+11z-\frac{5}{1-z}+\frac{5z}{(1-z)^2}\right)\;,$$

you get the generating function for the same recurrence, but with initial conditions $D(0)=6$ and $D(1)=17$.

Define the generating function:

$$G(z) = \sum_{n \ge 0} D(n) z^n$$

Take your recurrence written as:

$$D(n + 2) = D(n + 1) + D(n) + 5 (n + 1)$$

Multiply by $z^n$, sum over $n \ge 0$ and recognize some sums:

$$\frac{G(z) - D(0) - D(1) z}{z^2} = \frac{D(z) - D(0)}{z} + G(z) + \frac{5}{(1 - z)^2}$$

Solve for $G(z)$, split into partial fractions:

\begin{align} G(z) &= \frac{D(0) + (D(1) - 3 D(0)) z - (2 D(1) - 3 D(0) - 5) z^2 + (D(1) - D(0)) z^3} {(1 - z)^2 (1 - z - z^2)} \\ &= \frac{(D(0) + 10) + (D(1)- D(0) + 5) z}{1 - z - z^2} - \frac{5}{1 - z} - \frac{5}{(1 - z)^2} \end{align}

Now we know that the Fibonacci numbers $F_n$ are defined by:

$$F_{n + 2} = F_{n + 1} + F_n \qquad F_0 = 0, F_1 = 1$$

with generating function:

$$F(z) = \sum_{n \ge 0} F_n z^n = \frac{z}{1 - z - z^2}$$

so that $1 / (1 - z - z^2)$ corresponds to the sequence of the $F_{n + 1}$, and so:

$$D(n) = (D(0) + 10) F_{n + 1} + (D(1) - D(0) + 5) F_n - 5 - 5 (n + 1)$$

Plug in the known values of $D(2)$ and $D(3)$ to get a system of equations for the missing $D(0)$ and $D(1)$, and you are done.