Problem 1371

Cutting off the last digit of a satisfactory $(n + 1)$-digit integer yields a satisfactory $n$-digit integer. Notice how a satisfactory $(n + 1)$-digit integer can be constructed from a satisfactory $n$-digit integer. If the last digit of the integer is $1$, we can append any of the digits $3$, $4$, $5$. If the last digit is $2$, we can append $4$ or $5$; if it is $3$, $1$ or $5$ can be appended; if it is $4$, $1$ or $2$ can be appended; and, finally, in the case of $5$, we can append any of the digits $1$, $2$, $3$. Thus we can see that only the last digit matters. So now, let $a_n$ denote the number of satisfactory $n$-digit integers ending in $1$ or $5$; similarly $b_n$ for $2$ or $4$, and $c_n$ for integers ending in $3$. Then $p(n) = a_n + b_n + c_n$. Apparently, $a_1 = b_1 = 2$, $c_1 = 1$, $p(1) = 5 = 5 \cdot 2.4^0 = 5 \cdot 2.5^0$, $a_2 = 6$, $b_2 = 4$, $c_2 = 2$, $p(2) = 12 = 5 \cdot 2.4^1 < 5 \cdot 2.5^1$.
The above reasoning implies the recurrent formulae
$$a_{n+1} = a_n + b_n + 2c_n, \quad b_{n+1} = a_n + b_n, \quad c_{n+1} = a_n. \quad (1)$$
Hence it follows that $a_3 = 14$, $b_3 = 10$, $c_3 = 6$, $p(3) = 30 \in (5 \cdot 2.4^2; 5 \cdot 2.5^2)$.
Using mathematical induction, we prove that for every $n \ge 3$, it holds that
$$a_n \ge 2.4^n, \quad b_n \ge \frac{2}{3} \cdot 2.4^n, \quad c_n \ge 2.4^{n-1}.$$
It indeed does for $n = 3$. If $a_n \ge 2.4^n$, $b_n \ge \frac{2}{3} \cdot 2.4^n$ and $c_n \ge 2.4^{n-1}$, then also
$$\begin{align*} a_{n+1} &= a_n + b_n + 2c_n \ge 2.4^n + \frac{2}{3} \cdot 2.4^n + 2 \cdot 2.4^{n-1} = \\ &= 2.4^n \cdot \left(1 + \frac{2}{3} + \frac{5}{6}\right) = 2.5 \cdot 2.4^n > 2.4^{n+1}, \\ b_{n+1} &= a_n + b_n \ge 2.4^n + \frac{2}{3} \cdot 2.4^n = \frac{5}{3} \cdot 2.4^n > \frac{2}{3} \cdot 2.4^{n+1}, \\ c_{n+1} &= a_n \ge 2.4^n. \end{align*}$$
It follows from the proved inequalities that
$$p(n) = a_n + b_n + c_n \ge 2.4^n + \frac{2}{3} \cdot 2.4^n + 2 \cdot 2.4^{n-1} = (2.4+1.6+1) \cdot 2.4^{n-1} = 5 \cdot 2.4^{n-1}.$$

The latter inequality can be proved analogously; we will verify that for $n \ge 3$,
$$a_n \le k \cdot 2.5^n, \quad b_n \le k \cdot \frac{2}{3} \cdot 2.5^n, \quad c_n \le k \cdot 2.5^{n-1}, \quad (2)$$
where $k$ is a suitably chosen number. Then we will have
$$p(n) = a_n + b_n + c_n \le k \cdot 2.5^{n-1} \cdot \left(2.5 + \frac{5}{3} + 1\right) = k \cdot 2.5^{n-1} \cdot \frac{31}{6} = 5k \cdot \frac{31}{30} \cdot 2.5^{n-1}.$$
Therefore, setting $k = \frac{30}{31}$, we get $p(n) \le 5 \cdot 2.5^{n-1}$ for every $n \ge 3$.
It remains to prove, by mathematical induction, the inequalities (2) where $k = \frac{30}{31}$.
They hold for $n = 3$. If (2) holds, we also have
$$\begin{align*} a_{n+1} &= a_n + b_n + 2c_n \le k \cdot 2.5^n \cdot \left(1 + \frac{2}{3} + \frac{4}{5}\right) = k \cdot 2.5^n \cdot \frac{37}{15} < k \cdot 2.5^{n+1}, \\ b_{n+1} &= a_n + b_n \le k \cdot 2.5^n \cdot \left(1 + \frac{2}{3}\right) = k \cdot \frac{2}{3} \cdot 2.5^{n+1}, \\ c_{n+1} &= a_n \le k \cdot 2.5^n. \end{align*}$$

