Mathematical Reflections 2013, Issue 5 - Problem S281

Problem:
Let $f(n)$ be the sum of the digits of $n^2 + 1$. Define the sequence $(a_n)_{n \geq 0}$, with $a_0$ an
arbitrary positive integer and $a_{n+1} = f(a_n)$, $n \geq 0$. Prove that $(a_n)_{n \geq 0}$ is $3$-periodic.

Proposed by Roberto Bosch Cabrera.

Solution:
Since $f(5)=8, f(8)=11$ and $f(11)=5$, it suffices to prove that for every positive integer $a_0$ there exists some $n \in \mathbb{N}$ such that $a_n \in \{5,8,11\}$. Let $m$ be the number of digits of $a_0$. We prove the statement by induction on $m$. For $m \leq 2$ we proceed by a direct check. If $a_0 \in \{5,8,11\}$ there is nothing to prove. If $a_0$ is a two-digit number, then $a^2_0 \leq 10000$, so $a_1 \leq 37$ and we reduce to analyze the cases for $a_0 \leq 37$.

(i) If $a_0 \in \{2,7,20\}$, then $a_1=5$. If $a_0 \in \{1,10,26,28\}$, then $a_1 \in \{2,20\}$, so $a_2=5$. Finally, if $a_0 \in \{3,6,9,12,15,18,27,30,33\}$, then $a_3=5$.

(ii) If $a_0 \in \{4,13,23,32\}$, then $a_1=8$.

(iii) If $a_0 \in \{17,19,21,35,37\}$, then $a_1=11$. If $a_0 \in \{14,22,24,31,36\}$, then $a_1 \in \{17,19\}$, so $a_2=11$. Finally, if $a_0 \in \{16,25,29,34\}$, then $a_3=11$.

Thus, we have proved that if $a_0$ is a one or two-digit number, then $a_n \in \{5,8,11\}$ for some $n \in \mathbb{N}$, i.e. the sequence is $3$-periodic. Let $m \geq 2$ and suppose that the statement is true for all $k \leq m$. Let $a_0$ be an $(m+1)$-digit number. Then, $10^m \leq a_0 < 10^{m+1}$ which implies $10^{2m} \leq a^2_0 < 10^{2(m+1)}$. Hence, $$a_1=f(a_0) \leq 9\cdot2(m+1)+1<10^m,$$ and by induction hypothesis, the sequence $(a_n)_{n \geq 1}$ is $3$-periodic, which implies that the sequence $(a_n)_{n \geq 0}$ is $3$-periodic, as we wanted to prove.


Note: the problem was later changed.