Define a sequence as follows:
a1 = k
an+1 = an + (the product of the digits of an)
Is there a value of k for which this sequence is unbounded?
Note first that for a starting value k, if there is a term an in the sequence that includes the digit 0, then all the subsequent terms of the sequence are equal to an, 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 < 10r. The sequence is monotone increasing, so let am be the last term which is less than 10r. By (2), there must exist such a term.
What can we say about am+1? First of all, by definition:
am+1 >= 10r (1)
am+1 = am + (the product of the digits of am)
But am has at most r digits, each of which is at most 9, so:
am+1 <= am + 9r (2)Now:
(10/9)r >= (10/9)22 = 10.1546460985... > 101
9r < 10r-1
Combining this with (1) and (2) above, we finally get:
10r <= am+1 < 10r + 10r-1
This implies that the second digit of am+1 is 0, which is the contradiction that establishes the result.