The number of possible integers proof Let p(n) be the number of possible n-digit integers which can be made from digits 1,2,3,4,5 and which every two neighbor digits differ with number at least 2. (their difference is at least 2, for example 1352 / 1 3 2 5 no).
Prove that for every integer n: $5⋅2.4^{n-1}\le p(n)\le 5⋅2.5^{n-1}$
I've been thinking about it so much but can't come to the solution.
 A: A basic linear algebra approach to starting such a problem.
If you let $p_i(n)$ be the count of such nymbers with first digit $i$, for $i=1,2,3,4,5$, then you can show that $p_1(n)=p_5(n)$ and $p_2(n)=p_4(n)$ and $p(n)=2p_1(n)+2p_2(n)+p_3(n)$, and, in general, get:
$$\left(\begin{matrix} p_1(n)\\p_2(n)\\p_3(n)\end{matrix}\right)=\left(\begin{matrix}1&1&1\\1&1&0\\2&0&0\end{matrix}\right)^{n-1}\left(\begin{matrix} 1\\1\\1\end{matrix}\right)$$
The eigenvalues of this matrix are all real, being, approximately, $-1.17,0.69$ and $2.48$.
It's clear that the larger eigenvalue is a factor here, so we know that $p(n)$ is dominated by some constant times $2.48^n$.
Not sure if that helps any, however. It was just too long for a comment.
A: The numbers $p(n)$ satisfy the recurrence
$$p(n+1)=2\Big(p(n)+p(n-1)-p(n-2)\Big)\tag{1}$$
with initial conditions $p(1)=5,p(2)=12$, and $p(3)=30$.

Added: Using the notation of Thomas Andrews’ answer, we have $$\begin{align*}p(n+1)&=2p_1(n+1)+2p_2(n+1)+p_3(n+1)\\&=2\big(p_1(n)+p_2(n)+p_3(n)\big)+2\big(p_1(n)+p_2(n)\big)+2p_1(n)\\&=2\Big(2p_1(n)+2p_2(n)+p_3(n)\Big)+2p_1(n)\\&=2p(n)+2p_1(n)\;,\end{align*}$$ so it suffices to show that $p_1(n)=p(n-1)-p(n-2)$. 
And $$\begin{align*}p_1(n)&=p_1(n-1)+p_2(n-1)+p_3(n-1)\\&=p(n-1)-\big(p_1(n-1)+p_2(n-1)\big)\\&=p(n-1)-\Big(\big(p_1(n-2)+p_2(n-2)+p_3(n-2)\big)+\big(p_1(n-2)+p_2(n-2)\big)\Big)\\&=p(n-1)-\Big(2p_1(n-2)+2p_2(n-2)+p_3(n-2)\Big)\\&=p(n-1)-p(n-2)\;,\end{align*}$$ and $(1)$ is established.

For $n\ge 1$ let $d_n=\dfrac{p(n+1)}{p(n)}$; clearly $p(1)=\dfrac{12}5=2.4$ and $p(2)=\dfrac{30}{12}=2.5$. Now assume that $n\ge 3$ and $$\frac{12}5\le d_k\le\frac52$$ for $1\le k<n$. Then
$$\begin{align*}
d_n&=\frac{p(n+1)}{p(n)}\\\\
&=2+\frac{2p(n-1)-2p(n-2)}{p(n)}\\\\
&=2+\frac2{d_{n-1}}-\frac{2p(n-2)}{p(n-1)}\cdot\frac{p(n-1)}{p(n)}\\\\
&=2+\frac2{d_{n-1}}-\frac2{d_{n-1}d_{n-2}}\\\\
&=2+\frac2{d_{n-1}}\left(1-\frac1{d_{n-2}}\right)\;.
\end{align*}$$
Now $$\frac7{12}\le 1-\frac1{d_{n-2}}\le\frac35\quad\text{and}\quad\frac45\le\frac2{d_{n-1}}\le\frac56\;,$$
so $$2.4<2+\frac7{15}=2+\frac7{12}\cdot\frac45\le d_n\le 2+\frac35\cdot\frac56=\frac52\;,$$
and it follows by induction that $2.4\le d_n\le 2.5$ for $n\ge 1$. Since $p(1)=5$, it’s immediate that $5(2.4)^{n-1}\le p(n)\le 5(2.5)^{n-1}$ for all $n\ge 1$.
