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? 
 A: 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)$$
A: Hint. The characteristic equation is 
$$
(x+1)^2=0
$$ thus the general term of the sequence is
$$
a_n=(\alpha\: n+ \beta)(-1)^n.
$$
Can you take it from here?
A: So we have the following sequence:
$$a_0 = 1$$
$$a_1 = -2$$
$$a_n = -2a_{n-1} - a_{n-2}$$
One way to find the formula is to keep computing successive terms and look for patterns.
However, in this case we have a Fibonacci-like sequence, so we can find a characteristic polynomial for this sequence.
We have that:
$$a_n = -2a_{n-1} - a_{n-2}$$
$$x^2 = -2x - 1$$
$$x^2 + 2x + 1 = 0$$
$$(x+1)^2 = 0$$
We have a double-root, $x = -1$
Therefore, our general answer is:
$$a_n = (-1)^n(an+b)$$
Now, note that the sequence yields $1, -2, 3, -4, \ldots$
This follows an $(n+1)$-like sequence, with an $(-1)^n$ to denote our negative sign.
Thus, the final answer is: 
$$a_n = (-1)^n(n+1)$$
A: Without characteristic equation:
I just conjecture that 
$$a_n=\begin{cases}
n+1,&\text{ if } n \text{ is even}\\
-(n+1),&\text{ if } n \text{ is odd.}
\end{cases}$$
Let me verify my conjecture with mathematical induction:
For $n=2,3$  the inductive hypothesis is true: $a_2=-2\cdot (-2)-1=3$ and $a_3=-6+2=-4$.
Assume now that $n+1 $ is even. The $n$ is odd and $n-1$ is even. So,
$$a_{n+1}=-2\cdot a_n-a_{n-1}=2\cdot (n+1)-n=n+2.
$$
Let $n+1$ be odd. Then $ n$ is even and $n-1$ is odd again. So,
$$a_{n+1}=-2\cdot a_n-a_{n-1}=-2\cdot (n+1)+n=-(n+2).$$
