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

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?

• Looks good. $f(1)$ would be the sum of all the terms in the recursion IF the radius of convergence were $>1$. In this case, though, the radius is just $2-\sqrt 3$. – lulu Nov 27 '19 at 13:58
• $a_1$ is the coefficient on $x$ in the series for $f$ – J. W. Tanner Nov 27 '19 at 13:58

\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$$.
\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}