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.
On
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.
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$.