Problem solving recurrence equation for $a_n = a_{n-1} + 2a_{n-2}, \,\,\, a_0=a_1=1$

Question

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

Answer 1

I corrected the mistake in the second line of the calculations and got the following:

$$\Longrightarrow \sum_{n=2}^{\infty}a_{n}x^{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_{n}x^{n} = x\sum_{n=1}^{\infty}a_{n}x^{n} + 2x^2\sum_{n=0}^{\infty}a_{n}x^{n}$$

$$\Longrightarrow A(x) - x - 1= x(A(x)-1) + 2x^2A(x)$$

$$ \Longrightarrow A(x) = \frac{-1}{2x^2 + x -1 } = -\frac{2}{3} \cdot \frac{1}{2x - 1} + \frac{1}{3} \cdot \frac{1}{x + 1}$$

Which gives me the series expansion:

$$ A(x) = -\frac{2}{3}\sum_{n = 0}^{\infty} -2^{n}x^n + \frac{1}{3} \sum_{n=0}^{\infty} (-1)^nx^n$$

$$ = \sum_{n = 0}^{\infty} \frac{1}{3} ( 2^{n+1} + (-1)^n)x^n $$

$$\Longrightarrow \forall n \in \mathbb{N}: a_n = \frac{1}{3} ((-1)^n + 2^{n+1})$$

Which works. Thank you, guys.

Answer 2

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