Generating funtion -> recurrence relation

**lpd** · October 12th 2010, 06:11 AM

Hi. I have this problem.

Let $H(x)=\sum_{n\ge 0}{h_nx^n}$ and $H(x)=\frac{1-2x+2x^2}{(1-x)^2(1-2x)}$
a) Find the recurrence relation the coefficients $h_n$ satisfy. Be sure to state the initial values.

Okay, this is what I did so far. I went about finding the partial fractions for this $H(x)=\frac{1-2x+2x^2}{(1-x)^2(1-2x)}$ . And assuming I did it correctly (I checked it on a calculator so it should be correct)... I ended up with this
$H(x)=\frac{2}{1-2x}-\frac{1}{(1-x)^2}$

Then my nxt step was to place it into $H(x)=\sum_{n\ge 0}{h_nx^n}$ form. So I get,
$H(x)=2\sum_{n\ge 0}{(2x)^n-\sum_{n\ge 0}{(n+1)x^n}$ by geometric series.
$=2{\sum_{n\ge 0}{(2^n-\frac{1}{2}(n+1)) x^n$
so $h_n=2(2^n-\frac{1}{2}(n+1))$

It doesn't look right to me. Because I don't know what the initial values are. $h_0=\frac{1}{2}$ ?

b) Find an explicit expression for $h_n$ , $n\ge0$

How do I do this one? What would be the difference between finding the recurrence relation??

Thanks for your help.

**awkward** · October 12th 2010, 01:52 PM

Hi lpd,

On finding a recurrence relation, probably you want to start with

$(1-x)^2 (1-2x) H(x) = 1 - 2x + 2x^2$ .

See what happens when you multiply everything out-- it should give you information about the coefficients of H(x).

A recurrence relation is not the same thing as finding an explicit expression for the coefficients. For example, if I write

$x_{n+1} = 2 x_n, x_1 = 1$

then that's a recurrence relation. If I write

$x_n = 2^n$ ,

that's an explicit expression.

It's in finding an explicit expression for $h_n$ that you may find partial fractions useful.

**lpd** · October 12th 2010, 03:59 PM

cool. okay. this is what i did now.

$((1-x)^2(1-2x))H(x)=1-2x+2x^2$
$(1-4x+5x^2-2x^3)H(x)= 1-2x+2x^2$
coefficient of $x^n$ for $n \ge 3$ is $0$ from RHS

We have the following terms:
$(h_n x^n)1, (h_{n-1} x^{n-1})(-4x),(h_{n-2} x^{n-2})(5x^2),(h_{n-3} x^{n-3})(-2x^3).$
These terms must add up to zero,
$h_n-4h_{n-1}+5h_{n-2}-2h_{n-3}=0$

The constant term on RHS is $1$ . Hence the constant term of $h(x)$ is $1$ . i.e $h_0=1$

The coefficient of $x$ on RHS is $-2$ . Hence let $n=1$ , and equate it.
$(h_1)(1)+(h_0)(-4)=-2$ , $h_1=-2+4h_0$
i.e $h_1=2$

The coefficient of $x^2$ on RHS is $2$ . Hence let $n=2$ , and equate it.
$(h_2)(1)+(h_1)(-4)+(h_0)(5)=2$
$h_2=2+4h_1-5h_0=2+8-5$
i.e. $h_2=5$

Was I on the right track?

and for b) to find the explicit expression of h(x), I have somewhat done it already. i.e. finding the partial fraction. so

is correct right?

**awkward** · October 12th 2010, 05:32 PM

You have the right idea, but you need to double-check your algebra.

To see if your explicit solution is correct, substitute it into your recurrence relation. It should reduce to an identity.

Thread: Generating funtion -> recurrence relation

LinkBack

Thread Tools

Display

Generating funtion -> recurrence relation

Similar Math Help Forum Discussions

how to solve this recurrence using generating functions?

recurrence and generating functions

Finding the generating function of a recurrence

Prove/disprove that a given moment generating funtion has a pron. distribution.

Recurrence Relations: Generating Functions

Search Tags