<s>[INST] Solving linear recursive equation $a_n = a_{n-1} + 2 a_{n-2} + 2^n$. I wish to solve the linear recursive equation:

$a_n = a_{n-1} + 2a_{n-2} + 2^n$, where $a_0 = 2$, $a_1 = 1$.

I have tried using the Ansatz method and the generating function method in the following way:
Ansatz method
First, for the homogenous part, $a_n = a_{n-1} + 2a_{n-2}$, I guess $a_n = \lambda^n$ as the solution, and substituting and solving for the quadratic, I get $\lambda = -1, 2$. So, $a_n = \alpha (-1)^n + \beta 2^n$. Then, for the inhomogenous part, I guess $a_n = \gamma 2^n$, to get $\gamma 2^n = \gamma 2^{n-1} + 2\gamma 2^{n-2} + 2^n$, whence $2^n=0$, which means, I suppose, that this guess is not valid. These are the kind of guesses that usually work, so I don't know why it fails in this particular case, and what to do otherwise, so I tried the generating function method.
Generating function method
Let
$$
A(z) = \sum_{i=0}^{\infty} a_k z^k
$$
be the generating function for the sequence $\{ a_n \}_{n \in \mathbb{N} \cup {0}}$. Then, I try to write down the recursive relation in terms of $A(z)$:
$$
A(z) = zA(z) + 2z^2 A(z) + \frac{1}{1-2z} + (1 - 2z),
$$
where the last term in the brackets arises because of the given initial conditions. Then, solving for $A(z)$,
$$
\begin{align}
A(z) &= \frac{1}{(1+z)(1-2z)^2} + \frac{1}{1+z}\\
&= \frac{2}{9}\frac{1}{1-2z} + \frac{2}{3}\frac{1}{(1-2z)^2} + \frac{10}{9}\frac{1}{1+z}\\
&=\frac{2}{9} \sum_{k=0}^{\infty} 2^k z^k + \frac{2}{3} \sum_{k=0}^{\infty} (k+1)2^k z^k + \frac{10}{9} \sum_{k=0}^{\infty} (-1)^k z^k\\
&= \sum_{k=0}^\infty \frac{(3k+4)2^{k+1} + (-1)^k 10}{9} z^k.
\end{align}
$$
So,
$$
a_k = \frac{(3k+4)2^{k+1} + (-1)^k 10}{9}.
$$
But then, $a_1 = 2$, whereas we started out with $a_1 = 1$.
At first, I thought that maybe the generating function method did not work because some of the series on the right hand side were not converging, but they all look like they're converging for $|z| < 1/2$. I rechecked my calculations several times, so I don't think there is any simple mistake like that. It would be great if someone could explain to me what exactly is going wrong here.
 [/INST] 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$.
</s>