Given $x_1=1,x_2=2,x_{n+2}=3x_{n+1}-x_n\forall n\in\mathbb N$. Find $x_n$. 
Given $x_1=1,x_2=2,x_{n+2}=3x_{n+1}-x_n\forall n\in\mathbb N$. Find $x_n$.

I tried to find ways to telescope, but failed. Please help. Thank you.
 A: There is a general way to solve those type of recurrences, through the characteristic polynomial of the relation.
$$
x_{n+2}+ax_{n+1}+bx_{n} = 0 \leadsto X^2+aX+b=0
$$
Here, it'd be $X^2-3X+1$. The roots are $\phi=\frac{3+\sqrt{5}}{2}$ and $\bar{\phi}=\frac{3-\sqrt{5}}{2}$.Any solution $(x_n)_{n\in\mathbb{N}^\ast}$ is of the form $x_n = \alpha \phi^{n-1} + \beta \phi^{n-1}$ (since the two roots ${\phi},\bar{\phi}$ are distinct). Then use the initial conditions $x_1$ and $x_2$ to get $\alpha,\beta$.
A: The set of sequences of complex numbers (actually any field, but let's keep things simple) $(x_n)$ satisfying
$$
\begin{cases}
x_0=a\\
x_1=b\\
x_{n+2}=rx_{n+1}+sx_{n}
\end{cases}
$$
can be made into a vector space by defining addition componentwise and multiplication by scalars as multiplying each term by the scalar. Since a sequence is determined as soon as the $0$ and $1$ term are fixed, this vector space has dimension $2$.
Let's try finding two linearly independent sequences in it, by first looking at the simplest kind, that is, geometric progressions. So, when does the sequence $(t^n)$ belong to the vector space? It should satisfy
$$
t^{n+2}=rt^{n+1}+st^n
$$
for all $n$, in particular for $n=0$, that is,
$$
t^2-rt-s=0.
$$
Conversely, if $t$ satisfies this equation, the corresponding geometric progression belongs to the vector space.
If the polynomial $X^2-rX-s$ has distinct roots $\alpha$ and $\beta$, we want to show that the sequences $(\alpha^n)$ and $(\beta^n)$ are linearly independent. If
$$
p(\alpha^n)+q(\beta^n)=(0)
$$
where $(0)$ denotes the constant zero sequence, we have, in particular
$$
\begin{cases}
p+q=0\\
p\alpha+q\beta=0
\end{cases}
$$
and the determinant of the system is
$$
\det\begin{bmatrix}1 & 1\\\alpha&\beta\end{bmatrix}=\beta-\alpha\ne0,
$$
so the system has a unique solution, with $p=q=0$.
Therefore, for any sequence $(x_n)$ in the vector space there are coefficients $p$ and $q$ such that
$$
x_n=p\alpha^n+q\beta^n \qquad \text{for all $n\ge0$}
$$
and $p$ and $q$ can be uniquely determined by plugging in the given values for $x_0$ and $x_1$.
If the polynomial has only one (double) root $\alpha$, then we can see that the sequences $(\alpha^n)$ and $(n\alpha^n)$ are linearly independent: the linear system to look at is
$$
\begin{cases}
p=0\\
p\alpha+q\alpha=0
\end{cases}
$$
that surely is satisfied for $p=q=0$. Notice that $\alpha\ne0$, unless the recurrence is the trivial one $x_{n+2}=0$.
Of course this can be generalized to any linear recurrence equation.
