Return to Question

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

Lemma 7. $f(n) = 2n - 9\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$

The following simple argument shows that $\river 1$, $\river 3$ and $\river 9$ are distinct (and any river meets at most one of them). Recall that the doubling map $x \mapsto 2x \pmod 9$ on $\{0,1,2,\dotsc,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.

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) \mathrel{:=} \max\{r \geq 0 \colon a_j = 9 \text{ for all } j \in \{0,1, \dots, r\}\}\text{.} $$ Equivalently, $$ \operatorname{tr} n \mathrel{:=} \max\{j \geq 1 \colon n+1 \text{ is a multiple of }10^j\}\text{.} $$

The following simple argument shows that $\river 1$, $\river 3$ and $\river 9$ are distinct (and any river meets at most one of them). Recall that the doubling map $x \mapsto 2x \pmod 9$ on $\{1,2,\dotsc,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.

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) \mathrel{:=} \max\{r \geq 0 \colon a_j = 9 \text{ for all } j \in \{0,1, \dots, r\}\}\text{.} $$ Equivalently, $$ \operatorname{tr} n \mathrel{:=} \max\{j \geq 0 \colon n+1 \text{ is a multiple of }10^j\}\text{.} $$

EDITS: typos