$\DeclareMathOperator{\river}{river}\DeclareMathOperator{\leadingsum}{ls}\DeclareMathOperator{\digitsum}{ds}\newcommand{\qed}{\square}$
A [1999 British Informatics Olympiad question][1] asks about recursively-defined integer sequences called **(digital) rivers**. In any sequence, the number following $n$ is $n$ plus the digit sum of $n$ (in base $10$). By $\river k$, we mean the sequence with first term $k > 0$. Two rivers **meet** when they have terms in common. (All formalised below in case you care.)

Let's consider $\river 173$ for example. After $173$ comes $173+1+7+3=184$, after $184$ comes $184+1+8+4=197$, after $197$ comes $197 + 1 + 9 + 7 = 214$, and so on.

We find that $\river 91 = (91, 101, 103, \dots)$ meets $\river 100=(100, 101, 103, \dots)$, and that they both meet $\river 173$.

The question asserts the following without proof (and does not ask candidates for a proof).

> **Claim:** All rivers eventually meet $\river 1$, $\river 3$ or $\river 9$.

We'll agree to call these three the **main rivers**. (One may calculate that $\river 173$, $\river 91$ and $\river 100$ all meet $\river 1$). My attempts to write a proof of the claim have yielded only partial progress (details below). I've asked others in my department to no avail and so I'm casting the net wider.

I am grateful for any insight you can shed and any literature references you may think relevant. I am equally content to see this attacked with elementary tools as with sledgehammers. I also include an alternative characterisation of "$n$ plus the digit sum of $n$", in case it helps. Many thanks in advance!

----------
For the avoidance of doubt, here are some formal definitions.

Any positive integer $n$ has a unique base-$10$ representation $ \sum_{j=0}^\infty 10^j a_j $, where each $a_j \in \{0,1,2, \dots, 9\}$. In this representation, the **digit sum** of $n$ is $\digitsum n := \sum_{j=0}^\infty a_j$. (The digit sum is not to be confused with what others call the "digital root".) We define $f(n) := n + \digitsum n$, and then $\river k := (f^k(n))_{k \geq 0}$.

We say $\river k $ meets $\river k' $ if there exist $J,J' \geq 0$ with $f^J(k)=f^{J'}(k')$.

----------

The following simple argument shows that $\river 1$, $\river 3$ and $\river 9$ are distinct (and so any river meets at most one of them). Recall that the doubling map $x \mapsto 2x \pmod 9$ on $\{0,1,2,\dots,9\}$ permutes elements as follows: $9 \mapsto 9$, $3 \mapsto 6 \mapsto 3$, $1 \mapsto 2 \mapsto 4 \mapsto 8 \mapsto 7 \mapsto 5 \mapsto 1$. Observe in particular that $1$, $3$ and $9$ lie on distinct cycles.

>***Lemma 1.** $k \equiv \digitsum k \pmod 9 $*
>
> *Proof 1.* $ k = \sum_{j=0}^\infty 10^j a_j \equiv \sum_{j=0}^\infty 1^j a_j =\sum_{j = 0}^\infty a_j = \digitsum k $. $\qed$

>***Lemma 2.** $f(n) \equiv 2n \pmod 9$.*
>
>*Proof 2.* For any $j >0$, $f(n) = n + \digitsum n \equiv n + n = 2 n \pmod 9$ by Lemma 1. $\qed$

>***Lemma 3.** The rivers $\river 1$, $\river 3$, $\river 9$ are distinct.*
>
>*Proof 3.* Reduce the entries of these rivers modulo $9$, and find that they are the periodic sequences $(1,2,4,8,7,5,1,\dots)$, $(3,6,3,\dots)$ or $(9,9,\dots)$, by Lemma 2. None shares any entries with another. $\qed$

Consequently, $\river k$ can meet at most one main river, depending on which cycle of the doubling permutation lies the residue of $k$ modulo $9$.

----------

I'll end with an alternative characterisation of $f(n)$.

First, I need to define the number $\operatorname{tr} n$  of **trailing 9s** of $n$, which uses the base-$10$ representation of $n$ as above. Informally, it's the number of $9$s at the end of $n$, so that for example $\operatorname{tr} 78 = 0$, $\operatorname{tr} 79 = 1$, $\operatorname{tr}99 = 2$, $\operatorname{tr} 7999 = 3$. Formally,
$$
\operatorname{tr}\left(\sum_{j=0}^\infty 10^j a_j\right) := \max\{r \geq 0 \colon a_j = 9 \text{ for all } j \in \{0,1, \dots, r\}\}\text{.}
$$
Equivalently,
$$
\operatorname{tr} n := \max\{j \geq 1 \colon n+1 \text{ is a multiple of }10^j\}\text{.}
$$

> ***Lemma 4.** $\digitsum(n+1)-\digitsum n = 1 -9\operatorname{tr} n$*
>
> *Proof 4.* What happens to the digits when we add $1$ to $n$? The leftmost non-$9$ digit is increased by $1$, and all the trailing $9$s to the right of it are reduced from $9$ to $0$. Remaining digits are unaffected. The result follows. $\qed$

> ***Lemma 5.** $f(n+1)-f(n) = 2-9\operatorname{tr} (n)$*
>
> *Proof 5.* Follows trivially from Lemma 4. $\qed$

Next, define the **leading sum** of an integer $n>0$ to be $\leadingsum n := \sum_{j=1}^\infty \left\lfloor \frac{n}{10^j}\right\rfloor$ (beware: indices $j$ start at $1$, not $0$.) Some examples: $\leadingsum 12345 = 1234 + 123 + 12 + 1 = 1370$ and $\leadingsum 173 = 17 + 3 = 20$.

> ***Lemma 6.** $ \sum_{j=1}^{n-1} \operatorname{tr}(j) = \leadingsum(n)$*
>
> *Proof 6.* There are $\left\lfloor \frac{n}{10}\right\rfloor$ multiples of $10$ that are equal to or less than $n$ and each contributes $1$ to this sum. There are $\left\lfloor \frac{n}{100}\right\rfloor$ multiples of $100$ that are equal to or less than $n$ and each contributes a further $1$. Etc. The result follows. $\qed$

> ***Lemma 7.** $f(n) = 2n - \leadingsum n$*
>
> *Proof 7.* We can form a telescoping sum
> $$f(n) - f(1) = \sum_{j=1}^{n-1} f(j+1) - f(j) = \sum_{j=1}^{n-1} (2-9\operatorname{tr}j) = 2(n-1) - 9\sum_{j=1}^{n-1}\operatorname{tr} j = 2(n-1) -9 \leadingsum n\text{.}$$
> To this, we simply add $f(1)=2$ and we're done. $\qed$

[1]: https://www.olympiad.org.uk/papers/1999/bio/bio99r1q1.html