# Thread: Generating funtion -> recurrence relation

1. ## Generating funtion -> recurrence relation

Hi. I have this problem.

Let $\displaystyle H(x)=\sum_{n\ge 0}{h_nx^n}$ and $\displaystyle H(x)=\frac{1-2x+2x^2}{(1-x)^2(1-2x)}$
a) Find the recurrence relation the coefficients $\displaystyle 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 $\displaystyle 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
$\displaystyle H(x)=\frac{2}{1-2x}-\frac{1}{(1-x)^2}$

Then my nxt step was to place it into $\displaystyle H(x)=\sum_{n\ge 0}{h_nx^n}$ form. So I get,
$\displaystyle H(x)=2\sum_{n\ge 0}{(2x)^n-\sum_{n\ge 0}{(n+1)x^n}$ by geometric series.
$\displaystyle =2{\sum_{n\ge 0}{(2^n-\frac{1}{2}(n+1)) x^n$
so $\displaystyle 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. $\displaystyle h_0=\frac{1}{2}$?

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

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

2. Hi lpd,

$\displaystyle (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

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

then that's a recurrence relation. If I write

$\displaystyle x_n = 2^n$,

that's an explicit expression.

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

3. cool. okay. this is what i did now.

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

We have the following terms:
$\displaystyle (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,
$\displaystyle h_n-4h_{n-1}+5h_{n-2}-2h_{n-3}=0$

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

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

The coefficient of $\displaystyle x^2$ on RHS is $\displaystyle 2$. Hence let $\displaystyle n=2$, and equate it.
$\displaystyle (h_2)(1)+(h_1)(-4)+(h_0)(5)=2$
$\displaystyle h_2=2+4h_1-5h_0=2+8-5$
i.e. $\displaystyle 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?

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