<s>[INST] 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.
 [/INST] 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$.
</s>