<s>[INST] Solving recurrence equation using generating function method I've been trying to solve the following equation intuitively (I only know the method if there are minuses in the equation - $a_{n-1}, a_{n-2}...$).
$$a_{n+2}=4a_{n+1}-4a_{n}$$
$$a_{0}=3$$
$$a_{1}=8$$
$$
\begin{align}
A(x)&=\sum\limits_{n>=0}a_{n}x^{n} \\
&= \sum\limits_{n>=0}(a_{n+1}-\frac{1}{4}a_{n+2})x^{n} \\
&= \sum\limits_{n>=0}(a_{n+1})x^{n}-\frac{1}{4}\sum\limits_{n>=0}(a_{n+2})x^{n} \\
&= \sum\limits_{n>=1}(a_{n})x^{n+1}-\frac{1}{4}\sum\limits_{n>=2}(a_{n})x^{n+2} \\
&= \frac{1}{x}\sum\limits_{n>=1}(a_{n})x^{n}-\frac{1}{4x^{2}}\sum\limits_{n>=2}(a_{n})x^{n} \\
&= \frac{1}{x}[\sum\limits_{n>=0}(a_{n})x^{n} - 3]-\frac{1}{4x^{2}}[\sum\limits_{n>=0}(a_{n})x^{n} - 3 - 8x] \\
&= \frac{1}{x}[A(x) - 3]-\frac{1}{4x^{2}}[A(x) - 3 - 8x]
\end{align}
$$
So I get
$$A(x)=\frac{-4x+3}{4x^{2}-4x+1}$$
Is this correct? I'm asking because the answer to this question according to the source I got it from is $x^{2}-4x+4$ as the denominator...
 [/INST] Just another approach for verification.
Assume
$$
a_{n+2}=4a_{n+1}-4a_{n}
$$
Then
$$
\begin{align}
f(x)&=\sum_{k=0}^\infty a_kx^k\\
xf(x)&=\sum_{k=1}^\infty a_{k-1}x^k\\
x^2f(x)&=\sum_{k=2}^\infty a_{k-2}x^k\\
\end{align}
$$
Then we get
$$
\begin{align}
f(x)(1-4x+4x^2)&=a_0+a_1x-4a_0x+\sum_{k=2}^\infty(a_k-4a_{k-1}+4a_{k-2})x^k\\
&=a_0+(a_1-4a_0)x\\[18pt]
f(x)&=\frac{a_0+(a_1-4a_0)x}{1-4x+4x^2}\\
&=\frac{3-4x}{1-4x+4x^2}
\end{align}
$$
</s>