# Generating Functions

• Apr 25th 2008, 02:02 PM
Jrb599
Generating Functions
I had a test I took and my work or steps are right, but final answer is wrong and I can't figure out the error. I was given the generating function

$\displaystyle g(x)=\frac{5+2x}{(1-5x)(1+4x)}$

My function or formula is

$\displaystyle h_{n}=2(5^{n})+3(-4)^{n}$

And my recurrence I got was
$\displaystyle h_{n}=h_{n-1}+20h_{n-2}; h_{0}=5, h_{1}=7$

The only problem is my recurrence and function don't spit the same values out. Can anyone help me and tell me which one is wrong.
• Apr 25th 2008, 02:45 PM
PaulRS
This is what I get:
$\displaystyle \frac{1}{(1-5x)\cdot{(1+4x)}}=\sum_{n=0}^{\infty}{\left(\sum_{ k=0}^n{5^k\cdot{(-4)^{n-k}}}\right)\cdot{x^n}}$

$\displaystyle \sum_{k=0}^n{5^k\cdot{(-4)^{n-k}}}= \left( { - 4} \right)^n \cdot \sum\limits_{k = 0}^n {\left( { - \tfrac{5} {4}} \right)^k } = \left( { - 4} \right)^n \cdot \frac{{1 - \left( { - \tfrac{5} {4}} \right)^{n + 1} }} {{1 + \tfrac{5} {4}}} = \left( { - 4} \right)^n \cdot 4 \cdot \frac{{1 - \left( { - \tfrac{5} {4}} \right)^{n + 1} }} {9}$

Thus: $\displaystyle \frac{1} {{\left( {1 - 5x} \right) \cdot \left( {1 + 4 \cdot x} \right)}} = \sum\limits_{n = 0}^\infty {\left( {\tfrac{{\left( { - 4} \right)^n \cdot 4 + 5^{n + 1} }} {9}} \right) \cdot } x^n$

Therefore: $\displaystyle \frac{{2x + 5}} {{\left( {1 - 5x} \right) \cdot \left( {1 + 4 \cdot x} \right)}} = 5 + \sum\limits_{n = 1}^\infty {\left( {2 \cdot \tfrac{{\left( { - 4} \right)^{n - 1} \cdot 4 + 5^n }} {9} + 5 \cdot \tfrac{{\left( { - 4} \right)^n \cdot 4 + 5^{n + 1} }} {9}} \right) \cdot } x^n$

I've got to go now (Time)
• Apr 25th 2008, 02:57 PM
Jrb599
$\displaystyle \frac{5+2x}{(1-5x)(1+4x)}=\frac{2}{1-5x}+\frac{3}{1+4x}$

$\displaystyle \frac{2}{1-5x} = 2*[1+ 5x +5^{2}x^{2} +5^{3}x^{3}+..+5^{n}x^{n}]$ = $\displaystyle 2*5^{n}$

$\displaystyle \frac{3}{1+4x}=3*[1 + (-4x) + (-4x)^{2} +...+(-4)^{n}x^{n}]$= $\displaystyle 3*(-4)^{n}$

So the formula is

$\displaystyle h_{n}=2*5^{n} + 3*(-4)^{n}$

I think that's the formula, not what you posted.
• Apr 25th 2008, 04:35 PM
PaulRS
Quote:

Originally Posted by Jrb599
$\displaystyle \frac{5+2x}{(1-5x)(1+4x)}=\frac{2}{1-5x}+\frac{3}{1+4x}$

Actually it is: $\displaystyle \frac{5+2x}{(1-5x)(1+4x)}=\frac{3}{1-5x}+\frac{2}{1+4x}$

So the formula is: $\displaystyle h_n=3\cdot{5^n}+2\cdot{(-4)^n}$

The formula I posted is ok (it just doesn't look nice because it wasn't simplified)
• Apr 25th 2008, 04:43 PM
PaulRS
Quote:

Originally Posted by PaulRS
the formula is: $\displaystyle h_n=3\cdot{5^n}+2\cdot{(-4)^n}$

Thus the corresponding equation is: $\displaystyle 0=(x-5)\cdot{(x+4)}=x^2-x-20$ =>$\displaystyle x^2=20+x$

And $\displaystyle h_{n+2}=20\cdot{h_n}+h_{n+1}$ with $\displaystyle h_0=5$ and $\displaystyle h_1=7$ so the recurrence you got was ok (Wink)