Write the generating function of a sequence as the quotient of two polynomials I want to write the generating function of the sequence
$$a_0=2, \;a_1=3, \; a_{n}=2a_{n-1}-2a_{n-2} \; \text{for }n\geq 2$$
as the quotient of two polynomials. But how can I do that? What is the best way?
Just use the definition of the generating function:
\begin{align*}
G(x)&amp;=\sum_{n=0}^{\infty}a_nx_n=a_0+a_1x+\sum_{n=2}^{\infty}a_nx^n \\
&amp;=a_0+a_1x+\sum_{n=2}^{\infty}(2a_{n-1}-2a_{n-2})x^n \\
&amp;=a_0+a_1x+2\sum_{n=1}^{\infty}a_nx^{n+1}-2\sum_{n=0}^{\infty}a_nx^{n+2} \\
&amp;=a_0+a_1x+2x\left(-a_0+\sum_{n=0}^{\infty}a_nx^n\right)-2x^2\sum_{n=0}^{\infty}a_nx^n \\
&amp;=a_0+(a_1-2a_0)x+2xG(x)-2x^2G(x)
\end{align*}
Solving for $G(x)$ we obtain
$$
G(x)=\frac{a_0+(a_1-2a_0)x}{1-2x+2x^2}=\frac{2-x}{1-2x+2x^2}.
$$
I don't think this is possible. If you write the characteristic equation, you get $\lambda^2=2\lambda-2$, so $(\lambda-1)^2=-1$ i.e. $\lambda=1\pm i$ so the generic solution is of the form $a_n=c_1(1+i)^n+c_2(1-i)^n$ hence $c_1+c_2=2$ and $c_1(1+i)+c_2(1-i)=3$ which solves to
$$a_n=\left(1-\frac{i}{2}\right)(1+i)^n+\left(1+\frac{i}{2}\right)(1-i)^n$$
which is exponential (not a rational function) in $n$.