4
$\begingroup$

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?

  • 0
    Yes, p(1) is 5.2012-12-02

3 Answers 3

5

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

  • 0
    @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.2012-12-03
3

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.

  • 0
    I am a bit lost... I do not know how to use it for original equation.2012-12-02
2

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.

  • 0
    Nice that you worked out this "second" approach as well.2012-12-06