<s>[INST] $n$-digits numbers made of 1, 2, 3, such that none of two consecutive digits differ by more than one 
We call a number to be good if none of two consecutive digits differ by more than one. How many good $n$-digits numbers made from digits $1$, $2$ and $3$ are there?

For example, $12232$ is good, but $12\textbf{31}2$ isn't.
My idea was to subtract bad numbers made of $1$, $2$ and $3$ (bad numbers are ones that aren't good) from $3^n$ (which represents number of $n$-digit numbers made of $1$, $2$ and $3$).
I tried with representing number $abcd$ ($n=4$) as sequence of 3 ($4-1$) pairs of digits: $(a,b),\text{ }(b,c),\text{ }(c,d)$. Then (I think) we could count number of ways to have at least one of the pairs $(1,3)$ and $(3,1) appearing at least once. But alas...
 [/INST] Let the $n$ digit number be $a_1 a_2 \ldots a_n$. Let $N_1(n)$ be the number of $n$ digit numbers that are good starting with $1$, $N_2(n)$ be the number of $n$ digit numbers that are good starting with $2$ and , $N_3(n)$ be the number of $n$ digit numbers that are good starting with $3$.
We have
\begin{align}
N_1(n) & = N_1(n-1) + N_2(n-1)\\
N_2(n) & = N_1(n-1) + N_2(n-1) + N_3(n-1)\\
N_3(n) & = N_2(n-1) + N_3(n-1)
\end{align}
Hence, we have
$$\begin{bmatrix}N_1(n)\\ N_2(n)\\ N_3(n) \end{bmatrix} = \underbrace{\begin{bmatrix} 1 & 1 & 0\\ 1 & 1 & 1\\ 0 & 1 &1\end{bmatrix}}_A  \begin{bmatrix} N_1(n-1)\\ N_2(n-1)\\ N_3(n-1) \end{bmatrix}$$
Hence,
$$\vec{N}(n+1) = A^n \vec{N}(1)$$
We have $$V = \dfrac12 \begin{bmatrix} 1 & -\sqrt2 & 1\\ -\sqrt2 & 0 & \sqrt 2\\ 1 & \sqrt2 & 1\end{bmatrix}$$ and $$\Lambda = \begin{bmatrix} 1-\sqrt2 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 1 +\sqrt2\end{bmatrix}$$ and $$A = V \Lambda V^T$$
Hence,
$$\vec{N}(n+1) = V \Lambda^n V^T \vec{N}(1)$$
where $$\vec{N}(1) = \begin{bmatrix} 1 \\ 1 \\ 1\end{bmatrix}$$
Hence, the answer is 
\begin{align}
N_1(n) + N_2(n) + N_3(n) & = \begin{bmatrix} 1 & 1 & 1\end{bmatrix} V \Lambda^n V^T \begin{bmatrix} 1 \\ 1 \\ 1\end{bmatrix}\\
& = \dfrac14\begin{bmatrix} 2-\sqrt{2} & 0 & 2+\sqrt{2}\end{bmatrix} \begin{bmatrix} (1-\sqrt2)^{n-1} & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & (1 +\sqrt2)^{n-1}\end{bmatrix}\begin{bmatrix} 2-\sqrt{2} \\ 0 \\ 2+\sqrt{2}\end{bmatrix}\\
& = \dfrac12\begin{bmatrix} \sqrt{2}-1 & 0 & 1+\sqrt{2}\end{bmatrix} \begin{bmatrix} (1-\sqrt2)^{n-1} & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & (1 +\sqrt2)^{n-1}\end{bmatrix}\begin{bmatrix} \sqrt{2}-1 \\ 0 \\ 1+\sqrt{2}\end{bmatrix}\\
& = \dfrac{(1+\sqrt2)^{n+1} + (1-\sqrt2)^{n+1}}2
\end{align}
</s>