<s>[INST] 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).
 [/INST] 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)$$
</s>