<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] Use generating functions. Define $g(z) = \sum_{n \ge 0} x_n z^n$, take the recurrence shifted by 2, multiply by $z^n$ and sum over $n \ge 0$, recognize resulting sums:
$\begin{align*}
  \sum_{n \ge 0} x_{n + 2} z^n
    &= 2 \sum_{n \ge 0} x_{n + 1} z^n + 3 \sum_{n \ge 0} x_n z^n \\
  \frac{g(z) - x_0 - x_1 z}{z^2}
    &= 2 \frac{g(z) - x_0}{z} + 3 g(z)
\end{align*}$
Solve for $g(z)$, write as partial fractions; extract coefficient of $z^n$:
$\begin{align*}
  g(z)
    &= \frac{x_0 + (x_1 - 2 x_0) z}{1 - 2 z - 3 z^2} \\
    &= \frac{x_0 + x_1}{4 (1 - 3 z)} + \frac{3 x_0 - x_1}{4 (1 + z)} \\
  x_n
    &= [z^n] g(z) \\
    &= \frac{x_0 + x_1}{4} \cdot 3^n + \frac{3 x_0 - x_1}{4} \cdot (-1)^n
\end{align*}$
The last because the series is:
$\begin{align*}
  \sum_{n \ge 0} a^n z^n
    &= \frac{1}{1 - a z}
\end{align*}$
</s>