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

-
Do you mean that $p(n)$ is the number of possible $n$-digit integers? Also, what do you mean by "$5*2,4^{n-1}$"? – Eric Jan 31 '13 at 21:44
yes (sorry for mistake :X) p(n) is the number of n-digit integers, and the second question function – user12392 Jan 31 '13 at 21:47
Not clear what your "Prove that..." Sentence wants us to prove. Is that the European decimal notation, with $*$ meaning $\times$? – Thomas Andrews Jan 31 '13 at 21:52
now it should be ok (* = ⋅) – user12392 Jan 31 '13 at 21:54
@Thomas: Yes, it must be. For those not familiar with with the notation, the inequality is $$5(2.4)^{n-1}\le p(n)\le 5(2.5)^{n-1}\;.$$ – Brian M. Scott Jan 31 '13 at 22:03

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

-
Nice! Actually, my argument proves the recursive relation, since $x^3-2x^2-2x+2$ is the characteristic polynomial of the matrix above. But your approach is more direct. – Thomas Andrews Feb 1 '13 at 0:50
@Thomas: For some reason I just don’t naturally think in linear algebraic terms! – Brian M. Scott Feb 1 '13 at 5:33

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.

-