每日一题[3212]步进调头

设 $a$ 为正整数，$3 \mid a$，$f(1)=a$．令

$$f(n+1)=\begin{cases} \sqrt{f(n)}, & \sqrt{f(n)} \in \mathbb{Z}, \\ f(n)+3, & \sqrt{f(n)} \notin \mathbb{Z},\end{cases}$$ 其中 $n \geqslant 1$．求证：存在 $M$ 使得 $f(n) \leqslant M$（$n \geqslant 1$）．

解析    根据题意，有 $3\mid f(n)$，设 $a=3m$，则

$$f(n):~ 3m,3(m+1),\cdots,3(3t^2),3t,\cdots,$$ 观察可得 $t\leqslant m$，也即 $f(n)\leqslant 9a^2$，因此命题得证（取 $M=9a^2$ 即可），用数学归纳法容易证明：$3\mid f(n)$ 且 $f(n)\leqslant 9a^2$．