Generating function of $a_{n+1} = 4a_{n} - a_{n-1}$

Question

I need to find the generating function of this recurrence when $a_0 = 4$, $a_1$ = 8

$f(x) = \sum_{i=0}^\infty a_ix^i = 4 + 8x + (4a_1 - a_0)x^2 + (4a_2 - a_1)x^3 + \dots$

$f(x) = 4 + 8x + 4a_1x^2 - a_0x^2 + 4a_2x^3 - a_1x^3 + \dots$

$f(x) = 4 + 8x + 4x(a_1x + a_2x^2 + \dots) - x^2(a_0 + a_1x + \dots)$

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

$f(x) = \dfrac{4 - 8x}{x^2 - 4x + 1}$

I dont know if this is the correct generating function, but either way I dont know how to interpret the answer, like for instance $f(1)$ is the sum of all terms of the recurrence? then it seems strange I get $f(1) = 2$. Did I do a mistake?

Answer 1

To rewrite your work more clearly:

\begin{align}f(x)&=\sum_{n=0}^\infty a_nx^n\\&=4+8x+\sum_{n=0}^\infty a_{n+2}x^{n+2}\\&=4+8x+\sum_{n=0}^\infty(4a_{n+1}-a_n)x^{n+2}\\&=4+8x+4x(f(x)-4)-x^2f(x)\\&=4-8x-(x^2-4x)f(x)\end{align}

$$f(x)=\frac{4-8x}{x^2-4x+1}$$

As noted in the comments, this representation is valid provided that it converges, which is only for $|x|<2-\sqrt3$.

From this form, we can then derive the coefficients by expanding it out as follows:

\begin{align}f(x)&=\frac{4-8x}{x^2-4x+1}\\&=\frac{4-8x}{(x-2)^2-3}\\&=\frac{4-8x}{(x-2-\sqrt3)(x-2+\sqrt3)}\\&=\frac{-4-2\sqrt3}{x-2-\sqrt3}+\frac{-4+2\sqrt3}{x-2+\sqrt3}\\&=\frac2{1-\frac x{2+\sqrt3}}+\frac2{1-\frac x{2-\sqrt3}}\\&=2\sum_{n=0}^\infty\underbrace{\left[\frac1{(2+\sqrt3)^n}+\frac1{(2-\sqrt3)^n}\right]}_{a_n/2}x^n\end{align}