An Unbounded Sequence

Solution

Note first that for a starting value k, if there is a term a_n in the sequence that includes the digit 0, then all the subsequent terms of the sequence are equal to a_n, and the sequence is bounded.

We can thefore prove the assertion by establishing that for any starting value k, there will be a term of the sequence that includes the digit 0.

So, proceeding by contradiction, we assume that for a given k, the sequence is unbounded, meaning that no term of the sequence includes the digit 0.

Pick an integer r such that (1) r >= 22 and (2) k < 10^r. The sequence is monotone increasing, so let a_m be the last term which is less than 10^r. By (2), there must exist such a term.

What can we say about a_m+1? First of all, by definition:

a_m+1 >= 10^r (1)

Furthermore:

a_m+1 = a_m + (the product of the digits of a_m)

But a_m has at most r digits, each of which is at most 9, so:

a_m+1 <= a_m + 9^r (2)

Now:

(10/9)^r >= (10/9)²² = 10.1546460985... > 10¹

Hence:

9^r < 10^r-1

Combining this with (1) and (2) above, we finally get:

10^r <= a_m+1 < 10^r + 10^r-1

This implies that the second digit of a_m+1 is 0, which is the contradiction that establishes the result.