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.
 A: 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$.
A: 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.
