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

-
I don't understand what the commas signify. Is it the decimal point? In particular $p(1)=5$, right? –  hardmath Dec 2 '12 at 18:24
Yes, it is a decimal point. - see editted revision –  Jack09 Dec 2 '12 at 18:32
Yes, p(1) is 5. –  Jack09 Dec 2 '12 at 20:38

We can exactly express the count $p(n)$ of $n$-digit numbers from $\{1,2,3,4,5\}$ where adjacent digits cannot differ by less than two, as WimC outlines above. If $p_k(n)$ denotes the count of such numbers with leading digit $k$, then for $n \ge 1$:

$$p(n) = p_1(n) + p_2(n) + p_3(n) + p_4(n) + p_5(n)$$

Furthermore since an $n+1$ digit number of the required type consists of an $n$ digit such number with a compatible new leading digit (one that differs by at least two from the previous digit), we have by induction the matrix expression:

$$p(n) = u A^{n-1} u'$$

where row $u = \begin{pmatrix} 1&1&1&1&1 \end{pmatrix}$, and $A$ is WimC's $5\times5$ Toeplitz matrix. For example, $p(1) = 5$, $p(2) = 12$, $p(3) = 30$, $p(4) = 74$, and $p(5) = 184$.

The desired bounds can be framed in terms of Rayleigh quotients $R_n = \frac{u A^n u'}{u u'}$:

$$2.4^n \le R_n \le 2.5^n$$

because the denominator $u u' = 5$, so that $p(n) = 5 R_{n-1}$. The upper bound is implied by the computation of the dominant eigenvalue of real symmetric $A^n$, which is the $n$th power of the dominant eigenvalue of $A$.

As WimC noted, $A$ has a dominant eigenvalue $\lambda_{max} \approx 2.4812 \lt 2.5$. Indeed $A$'s characteristic polynomial is $(\lambda^3 -2\lambda^2 -2\lambda + 2)(\lambda + 2)\lambda$ and there are five distinct real eigenvalues. By virtue of $A$ being real symmetric, these correspond to mutually orthogonal eigenvectors.

The two "easy" eigenvalues $\lambda = -2,0$ correspond to unit (left) eigenvectors $\frac{1}{2}\begin{pmatrix} 1&1&0&-1&-1 \end{pmatrix}$ and $\frac{1}{2}\begin{pmatrix} 1&-1&0&1&-1 \end{pmatrix}$ respectively. These happen to be orthogonal to $u$, and so are not used below to express $u$ in terms of the orthonormal basis of $A$-eigenvectors.

$$\lambda_{max} \approx 2.4812, v_{max} \approx \begin{pmatrix} 0.52990 & 0.35775 & 0.42713 & 0.35775 & 0.52990 \end{pmatrix}$$

$$\lambda_{med} \approx 0.68889, v_{med} \approx \begin{pmatrix} 0.17934 & -0.57645 & 0.52066 & -0.57645 & 0.17934 \end{pmatrix}$$

$$\lambda_{min} \approx -1.17009, v_{min} \approx \begin{pmatrix} 0.43249 & -0.19929 & -0.73924 & -0.19929 & 0.43249 \end{pmatrix}$$

Taking the dot-product of $u$ with each of these vectors gives us the coefficients of the basis expansion:

$$u \approx 2.20243 v_{max} - 0.27356 v_{mid} - 0.27284 v_{min}$$

Thus the Rayleigh quotient $R_n$ can be computed from that expansion:

$$A^n u' \approx 2.20243 \lambda_{max}^n v_{max} - 0.27356 \lambda_{med}^n v_{mid} - 0.27284 \lambda_{min}^n v_{min}$$

$$R_n \approx (2.20243^2 \lambda_{max}^n + 0.27356^2 \lambda_{med}^n + 0.27284^2 \lambda_{min}^n)/5$$

The lower bound $R_n \ge 2.4^n$ may be established by noting that it holds with equality for $n=0,1$ and then showing that $2.4^{-n} R_n$ increases thereafter:

$$2.4^{-n} R_n \approx 0.97014 (\frac{\lambda_{max}}{2.4})^n + 0.01497 (\frac{\lambda_{med}}{2.4})^n + 0.01489 (\frac{\lambda_{min}}{2.4})^n$$

The growing leading term, whose base $\frac{\lambda_{max}}{2.4}$ exceeds 1, will of course eventually dominant the other two terms, one of which is positive but shrinking and the other alternating in sign (but also shrinking).

Treating this as a continuous function of the exponent n (over positive reals) and differentiating gives a concrete proof that it increases for $n \gt 1$, which agrees with the several initial values already tabulated:

$$2.4^{-1} R_1 = 1$$

$$2.4^{-2} R_2 = 1.041666...$$

$$2.4^{-3} R_3 = 1.07060185...$$

$$2.4^{-4} R_4 = 1.109182098765432...$$

-
+1. I was about to finish my answer but that won't be necessary anymore. :-) –  WimC Dec 3 '12 at 18:15
@WimC: Thanks, I think there's a simpler foundation via $p(n)$ satisfying a four-term linear recurrence (similar to how the Fibonacci numbers satisfy a three-term relation), namely $p(n+1) = 2(p(n)+p(n-1)-p(n-2))$. I can't visualize why this is so, directly from the objects being counted. –  hardmath Dec 3 '12 at 19:45
That seems reasonable, given the characteristic polynomial that you already mentioned and the fact that eigenvalues $-2$ and $0$ do not contribute. –  WimC Dec 3 '12 at 19:59
@WimC: I guess we can use the matrix representation to justify it (I checked the first few sets of tabulated values). Then it seems we can do upper and lower bounds by simple induction. –  hardmath Dec 3 '12 at 20:08

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.

-
Thanks! There is a condition "each two neighbour digits differ by 2 or more"... –  Jack09 Dec 2 '12 at 20:36
Your approach can be pushed through. Given the matrix $A$ you define and row vector $u=(1..1)$, $p(n) = uA^{n-1}u'$. As a real symmetric matrix, $A$ has a complete orthonormal basis of eigenvectors, with which we can express vector $u'$ as some linear combination. This gives an explicit expression for $A^{n-1} u'$, and thus for $p(n)$. –  hardmath Dec 2 '12 at 21:53
@Jack09: WimC has accounted for the "each two neighbor digits differ by 2 or more" in the way the transition matrix is constructed. –  hardmath Dec 2 '12 at 21:55
I am a bit lost... I do not know how to use it for original equation. –  Jack09 Dec 2 '12 at 22:25

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.

-
Nice that you worked out this "second" approach as well. –  WimC Dec 6 '12 at 12:47