<s>[INST] Find the formula for the sequence $a(n)$ Find the formula for the sequence $a(n)$ given by the following recurrence relations and prove that the formula is correct:
$a(0) = 1, ~a(1) = -2,~ a(n) = -2a(n-1)-a(n-2)$
How to solve it? I don't know how to start? 
 [/INST] Let $$f(x) = \sum_{n = 0}^\infty a_nx^n$$ be the generating function for the sequence $\left\{a_n\right\}_{0}^\infty$. Then
$$\begin{align}f(x) &= a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 + \dots \\
&= 1 -2x + (-2a_1 - a_0)x^2 + (-2a_2 - a_1)x^3 + (-2a_3 - a_2)x^4 + \dots\\
&= 1 - 2x + (-2x)(f(x) - a_0) + (-x^2)f(x)\\
&= 1 - 2x + 2x - 2xf(x) - x^2f(x)\\
&=1 - 2xf(x) - x^2f(x)\end{align}$$
so that with some rearrangement,
$$f(x) + 2xf(x) + x^2f(x) = 1$$
$$(1 + 2x + x^2)f(x) = 1$$
$$\begin{align}f(x) &= \frac{1}{1 + 2x + x^2}\\
&=\frac{1}{(1 + x)^2}\end{align}$$
But we know that
$$\frac{1}{1 + x} = 1 - x +x^2 - x^3 + x^4 - \dots$$
Differentiating both sides,
$$-\frac{1}{(1 + x)^2} = -1 + 2x - 3x^2 + 4x^3 - \dots$$
$$f(x) = \frac{1}{(1 + x)^2} = 1 - 2x + 3x^2 - 4x^3 + \dots$$
$$a_0 + a_1x + a_2x^2 + a_3x^3 + \dots = 1 - 2x + 3x^2 - 4x^3 + \dots$$
Hence, by comparing the coefficients directly,
$$a_n = (-1)^n (n + 1)$$
</s>