Recurrence relation problem

**rorosingsong** · November 8th 2011, 03:35 AM

Hi I'm studying for my finals and having trouble with this question:

Consider the following recurrence relation:
$a_{n+2} = a_{n+1} + a_{n} + n$ for $n\geqslant 0$ where $a_{0} = a_{1} = 1$ .
Write the corresponding generating function in its closed form.

I've set up the generating function as
$G(z) = a_{0} + a_{1}z + a_{2}z^{2} + a_{3}z^{3} + a_{4}z^{4} + ...$ and I've gotten as far in my working as:
$G(z)(1-z-z^{2})= 1 + nz^{2}(1 + nz + nz^{2} + ...)$

But according to the solutions I should at this stage be getting:
$G(z)(1-z-z^{2})= 1 + z^{3}(1 + 2z + 3z^{2} + ...)$

What am I doing wrong?
I'd really appreciate some help on this one, thanks in advance!

Cheers,
Roro

**emakarov** · November 8th 2011, 06:45 AM

We have the following table where I called the function in the last row F(z):

$\begin{array}{cccccc|ccccccc}G(z) & = & a_0 & + & a_1z^1 & + & a_2z^2 & + & a_3z^3 & + & a_4z^4 & + & \dots\\G(z)z & = & & & a_0z^1 & + & a_1z^2 & + & a_2z^3 & + & a_3z^4 & + & \dots\\G(z)z^2 & = & & & & + & a_0z^2 & + & a_1z^3 & + & a_2z^4 & + & \dots\\F(z) & = & & & & & 0z^2 & + & 1z^3 & + & 2z^4 & + & \dots\\\end{array}$

In the right part of the table (after the vertical line), the first row equals the sum of the other rows. Using $a_0=a_1=1$ , this gives

$\begin{aligned}G(z)-1-z &= (G(z)z-z) + G(z)z^2+F(z)\\ &= (G(z)z-z) + G(z)z^2+z^3(1+2z+3z^2+\dots)\\\end{aligned}$

Thread: Recurrence relation problem

LinkBack

Thread Tools

Display

Recurrence relation problem

Re: Recurrence relation problem

Similar Math Help Forum Discussions

recurrence relation problem!

Population recurrence relation problem.

Recurrence Relation Problem...

Recurrence Relation problem (URGENT)

Recurrence relation problem

Search Tags