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?

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.
