<s>[INST] Express the sequence $\{x_n\}$ where $x_n = 2x_{n-1} + 3x_{n-2}$ in terms of ${x_0, x_1, n}$ Given a sequence $\{x_n\}$ where $x_n = 2x_{n-1} + 3x_{n-2}$ how can one express it in terms of ${x_0, x_1, n}$. Can this be generalized for ${x_n = \alpha x_{n-1} + \beta x_{n-2}}$
I've tried to use the following approach:
$$\eqalign{
 & 1x_0 = x_01 \\
 & zx_1 = x_1z \\
 & z^2x_2 = (2x_1 + 3x_0)z^2 \\
 & z^3x_3 = (2x_2 + 3x_1)z^3 \\
 & z^4x_4 = (2x_3 + 3x_2)z^4 \\
 & ... \\
 & z^nx_n = (2x_{n-1} + 3x_{n-2})z^n
}$$
Then sum LHS with RHS which will produce:
$${
x_0 + \sum\limits_{k = 1 }^na_nz^n = x_0 +zx_1 + 2\sum\limits_{k = 2}^nx_{n-1}z^n + 3 \sum\limits_{k = 2}^n x_{n-2}z^n
}$$
Let 
$${
G(z) = x_0 + \sum\limits_{k = 1 }^na_nz^n
}$$
Then RHS may be expressed in terms of ${G(z)}$. For example 
$${
2\sum\limits_{k = 2}^na_{n-1}z^n = 2z\sum\limits_{k = 2}^na_{n-1}z^{n-1} = 2z(\sum\limits_{k = 1}^na_{n}z^{n} + x_0 - x_0) = 2z(G(z) - x_0)
}$$
Applying those transformations I eventually got ${G(z)}$ expressed in terms of z and ${x_1, x_0}$. But at this point I got stuck.
I got a sum of fractions:
$${
\frac{3x_0 - x_1}{4(1+z)}+\frac{x_0+x_1}{4(1-3z)}
}$$
I guess i could expand the fractions into series and find their sum, but i am not supposed to know about such expansions at the point of the book i took the problem from.
All of the above feels like a wrong approach. So the question is whether this can be done in a more elegant way.
 [/INST] Consider the matrix:
$$ X_n =
\begin{bmatrix}
x_{n+2} & x_{n+1} \\
x_{n+1} & x_{n}
\end{bmatrix}
$$
Then there is a recurrence relation:
$$X_{n+1} = 
X_n
\begin{bmatrix}
2 & 1 \\
3 & 0
\end{bmatrix}
$$
So we may say that
$$X_{n} = X_0
\begin{bmatrix}
2 & 1 \\
3 & 0
\end{bmatrix}^{n} = X_0A^n$$
Through whatever method you'd like to use, realize the eigenvectors of $A$ are $(-1, 3)$ and $(1, 1)$, with values $-1$ and $3$. Thus through a change of basis,
$$A =
\begin{bmatrix}
-1 & 1 \\
3 & 1
\end{bmatrix}
\begin{bmatrix}
-1 & 0 \\
0 & 3
\end{bmatrix} 
\begin{bmatrix}
-1 & 1 \\
3 & 1
\end{bmatrix}^{-1}
=
\begin{bmatrix}
-1 & 1 \\
3 & 1
\end{bmatrix}
\begin{bmatrix}
-1 & 0 \\
0 & 3
\end{bmatrix} 
\begin{bmatrix}
-1/4 & 1/4 \\
3/4 & 1/4
\end{bmatrix}
$$
and
$$
A^n =
 \begin{bmatrix}
-1 & 1 \\
3 & 1
\end{bmatrix}
\begin{bmatrix}
-1 & 0 \\
0 & 3
\end{bmatrix}^n
\begin{bmatrix}
-1/4 & 1/4 \\
3/4 & 1/4
\end{bmatrix}
=
\begin{bmatrix}
-1 & 1 \\
3 & 1
\end{bmatrix}
\begin{bmatrix}
(-1)^n & 0 \\
0 & 3^n
\end{bmatrix}
\begin{bmatrix}
-1/4 & 1/4 \\
3/4 & 1/4
\end{bmatrix}
 $$
Finally, let $x_0 = 0$ (or whatever, it don't matter) so that
$$
X_0=
\begin{bmatrix}
x_2 & x_1 \\
x_1 & x_0
\end{bmatrix}$$
Then multiplying, (the top-right and bottom-left elements are actually equal)
$$
X_n=
\begin{bmatrix}
\dfrac{3^{n+1}(x_2 + x_1) - (-1)^{n}(3x_1 - x_2)}{4} & \dfrac{3^{n}(x_2 + x_1) + (-1)^{n}(3x_1 - x_2)}{4} \\
\dfrac{3^{n+1}(x_1 + x_0) - (-1)^{n}(3x_0 - x_1)}{4} & \dfrac{3^{n}(x_1 + x_0) + (-1)^{n}(3x_0 - x_1)}{4}
\end{bmatrix}
$$
The bottom right element is $x_n$. Thus,
$$x_n = \frac{3^{n}(x_1 + x_0) + (-1)^{n}(3x_0 - x_1)}{4}$$
</s>