Solving recurrence equation using generating function method

Question

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...

Answer 1

Not sure where you went wrong, so I'll start from scratch with a different method:

Let $A(x)=\sum_{n=0}^\infty a_nx^n$. Note that $a_n$ satisfies $a_{n+2}-4a_{n+1}+4a_n=0$. Let $p(x)=1-4x+4x^2$. We then define $$ B(x) = \sum_{n=0}^\infty b_nx^n=p(x)A(x) $$ Note that for $n\geq2$, we have $b_n=a_{n+2}-4a_{n+1}+4a_n=0$. So, we simply have $$ p(x)A(x) = b_0+b_1 x $$ Thus, $$ A(x) = \frac{b_0+b_1 x}{1-4x+4x^2}=\frac{a_0+(a_1-4a_0) x}{1-4x+4x^2}=\frac{3-4x}{1-4x+4x^2} $$ It seems you have the right answer, and that your source has a typo.

Answer 2

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