How to find the general formula for this recursive problem? I want to ask about recursive problem.
Given: $$a_0= 11, a_1= -13,$$ and $$a_n= -a_{n-1} +2a_{n-2}.$$
What is the general formula for $$a_n$$ ?
I've already tried to find the first terms of this series. From there, I got:
$$a_2 = 35, a_3= -61,$$ and $$a_4= 131.$$
From there, I think I need to use the rule from arithmetic and geometric series to find the general formula that I want to find.
But, I cannot find the certain pattern from this series, because the differences is always changing, such that -24, 48, -96, 192. 
From there I think the general formula for a_n should be including (-1)ⁿ. But, how can we deal with series 24,48,96,192?
It seems the series is geometric, but how can we find the formula?
Thanks
 A: Linear Recurrence Equations have typical solutions $a_n=\lambda^n$. Using this, we can compute the possible values of $\lambda$ for this equation from
$$
\lambda^n=-\lambda^{n-1}+2\lambda^{n-2}
$$
which means, assuming $\lambda\ne0$, that
$$
\lambda^2+\lambda-2=0
$$
This is the characteristic polynomial for the recurrence
$$
a_n=-a_{n-2}+2a_{n-2}
$$
The characteristic polynomial is $x^2+x-2$ which has roots $1$ and $-2$. Thus, the sequence is $a_n=b(1)^n+c(-2)^n$. Plugging in the values for $n=0$ and $n=1$ gives
$$
a_n=3+8(-2)^n
$$
A: Let me try. Putting $b_n = a_{n+1} + 2a_n$, for $n \geq 1$, one has $$b_0=9,$$ and $$b_{n-1} = b_{n-2},\ \mbox{ for } n \geq 2.$$
Then one has $b_n = b_0 = 9$, for all $n$.
So, $a_{n+1} + 2a_n = 9,$ for all $n$.
Putting $c_n = a_n - 3$, one has $c_{n+1} + 2c_n = 0$ and $c_0 = 8$.
Thus, $c_n = -2c_{n-1} = (-2)^n c_0 = 8.2^n.(-1)^n$.
We can get $a_n = 8.2^n.(-1)^n + 3$.
EDIT:
The way chooses $b_n$ is a trick. We can solve this problem as follows.
Consider the equation: $a^2+a-2=0$. It has two solutions: $a_1=1$ and $a_2=-2$. Then, $x_n = \alpha a_1^n + \beta a_2^n$. Indeed, one has
$$x_{n+2} + x_{n+1} - 2x_n = \alpha a_1^n(a_1^2+a_1-2) + \beta a_2^n(a_2^2+a_2-2) = 0.$$
Now, we find $\alpha$ and $\beta$.
We have $x_0 = \alpha + \beta = 11$, $x_1 = \alpha - 2\beta = -13$. Then, $\alpha = 3$ and $\beta = 8$. We get $$x_n = 3 + 8(-2)^n$$
A: A useful trick here is to use a generating function.
Let $f(x)=\sum\limits_{n=0}^\infty a_nx^n$. Then we have that $f(x)=a_0+a_1x+\sum\limits_{n=2}^\infty a_nx^n=11-13x+\sum\limits_{n=2}^\infty (-a_{n-1}+2a_{n-2})x^n$. (1) Note that for this last sum: $\sum\limits_{n=2}^\infty (-a_{n-1}+2a_{n-2})x^n=-x\sum\limits_{n=2}^\infty a_{n-1}x^{n-1}+2x^2\sum\limits_{n=2}^\infty a_{n-2}x^{n-2}$. (2) Then, re-indexing the summations yields:
(2) $= -x\sum\limits_{n=1}^\infty a_nx^n+2x^2\sum\limits_{n=0}^\infty a_nx^n=-x\cdot(f(x)-a_0)+2x^2\cdot f(x)$.
Rewriting (1) and solving for $f(x)$ then yields $f(x)=\frac{11-2x}{1+x-2x^2}$. Writing out the Taylor series for this function and equating coefficients will then yield a formula for $a_n$.
A: There are two ways:
Firstly, you could guess the answer. After a bit of investigation, you ca see that  the absolute values of the differences are growing by a factor of two, so we search for a connection between powers of two. And indeed, $a_n=-(-2)^{n+3}+3$ seems to work. We can prove this by induction.
Alternatively, you could try to find all the geometric sequences, which satisfy this recurrence. So assume, $b_n$ is geometric and $b_n=-b_{n-1}+2b_{n-2}$. We can now use the fact, that $b_n=c^nb_0$ for a certain constant $c$ (it is geometric). If we plug this in, we obtain:
$$
b_0c^n=-b_0c^{n-1}+2b_0c^{n-2}\iff c^2=-c+2\iff (c+2)(c-1)=0
$$
So either $c=-2$ or $c=1$. So we know, that every sequence of the form $p_n=p_0(-2)^n$ and $q_n=q_0(1)^n=q_0$ has the desired property. Furthermore, even the linear combinations of $p_n$ and $q_n$ have the desired property. So we have to find $p_0$ and $q_0$ such that:
$$
a_n=p_n+q_n\implies 11=a_0=p_0+q_0\space\text{and}\space -13=a_1=-2p_0+q_0
$$
We can solve these two equations to obtain $p_0=8$ and $q_0=3$ which yields $a_n=8(-2)^n+3=-(-2)^{n+3}+3$. Note, that this approach works generally for recurrence relations of the form $a_n=\lambda a_{n-1}+\mu a_{n-2}$.
