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?
 A: 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.
A: Here's a second approach, depending more on algebra and less on analysis.
Recall that $p(n)$ counts how many permitted $n$-digit numbers can be formed from {1,2,3,4,5} such that adjacent digits differ by at least two.  Note that $p(n)$ is a positive integer for each positive integer $n$.
First we will show that $p(n)$ satisfies the following linear recurrence relation:
$$p(n+1) = 2p(n) + 2p(n-1) - 2p(n-2)$$
Then we will use induction to prove for $n = 1,2,3,\dots$ :
$$ 2.4 \le p(n+1)/p(n) \le 2.5 $$
From $p(1) = 5$ it follows that $5 \cdot 2.4^{n-1} \le p(n) \le 5 \cdot 2.5^{n-1}$.
Recurrence relation:
Consider expressing $p(n) = (p_1(n)+p_5(n)) + (p_2(n)+p_4(n)) + p_3(n)$ where as before $p_d(n)$ denotes the count of permitted numbers with leading digit $d$.
The point of lumping $p_1(n)$ and $p_5(n)$ together (resp. $p_2(n)$ and $p_4(n)$) is that the transition rules are simplified when numbers are so grouped.  Instead of a $5 \times 5$ transition matrix, we need only a $3 \times 3$ matrix:
$$ p(n) = (1\;1\;1) \begin{pmatrix} 1&1&2\\1&1&0\\1&0&0 \end{pmatrix}^{n-1}
 \begin{pmatrix} 2\\2\\1 \end{pmatrix} $$
Let me decode the transition matrix $A$ shown here.  How many ways are there to get a permitted $n$-digit number with a leading 1 or 5?  For each permitted $n-1$-digit number, there is one way to thus extend it if it began with 1 or 5 (by prefixing the alternative), one way to extend if it began with 2 or 4, and two ways to extend if it began with 3.  Similarly to get a permitted $n$-digit number with a leading 2 or 4, there's one way to extend a prior digit 1 or 5, one way to extend a 2 or 4, and no way to extend a 3.  Finally there is only one way to extend to a permitted number with leading 3, and that requires the prior digit to be 1 or 5.
The linear recurrence relation is now an easy consequence of $A$ satisfying characteristic polynomial $| \lambda I - A| = \lambda^3 - 2 \lambda^2 - 2 \lambda +2 $.
Bounds by Induction:
Let's begin by noting some of the initial ratios $p(n+1)/p(n)$.
$$ \begin{array}{cl} \underline{ n } & p(n+1)/p(n)
\\ 1 & 2.4
\\ 2 & 2.5
\\ 3 & 2.4\overline{6}
\\ 4 & 2.4\overline{864}
\\ 5 & 2.47826086956522\ldots
\\ 6 & 2.48245614035088\ldots
\\ 7 & 2.4\overline{814}
\end{array} $$
Certainly the ratios appear to settle into the interval $[2.4,2.5]$.  In any case the values shown will serve as our basis step for induction.
Suppose for the sake of generality that we know bounds:
$$a \le p(n)/p(n-1), p(n-1)/p(n-2) \le b$$
for positive constants $a,b$.  The obvious manipulation of inequalities yields:
$$ b^{-1} \le p(n-1)/p(n) \le a^{-1} $$
$$ b^{-2} \le p(n-2)/p(n) \le a^{-2} $$
Applied to an immediate implication of the recurrence relation:
$$ p(n+1)/p(n) = 2(1 + p(n-1)/p(n) - p(n-2)/p(n)) $$
one obtains the successive bounds:
$$ 2(1 + b^{-1} - a^{-2}) \le p(n+1)/p(n) \le 2(1 + a^{-1} - b^{-2}) $$
Now if we set $a = 2.47$ and $b = 2.49$, the bounds evaluate to:
$$ 2.475\ldots \le  p(n+1)/p(n) \le 2.487\ldots $$
Combining the table entries with this induction step for $n \ge 6$ thus proves the sought bounds $2.4 \le p(n+1)/p(n) \le 2.5$ for all positive integers. 
