Recurrence relation using generating functions to solve? Consider the recurrence relation: $ a_n = −a_{n−1} + 6a_{n−2}, n ≥ 2, a_0 = 0, a_1 = 4.$
(a) Solve the recurrence relation by finding the characteristic
equation.
$r^2+r+6=0 \to (r+ \frac {1}{2})^2 +\frac{23}{4}=0 \to r= -\frac {1}{2}\pm i\frac{ \sqrt {23}}{2}$
$a_n^{(h)} =  (-\frac {1}{2}+ (i\frac{ \sqrt {23}}{2})^n + ( -\frac {1}{2}\ -(i\frac{ \sqrt {23}}{2}))^n$
$a_n =  c_1(-\frac {1}{2}+ (i\frac{ \sqrt {23}}{2})^n + c_2 ( -\frac {1}{2}\ -(i\frac{ \sqrt {23}}{2}))^n $
$a_0=0 =  c_1 + c_2 $
$a_1 =4=  c_1(-\frac {1}{2}+ (i\frac{ \sqrt {23}}{2}) + c_2 ( -\frac {1}{2}\ -(i\frac{ \sqrt {23}}{2}))$
(b) Solve the recurrence relation using the method of generating functions.
$ a_2 = −a_{1} + 6a_{0} $
$ a_3 = −a_{2} + 6a_{1} $
$ a_4 = −a_{3} + 6a_{2} $
i know im supposed to  multiple $a_1 $ by x etc but im not really sure how to do it... how do i know what $g(x)$='s?
 A: It is formally very easy, but dizzying sometimes:
Define
$$f(x)=\sum_0^\infty a_nx^n$$
Write the recurrence relation,
$$a_{n+2}=-a_{n+1}+6a_n$$
Multiply by $x^{n+2}$
$$a_{n+2}x^{n+2}=-a_{n+1}x^{n+2}+6a_nx^{n+2}$$
Sum
$$\sum_0^\infty a_{n+2}x^{n+2}=-\sum_0^\infty a_{n+1}x^{n+2}+\sum_0^\infty 6a_nx^{n+2}$$
Do things
$$\sum_2^\infty a_{n}x^{n}=-x\sum_1^\infty a_{n}x^{n}+6x^2\sum_0^\infty a_nx^n$$
$$\sum_0^\infty a_{n}x^{n}-a_1x-a_0=-x\sum_0^\infty a_{n}x^n+a_0x++6x^2\sum_0^\infty a_nx^n$$
Recover $f(x)$
$$f(x)-a_1x-a_0=-xf(x)+a_0x+6x^2f(x)$$
Isolate:
$$(6x^2-x-1)f(x)=-a_1x-a_0x-a_0$$
$$f(x)=-\frac{a_1x+a_0x+a_0}{6x^2-x-1}=-\frac{a_1x+a_0x+a_0}{6x^2-x-1}$$
We can get now $a_0=0$, $a_1=4$
$$f(x)=\frac{-4x}{(2x-1)(3x+1)}=\frac{-4}{5(2x-1)}+\frac{-4}{5(3x+1)}$$
$$f(x)=\frac{4}{5(1-2x)}-\frac{4}{5(1-(-3x))}$$
These can be expanded as the geometric series:
$$f(x)=\sum_0^\infty\frac 45(2x)^n-\sum_0^\infty\frac 45(-3x)^n$$
At last,
$$f(x)=\sum_0^\infty\frac{4}{5}(2^n-(-3)^n)x^n$$
A: $G(x) = \sum_{n=0}^{\infty} a_nx^n$
$G(x) = a_0x^0 + a_1x^1 + \sum_{n=2}^{\infty} a_nx^n$
$G(x) - 4x= + \sum_{n=2}^{\infty} (-a_{n-1} + 6a_{n-2})x^n$
$G(x) - 4x= -\sum_{n=2}^{\infty}a_{n-1}x^n + 6\sum_{n=2}^{\infty}a_{n-2}x^n$
$G(x) - 4x= -x\sum_{n=2}^{\infty}a_{n-1}x^{n-1} + 6x^2\sum_{n=2}^{\infty}a_{n-2}x^{n-2}$
$G(x) - 4x= -x\sum_{n=1}^{\infty}a_{n}x^{n} + 6x^2\sum_{n=0}^{\infty}a_{n}x^{n}$
$G(x) - 4x= -x(-0x^0 + \sum_{n=0}^{\infty}a_{n}x^{n}) + 6x^2\sum_{n=0}^{\infty}a_{n}x^{n}$
$G(x) - 4x= -xG(x) + 6x^2G(x)$
$G(x) =  \frac{4x}{1 + x - 6x^2} = \frac{4x}{ (1-2 x)(1+3 x)}$
Apply partial fraction decomposition to get:
$G(x) = \frac{4}{5}\left(\frac{1}{1-2 x} - \frac{1}{1+3 x} \right)$
$a_n = \frac{4}{5}(2^n - (-3)^n)$
