1
$\begingroup$

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 enter image description here

I don't know how i got this. Please can anyone give explanation for this?

Thank you.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.