<s>[INST] p(n) is count of all n-digit numbers... Let $n$ be an arbitrary positive integer, and $p(n)$ be the number of $n$-digit numbers which consist only of the digits $1,2,3,4,5$, and in which each two neighbour digits differ by $2$ or more.
My task is to prove that this inequality is true for any positive integer $n$:
$$\ 5 \cdot (2,4)^{n-1} ≤ p(n) ≤ 5 \cdot (2,5)^{n-1} $$
Any ideas?
 [/INST] Just an idea (not a complete answer).  Let $p_k(n)$ be the number of $n$-digit numbers of the requested form that end in the digit $k$.  Then $p_k(1) = 1$ for all $k \in \{1, \dotsc, 5\}$ and $p_k(n+1)$ can be computed recursively by
$$
\begin{pmatrix}
p_1(n+1) \\
p_2(n+1) \\
p_3(n+1) \\
p_4(n+1) \\
p_5(n+1)
\end{pmatrix} = \begin{pmatrix}
0 & 0 & 1 & 1 & 1 \\
0 & 0 & 0 & 1 & 1 \\
1 & 0 & 0 & 0 & 1 \\
1 & 1 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 0
\end{pmatrix} \begin{pmatrix}
p_1(n) \\
p_2(n) \\
p_3(n) \\
p_4(n) \\
p_5(n)
\end{pmatrix}
$$
The largest eigenvalue of the matrix on the left is $\approx 2.48$ for a strictly positive eigenvector.  Not all other eigenvalues have norm less than $1$ though, so a more refined argument is still needed.
</s>