# Generating functions - a reccurence to solve

• May 27th 2011, 04:11 PM
Muvena
Generating functions - a reccurence to solve
I'm not sure how to solve the following reccurence:
By using generating functions solve the reccurence. Find both the generating function and the closed form solution of the sequence:

$\\a_{0} =0, \\a_{1} = 1, \\a_{n} = 7a_{n-1} - 10a_{n-2} + 2 , \: for \: n \geq 2$
• May 27th 2011, 06:28 PM
Also sprach Zarathustra
Quote:

Originally Posted by Muvena
I'm not sure how to solve the following reccurence:
By using generating functions solve the reccurence. Find both the generating function and the closed form solution of the sequence:

$\\a_{0} =0, \\a_{1} = 1, \\a_{n} = 7a_{n-1} - 10a_{n-2} + 2 , \: for \: n \geq 2$

Let $f(x)=a_0+a_1x+a_2x^2+...$ be the generating function of $a_n$.

Let us write:

$f(x)=\sum_{i = 0}^\infty a_ix^i=0+x+\sum_{i = 2}^\infty a_ix^i=x+\sum_{i = 2}^\infty(7a_{i-1} - 10a_{i-2} + 2 )x^i=x+\sum_{i = 2}^\infty7a_{i-1}x^i-\sum_{i = 2}^\infty10a_{i-2}x^i+\sum_{i = 2}^\infty2x^i=x+x\sum_{j = 1}^\infty7a_{j}x^j-x^2\sum_{j = 0}^\infty10a_{j}x^j+\frac{2x^2}{1-x}=x+7x(f(x))-10x^2(f(x))+\frac{2x^2}{1-x}$

So:

$f(x)=x+7x(f(x))-10x^2(f(x))+\frac{2x^2}{1-x}$

$f(x)\{1-7x-+10x^2 \}=x+\frac{2x^2}{1-x}$

$f(x)=\frac{x+\frac{2x^2}{1-x}}{1-7x-+10x^2}$

Now, to find closed form solution of the sequence you need to find the coefficient of $x^k$ in Taylor's series of $f(x)$. This task I'll leave it to you.
• May 28th 2011, 03:28 PM
Krakowie
Thanks a lot for your help!