Problem solving recurrence equation for $a_n = a_{n-1} + 2a_{n-2}, \,\,\, a_0=a_1=1$ I want to try the generating function $A(x)$ and a formula for $a_n$ for the following sequence:
$$a_n = a_{n-1} + 2a_{n-2}, \,\,\, a_0 = a_1 = 1$$
So I multiplied the above equation on both sides by $x^n$ and summed them for each $n \geq 2$. So:
$$\sum_{n=2}^{\infty} a_nx^n = \sum_{n=2}^{\infty} a_{n-1}x^n + 2\sum_{n=2}^{\infty} a_{n-2}x^n$$
$$\Longrightarrow \sum_{n=2}^{\infty} a_nx^n= \frac{1}{x}\sum_{n=1}^{\infty} a_{n}x^n + 2\frac{1}{x^2}\sum_{n=0}^{\infty} a_{n}x^n$$
$$\Longrightarrow A(x) - x - 1 = \frac{A(x)-1}{x} + 2\frac{A(x)}{x^2}$$
$$\Longrightarrow x^2A(x) - x^3 - x^2 = xA(x)-x + 2A(x)$$
$$\Longrightarrow A(x)(x^2-x-2) = x^3 + x^2 + x$$
$$\Longrightarrow A(x) = \frac{x(x^2 + x + 1)}{(x-2)(x+1)} = \frac{1}{3}  \cdot \frac{1}{1+x} + \frac{14}{3} \cdot \frac{1}{2-x}$$
Now if I search for the series expansion, I find:
$$A(x) = \sum_{n=0}^{\infty} (\frac{1}{3} \cdot (-1)^n - \frac{14}{3} \cdot \frac{1}{2^{n+1}})x^n$$
$$\Longrightarrow a_n = \frac{1}{3} \cdot (-1)^n - \frac{14}{3} \cdot \frac{1}{2^{n+1}}$$
However, this is obviously wrong. I checked on Wolfram, and the correct answer should be:
$$a_n = \frac{1}{3} ((-1)^n+2^{n+1})$$
I redid the whole thing twice, but I got the same result, so I guess that there is some flaw in my logic, rather than the calculations (I could be wrong though).

As the recurrence relation is linear with constant coefficients, let us look for a solution of the form $a_n = z^n$. We obtain
$$z^n (z^2 - z - 2) = 0$$
Given the nonzero initial conditions, $z^n \neq 0$. Hence, $z^2 - z - 2 = 0$. The solutions are $-1$ and $2$.
$$a_n = \beta_1 (-1)^n + \beta_2 2^n$$
From the initial conditions $a_0 = a_1 = 1$, we obtain $\beta_1 = \frac 13$ and $\beta_2 = \frac 23$. Thus,
$$a_n = \frac 13 \left( (-1)^n + 2^{n+1} \right)$$
