A recurrence system and Markov chain. I have troubles understanding the solution for the following exercise. It's about markov chain, but the part I don't understand is rather algebraic and about a recurrence system.

Exercise: Let $p \in ]0,1[$ and $(X_n)_{n\geq 0}$ be a Markov chain on $E=\{a,b,c\}$ with transition Matrix
  $$Q:=\begin{pmatrix}1-p &p &0\\1/2&0&1/2\\0&0&1
\end{pmatrix}$$
  Compute the probabillity $P(X_n=b\mid X_0=a),\ n\in\mathbb{N}$ and find it's limit for $n\to \infty$
Solution: The graph looks like this:

First notice $Q_n=Q\cdot Q_{n-1}\quad \forall n\geq 1$. In particular $a_n:=P(X_n=b\mid X_0=a)$ and $b_n:=P(X_n=b\mid X_0=b)$ then
  $$\begin{cases}a_n=(1-p)a_{n-1}+pb_{n-1}\\ b_n=\frac{1}{2}a_{n-1}\end{cases}$$
  Thus $(a_n)_{n\geq 0}$ is
  $$\begin{cases}a_n-(1-p)a_{n-1}-\frac{p}{2}a_{n-2}=0,\quad n\geq 2,\\ a_0=0,\ a_1=p\end{cases}$$

Here is the part I don't understand. I have no clue how to solve this recurrence system. I've never did this before.

Solution: Hence $$a_n=p\frac{(1-p+\sqrt{1+p^2})^n-(1-p-\sqrt{1+p^2})^n}{2^n\sqrt{1+p^2}}$$
  And find $a_n\to 0$.

How do I get to that result? I tried
$$a_n-(1-p)a_{n-1}-\frac{p}{2}a_{n-2}=a_n-(1-p)a_{n-1}-\frac{p}{2}\left((1-p)a_{n-2}-\frac{p}{2}a_{n-3}\right)=0$$
But I fail miserably. (I also find the solution quite not so "probabilistic", is this the only possible way to compute this?)
 A: Hint: Check Recurrence relation to solve this linear recurrence relation.
Also, note that the given Markov chain is absorbing, with $ c $ being an absorbing state,
while $ a,b $ are transient states. Thus, $ \lim_{n\to \infty} P(X_n=b|X_0= a) = 0 $.
A: So we have:
$${\bf Q}=\begin{pmatrix}1-p &p &0\\1/2&0&1/2\\0&0&1
\end{pmatrix}$$
Having a probability distribution row vector $\bf v$, the probability after a hop in the chain will be:
$$\bf vQ$$
Analogously, after $n$ hops:
$${\bf vQ}^n$$
Now consider the vector $\bf v$ representing some probability distribution a priori. If we know the state is $a$, then ${\bf v} = [1,0,0]$, 100 % chance for first state? Then analogously for state $b$ : ${\bf v} = [0,1,0]$, because 100% chance for second state. Okay so far?
Now what remains is to try and express ${\bf vQ}^n$ in some simpler way. We can do this with an eigenvalue decomposition : $${\bf Q = S}^{-1}{\bf DS}  $$ where $\bf D$ is diagonal, containing the eigenvalues $\lambda_1,\lambda_2,\lambda_3$, and $\bf S$ contains the corresponding eigenvectors as columns.
$${\bf Q}^n = {\bf S}^{-1}{\bf D}^n{\bf S}$$
Here the ${\bf D}^n$ is much nicer to calculate than a general matrix power.
What is required to find the values in the $\bf D$ matrix (the $\lambda$s) this is to solve the equation:
$$\det ({\bf Q}-\lambda {\bf I}) = 0 \Leftrightarrow \left|\begin{pmatrix}1-p-\lambda &p &0\\1/2&-\lambda&1/2\\0&0&1-\lambda
\end{pmatrix}\right|=0$$
Now this is a third order polynomial (in $\lambda$) which we leave as an exercise:
$$(1-p-\lambda)(-\lambda)(1-\lambda) - p/2(1-\lambda) = 0$$
If you solve it you will find the eigenvalues to be very resemblant to the expressions in your book and then you are almost done.