We will show that each of the sequences $\{a_n\}$, $\{b_n\}$, $\{c_n\}$ defined in the above solution satisfies (as a consequence of the equalities (1)) the recurrent equation $x_{n+2} = 2x_{n+1} + 2x_n - 2x_{n-1}$, and so this equation is satisfied by the sequence $p(n) = a_n + b_n + c_n$ in question, which we will denote by (3).
Indeed, the first and third equalities of (1) give $a_{n+1} = a_n + b_n + 2a_{n-1}$, whence
$$b_n = a_{n+1} - a_n - 2a_{n-1}, \quad \text{so} \quad b_{n+1} = a_{n+2} - a_{n+1} - 2a_n.$$
Considering the second equality in (1), we thus get
$$a_{n+2} - a_{n+1} - 2a_n = b_{n+1} = a_n + b_n = a_n + (a_{n+1} - a_n - 2a_{n-1}).$$
Confronting the marginal expressions leads to the mentioned equality
$$a_{n+2} = 2a_{n+1} + 2a_n - 2a_{n-1}.$$
Triple substitution of $a_n = b_{n+1} - b_n$ into the equality $b_n = a_{n+1} - a_n - 2a_{n-1}$ yields
$$b_n = (b_{n+2} - b_{n+1}) - (b_{n+1} - b_n) - 2(b_n - b_{n-1}),$$
which can be rearranged to
$$b_{n+2} = 2b_{n+1} + 2b_n - 2b_{n-1}.$$
Finally, the sequence $\{c_n\}$ is merely a shifted sequence $\{a_n\}$, so
$$c_{n+2} = a_{n+1} = 2a_n + 2a_{n-1} - 2a_{n-2} = 2c_{n+1} + 2c_n - 2c_{n-1}.$$
Combining all of the three recurrent formulae, we get
$$p(n+2) = 2p(n+1) + 2p(n) - 2p(n-1). \quad (3)$$

Using mathematical induction, we will prove that for every $k \ge 1$,
$$2.4p(k) \le p(k+1) \le 2.5p(k). \quad (4)$$
The inequalities (4) hold for both $k = 1$ and $k = 2$. If (4) holds for all $k \in \{1, 2, \dots, n+1, n+2\}$, then
$$\begin{aligned} p(n+3) &= 2(p(n+2) + p(n+1) - p(n)) \ge 2\left(p(n+2) + p(n+1) - \frac{p(n+1)}{2.4}\right) = 2\left(p(n+2) + \frac{7p(n+1)}{12}\right) \ge 2\left(p(n+2) + \frac{7}{12} \cdot \frac{p(n+2)}{2.5}\right) = \frac{74p(n+2)}{30} > 2.4p(n+2). \end{aligned}$$
Similarly,
$$\begin{aligned} p(n+3) &\le 2\left(p(n+2) + p(n+1) - \frac{p(n+1)}{2.5}\right) \le 2\left(p(n+2) + \frac{3}{5} \cdot \frac{p(n+2)}{2.4}\right) = 2.5p(n+2). \end{aligned}$$
The equalities $5 \cdot 2.4^0 = p(1) = 5 \cdot 2.5^0$ and the inequalities of (4) imply that the inequality $5 \cdot 2.4^{n-1} \le p(n) \le 5 \cdot 2.5^{n-1}$ holds for every positive integer $n$.