Solving linear recursive equation $a_n = a_{n-1} + 2 a_{n-2} + 2^n$.

The $1-2z$ in your implicit equation for $A(z)$ is not correct, it should be $1-3z$:

$$\begin{eqnarray*}A(z)&=& a_0 + a_1 z + \sum_{n \geq 2} a_n z^n \\ &=& 2+ z + \sum_{n \geq 2} a_{n-1} z^n + \sum_{n \geq 2} 2 a_{n-2} z^n + \sum_{n \geq 2} 2^n z^n \\ &=&2+ z + \sum_{n \geq 1} a_n z^{z+1} + \sum_{n \geq 0} 2 a_n z^{n+2} + \sum_{n \geq 2} (2z)^n \\ &=&2+ z + \bigl(z A(z)-2 z\bigr) + 2 z^2 A(z) + \left(\frac{1}{1-2z}-1-2z\right)\\ &=&1-\color{red}{3} z + z A(z) + 2z^2 A(z) + \frac{1}{1-2z}\end{eqnarray*}$$ Now you can use your method to compute the coefficients of $A(z)$. This is done in detail in Brian M. Scott's answer.

I’ll use generating functions. I first rewrite the recurrence so that it holds for all $n\ge 0$ on the assumption that $a_n=0$ for $n<0$:

$$a_n=a_{n-1}+2a_{n-2}+2^n+[n=0]-3[n=1]\;,\tag{1}$$

where the last two terms use the Iverson bracket. (This is basically just a sneaky way to take care of the initial values right from the start.) Now multiply $(1)$ be $x^n$ and sum over $n\ge 0$, writing $A(x)$ for $\sum_{n\ge 0}a_nx^n$:

$$\begin{align*} A(x)&=\sum_{n\ge 0}a_{n-1}x^n+2\sum_{n\ge 0}a_{n-2}x^n+\sum_{n\ge 0}2^nx^n+1-3x\\ &=x\sum_{n\ge 0}a_{n-1}x^{n-1}+2x^2\sum_{n\ge 0}a_{n-2}x^{n-2}+\frac1{1-2x}+1-3x\\ &=xA(x)+2x^2A(x)+\frac{2-5x+6x^2}{1-2x}\;, \end{align*}$$

so

$$A(x)=\frac{2-5x+6x^2}{(1-2x)(1-x-2x^2)}=\frac{2-5x+6x^2}{(1-2x)^2(1+x)}\;.$$

Break this into partial fractions:

$$\frac{2-5x+6x^2}{(1+x)(1-2x)^2}=\frac{a}{1+x}+\frac{b}{1-2x}+\frac{c}{(1-2x)^2}\;,$$

so

$$2-5x+6x^2=a(1-2x)^2+b(1+x)(1-2x)+c(1+x)\;.$$

Substituting $x=\frac12$, we find that $\frac32c=1$, or $c=\frac23$. Substituting $x=-1$, we find similarly that $9a=13$, or $a=\frac{13}9$. Thus,

$$\begin{align*} 2-5x+6x^2&=\frac{13}9(1-2x)^2+b(1+x)(1-2x)+\frac23(1+x)\\ &=\left(\frac{13}9+b+\frac23\right)+x\left(-\frac{52}9-b+\frac23\right)+x^2\left(\frac{52}9-2b\right)\\ &=\left(b+\frac{19}9\right)+x\left(-b-\frac{46}9\right)+x^2\left(\frac{52}9-2b\right)\;, \end{align*}$$

so $b+\frac{19}9=2$, and $b=-\frac19$. As a safety check it’s easily verified that the other two coefficients yield the same value of $b$, so

$$\begin{align*} A(x)&=\frac19\left(\frac{13}{1+x}-\frac1{1-2x}+\frac6{(1-2x)^2}\right)\\ &=\frac19\left(13\sum_{n\ge 0}(-1)^nx^n-\sum_{n\ge 0}2^nx^n+3\cdot\frac2{(1-2x)^2}\right)\\ &=\frac19\left(13\sum_{n\ge 0}(-1)^nx^n-\sum_{n\ge 0}2^nx^n+3\cdot\frac{d}{dx}\left(\frac1{1-2x}\right)\right)\\ &=\frac19\left(13\sum_{n\ge 0}(-1)^nx^n-\sum_{n\ge 0}2^nx^n+3\sum_{n\ge 0}n2^nx^{n-1}\right)\\ &=\frac19\left(13\sum_{n\ge 0}(-1)^nx^n-\sum_{n\ge 0}2^nx^n+6\sum_{n\ge 0}(n+1)2^nx^n\right)\\ &=\sum_{n\ge 0}\frac{13(-1)^n-2^n+6(n+1)2^n}9x^n\\ &=\sum_{n\ge 0}\frac{(6n+5)2^n+13(-1)^n}9x^n\;, \end{align*}$$

and

$$a_n=\frac{(6n+5)2^n+13(-1)^n}9\;.$$

Suppose $$ a_n=a_{n-1}+2a_{n-2}+2^n\tag{1} $$ Let $a_n=b_n+\frac23n\,2^n$, then $$ b_n+\frac23n\,2^n =b_{n-1}+\frac23(n-1)\,2^{n-1}+2b_{n-2}+2\cdot\frac23(n-2)\,2^{n-2}+2^n\tag{2} $$ and cancelling, we get $$ b_n=b_{n-1}+2b_{n-2}\tag{3} $$ The standard solution to $(3)$ is $b_n=c_1(-1)^n+c_22^n$. Therefore, $$ a_n=c_1(-1)^n+\left(c_2+\frac23n\right)2^n\tag{4} $$ Solving for $a_0=2$ and $a_1=1$, we get $$ a_n=\frac{13}9(-1)^n+\left(\frac59+\frac23n\right)2^n\tag{5} $$

---

Comment on the Ansatz Method

Let $Sa_n=a_{n+1}$. If we apply $S-2$ to $(1)$, we get $$ \begin{align} (S-2)\left(a_n-a_{n-1}-2a_{n-2}\right) &=(S-2)2^n\\ &=0\tag{6} \end{align} $$ This means $$ (S+1)(S-2)^2a_n=0\tag{7} $$ The problem with the Ansatz method, is the exponent of $2$ on $(S-2)$.

The standard solution for $(7)$ is $a_n=c_1(-1)^n+(c_2+c_3n)2^n$.