# generating functions (recurrence relations)

how can I use generating functions to solve the recurrence relation $$a_n = 4a_{n-1} -4a_{n-2}$$

$$a_1 = 1, a_2=3$$

some terms: 1,3,8,20,48

$$a_n -4a_{n-1} +4a_{n+2} =0$$

$$f(x)= 1+3x+ 8x^2 +20x^3+\dots$$ $$-4xf(x)= 4x+12x^2 +32x^3$$ $$4x^2f(x)= 4x^2 +12x^3 +32x^4$$

$$(1-4x+4x^2)f(x)=1-x$$

so I get $f(x)=\frac {1-x}{1-4x+4x^2}$ but I think it should be $f(x)= \frac {x-x^2}{1-2x^2}$ dunno where it went wrong.

and then I'm wondering how can I find $a_n$ now that I have the generating function?

Start by setting up your generating function: $$F(x):=\sum_{n=1}^{\infty}a_nx^n.$$ Now, using the recurrence relation that $a_n=4a_{n-1}-4a_{n-2}$, you can rewrite this as \begin{align*} F(x)&=\sum_{n=1}^{\infty}a_nx^n\\ &=a_1x+a_2x^2+\sum_{n=3}^{\infty}a_nx^n\\ &=a_1x+a_2x^2+\sum_{n=3}^{\infty}(4a_{n-1}-4a_{n-2})x^n\\ &=a_1x+a_2x^2+4x\sum_{n=3}^{\infty}a_{n-1}x^{n-1}-4x^2\sum_{n=3}^{\infty}a_{n-2}x^{n-2}\\ &=a_1x+a_2x^2+4x\sum_{n=2}^{\infty}a_nx^n-4x^2\sum_{n=1}^{\infty}a_nx^n. \end{align*} These last two sums are closely related to your original generating function $F(x)$. See if you can rewrite this formula by leveraging that fact, to get a functional relation satisfied by $F(x)$; from there, solving for $F(x)$ will give you an explicit generating function for $(a_n)$, and from there an explicit expression for $(a_n)$ itself.
• You will end up with an equation that looks like $F(x)=\text{(something in terms of$F(x)$)}$. Then, treating $F(x)$ as an unknown quantity, you can solve for $F(x)$ explicitly. Nov 24, 2015 at 19:59
• I'm not going to give you the answer. You have all the parts you need to get that. Notice that one of the two sums above is exactly $F(x)$, and the other one would be if it wasn't missing one term. Nov 24, 2015 at 22:35