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.
 A: Solving recurrence relations is actually very similar to solving ODEs. For simplicity, lets stick with the general second order recurrence relation
$$a_n=\alpha a_{n-1}+\beta a_{n-2}$$
Firstly, observe that if $a_n=f(x_0,x_1,n)$ and $a_n=g(x_0,x_1,n)$ are both solutions, then $a_n=(f+g)(x_0,x_1,n)$ is also a solution.
Now, we guess the solution $a_n=\lambda^n$ for some constant $\lambda$ to be determined. Plugging this in:
\begin{align}
\ & a_n=\alpha a_{n-1}+\beta a_{n-2} \\
\ \implies & \lambda^n=\alpha \lambda^{n-1}+\beta \lambda^{n-2} \\
\ \implies & \lambda^2-\alpha\lambda-\beta=0
\end{align}
i.e. $\lambda$ is a root to this quadratic. Let the two roots of this quadratic be $\lambda_1$ and $\lambda_2$. Then the general solution would be
$$a_n=A\lambda_1^n+B\lambda_2^n$$
where the constants $A$ and $B$ are to be determined by the initial conditions. As per your question with the general case, if $a_0=a_0$ and $a_1=a_1$, then we have
$$a_0=a_0 \implies a_0=A+B$$
$$a_1=a_1 \implies a_1=A\lambda_1+B\lambda_2$$
and we solve for $A$ and $B$ from here.

In your example where you had the recurrence relation
$$a_n=2a_{n-1}+3a_{n-2}$$
By guessing the solution $a_n=\lambda^n$, we arrive at the quadratic
$$\lambda^2-2\lambda-3=0$$
giving the roots $\lambda_1=3$ and $\lambda_2=-1$. Thus, the general solution is
$$a_n=A\cdot 3^n+B\cdot (-1)^n$$
Plugging in $n=0$ and $n=1$, we get
$$a_0=A+B \qquad a_1=3A-B$$
Hence $A=\frac{a_0+a_1}{4}$ and $B=\frac{3a_0-a_1}{4}$, giving
$$a_n=\frac{a_0+a_1}{4}\cdot 3^n+\frac{3a_0-a_1}{4}\cdot (-1)^n$$
A: Let $f(x)$ be the generating function for some sequence $(a_{n})_{n\in\mathbb{N}}$ such that 
    \begin{align*}
  f(x)=\frac{c}{bx+d}=\sum^{\infty}_{n=0}{a_{n}x^{n}},\ c,b,d\in\mathbb{Z}.\tag{1}
 \end{align*} 
Then
\begin{alignat*}{3}
  f(x)=\frac{c}{bx+d}&\implies f^{\prime}(x)                       &&=-1!\left(\frac{b}{c}\right)^{1}f(x)^{2}\\
                               &\implies f^{\prime\prime}(x)             &&=+2!\left(\frac{b}{c}\right)^{2}f(x)^{3}\\
                               &\implies f^{\prime\prime\prime}(x)   &&=-3!\left(\frac{b}{c}\right)^{3}f(x)^{4}\\
                               &\qquad                                            &&\vdots\\
                               &\implies f^{n}(x)                               &&=(-1)^{n}n!\left(\frac{b}{c}\right)^{n}\big(f(x)\big)^{n+1},
 \end{alignat*}
where $f^{n}(x)$ denotes the $n^{\text{th}}$ derivative of $f$ with respect to $x.$ If we evaluate $f^{n}(0)$, the Maclaurin series expansion of $f(x)$ is then given by
\begin{alignat*}{4}
   &\qquad \qquad \qquad \qquad \quad f^{n}(0)&&=(-1)^{n}n!\left(\frac{b}{c}\right)^{n}f(0)^{n+1}\\
   &              &&=(-1)^{n}n!\left(\frac{b}{c}\right)^{n}\left(\frac{c}{d}\right)^{n+1}\\
   &\qquad \qquad \qquad \quad \implies f(x)        &&=\sum_{n=0}^{\infty }c\ (-1)^{n}\left(\frac{1}{d}\right)^{n+1}{b^{n}x^{n}}.\tag{2}\\
     \end{alignat*}
It follows from (1) and (2) that the explicit form of the sequence $(a_{n})_{n\in\mathbb{N}}$ is given by
 \begin{align*}a_{n}=c\ (-1)^{n}\left(\frac{1}{d}\right)^{n+1} b^{n}.\tag{3}\\ \end{align*}
If we let $c=x_{0}+x_{1},\ b=-12,$ and $d=4$, as in (1) then 
\begin{alignat*}{3}
  g(x)=\frac{x_{0}+x_{1}}{4-12z}&\overset{(3)}{\implies} g_{n}&&=(-1)^{n}(x_{0}+x_{1})(-12)^{n}\left(\frac{1}{4}\right)^{n+1}\\
                               &\qquad              &&=(x_{0}+x_{1})(-1)^{n}(-1)^{n}(3)^{n}(4)^{n}\left(\frac{1}{4}\right)^{n}\left(\frac{1}{4}\right)\\
                               &\ \implies g_{n}          &&=\left(\frac{1}{4}\right)3^{n}(x_{0}+x_{1}).\tag{4}
 \end{alignat*}
Similarly
\begin{alignat*}{3}
  h(x)=\frac{3x_{0}-x_{1}}{4+4z}&\overset{3}{\implies} h_{n}&&=(-1)^{n}(3x_{0}-x_{1})(4)^{n}\left(\frac{1}{4}\right)^{n+1}\\
                               &\qquad              &&=(3x_{0}-x_{1})(-1)^{n}(4)^{n}\left(\frac{1}{4}\right)^{n}\left(\frac{1}{4}\right)\\
                               &\ \implies h_{n}          &&=(-1)^{n}\left(\frac{1}{4}\right)(3x_{0}-x_{1}).\tag{5}\\
 \end{alignat*}
It follows from the linearity of differentiation, (superposition principle), that we may combine (4) and (5) to obtain the desired formula for $x_{n}$. Whence,
\begin{align}x_{n}=\left(\frac{1}{4}\right)3^{n}(x_{0}+x_{1})+ (-1)^{n}\left(\frac{1}{4}\right)(3x_{0}-x_{1})\tag*{$\square$}\end{align}
A: 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}$$
A: 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*}$
