Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
1  
@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

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.