$n$-digits numbers made of 1, 2, 3, such that none of two consecutive digits differ by more than one

Question

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...

Answer 1

Let $A_n, B_n, C_n$ be the number of ways an $n-$digit number satisfies the condition, and starts with $1, 2, 3$ respectively. We have $A_1 = B_1 = C_1 = 1$. We are looking for $A_n + B_n + C_n$.

The recurrence relation is $A_{n+1} = A_n + B_n$, $B_{n+1} = A_n + B_n + C_n$, $C_{n+1} = B_n + C_n$. By symmetry, we have $C_n = A_n$.

Claim: $A_n \sqrt{2} +B_n= (\sqrt{2}+1 )^{n+1}$.

Proof: This is true for $n=1$. Proceed by induction to show that the recurrence relation is satisfied. $_\square$

Similarly, $A_n \sqrt{2} - B_n = (\sqrt{2} -1)^{n+1}$. This allows you to obtain closed forms for $A_n$ and $B_n$.

Answer 2

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}