Solving a recurrence relation of second order I have a pattern, which goes: $x_n =2(x_{n-1}-x_{n-2})+x_{n-1}$ and this pattern holds for all $n \ge 2$. I also know that $x_0 = 1 \ and \ x_1 = 5.$
$x_2 = 2(x_1-x_0)+x_1$
$\begin{align}
x_3 = 2(x_2-x_1) + x_2 &= 2(2(x_1-x_0)+x_1)+x_2\\
&=2^2x_1-2^2x_0+2x_ 1+x_2
\end{align}$
$\begin{align}
x_4 = 2(x_3-x_2)+x_3 &= 2(2^2x_1-2^2x_0+2x_1+x_2-(2(x_1-x_0)+x_1)+x_2)+x_3 \\
&=2^3x_1-2^3x_0+2^2x_1+2x_2-(2x_1-2x_0+x_1)+x_2)+x_3 \\
&=2^3x_1-2^3x_0+2^2x_1+2x_2 - 2x_1 +2x_0-x_1+x_2+x_3 \\
&=2^2x_1-2^2x_0+2x_1+2^2x_2+x_3
\end{align}$
(The formula below is no longer valid, I noticed since last edit)
$[x_n = 2^{n-1}(x_1-x_0) + \sum^{n-1}_{i=0}(2^{n-2-i}x_i)]$
Well, here I'm confused; there's no pattern to be found anymore, or am I just blind?
 A: Let's write the formula as $x_n = 3x_{n-1} - 2x_{n-2}$. 
This is a linear homogeneous recurrence relation with constant coefficients. 
The characteristic equation is $\lambda^2 - 3\lambda + 2 = 0$, i.e. $(\lambda-2)(\lambda-1) = 0$. 
The roots are $\lambda_1 = 2$ and $\lambda_2 = 1$, so the general solution is $x_n = C_1\lambda_1^n + C_2\lambda_2^n = C_1 \cdot 2^n + C_2$. 
Using the initial conditions $x_0 = 1$ and $x_1 = 5$, we get: 
$x_0 = C_1+C_2 = 1$
$x_1 = 2C_1+C_2 = 5$
Solving gives us $C_1 = 4$ and $C_2 = -3$. 
Therefore, the specific solution (based on the initial conditions) is $x_n = 4\cdot 2^n - 3$. 
A: Since I'm a fan of generating-function methods, I'll demonstrate how that works here. (It'll prove to be overkill, but it's perfectly straightforward). Let $X(t)=\sum_{n=0}^\infty x_n t^n$, which is the formal power series in $t$ with coefficients. We have the recurrence relation $x_n=2(x_{n-1}-x_{n-2})+x_{n-1}=3x_{n-1}-2x_{n-2}$. Since this is valid for $n\geq 2$, let's focus on the terms in $X(t)$ of at least quadratic order; with this in mind we may write
\begin{align}
X(t)-x_0-x_1 t
&=\sum_{n=2}^\infty x_{n}t^n\\
&=\sum_{n=2}^\infty 3x_{n-1}t^n-\sum_{n=2}^\infty 2x_{n-2}t^n\quad(\text{recurrence relation})\\
&=3t\cdot\sum_{n=1}^\infty x_{n}t^n-2t^2\cdot \sum_{n=0}^\infty x_{n}t^n\quad(\text{by shifting indices})\\
&=3t(X(t)-x_0)-2t^2 X(t)
\end{align}
which we may rearrange to solve for $X(t)$ as $$(1-3t+2t^2)X(t)=x_0+(x_1-3x_0)t\implies X(t)=\frac{1+2t}{(1-t)(1-2t)}$$
where we have plugged in $(x_0,x_1)=(1,5)$. To read off series coefficients we expand in partial fractions as 
$$X(t)=\frac{1+2t}{(1-t)(1-2t)}=\frac{4(1-t)-3(1-2t)}{(1-t)(1-2t)}=\frac{4}{1-2t}-\frac{3}{1-t}$$
and since these are geometric series we immediately have $\boxed{x_n=4\cdot 2^n-3}$ which matches the first solution.
A: Here is another answer which uses a trick special to this problem. Note that the recurrence may be written as $x_n-x_{n-1}=2(x_{n-1}-x_{n-2})$ for $n\geq 2$. So the difference in terms is doubling at each step, and if we iterate this we come to $x_n-x_{n-1}=2^{n-1}(x_1-x_0)=2^{n+1}$ since $x_1-x_0=4$. So we can solve the recurrence $x_n=x_{n-1}+2^{n+1}$ instead (valid for $n\geq 1$). But this iterates to
\begin{align}
x_n
&=x_{n-1}+2^{n+1}\\
&=x_{n-2}+2^n+2^{n+1}\\
&\cdots\\
&=x_0+2^2+2^3+\cdots +2^{n+1}\\
&=1+4\cdot(2^{n}-1)\\
&=4\cdot 2^{n+2}-3
\end{align}
which is the same answer as in the other solutions.
