Generating Functions

**Jrb599** · April 25th 2008, 02:02 PM

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

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

My function or formula is

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

And my recurrence I got was
$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.

**PaulRS** · April 25th 2008, 02:45 PM

This is what I get:
$\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}}$

$\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: $ \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: $ \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

**Jrb599** · April 25th 2008, 02:57 PM

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

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

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

So the formula is

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

I think that's the formula, not what you posted.

**PaulRS** · April 25th 2008, 04:35 PM

Originally Posted by Jrb599

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

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

So the formula is: $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)

**PaulRS** · April 25th 2008, 04:43 PM

Originally Posted by PaulRS

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

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

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

Thread: Generating Functions

LinkBack

Thread Tools

Display

Generating Functions

Similar Math Help Forum Discussions

Generating functions

generating functions

generating functions

Generating functions

Generating functions...need some help here

Search Tags