每日一题[1800]二进制长度

设 $k$ 是给定的正整数，$r=k+\dfrac 12$．记 $f^{(1)}(r)=f(r)=r\lceil r \rceil$，$f^{(l)}(r)=f(f^{(l-1)}(r))$，$l \geqslant 2$．证明：存在正整数 $m$，使得 $f^{(m)}(r)$ 为一个整数．这里 $\lceil x \rceil$ 表示不小于实数 $x$ 的最小整数，例如：$\left\lceil \dfrac 12 \right\rceil=1$，$\lceil 1 \rceil=1$．

解析    记 $v_2(n)$ 表示正整数 $n$ 所含的 $2$ 的幂次，接下来证明：

引理    当 $m=v_2(k)+1$ 时，$f^{(m)}(r)$ 为整数．

证明    下面我们对 $v_2(k)=v$ 进行归纳．

归纳基础    当 $v=0$ 时，$k$ 为奇数，$k+1$ 为偶数，此时 $$f(r)=\left(k+\dfrac 12\right) \left\lceil k+\dfrac 12\right\rceil=\left(k+\dfrac 12\right) (k+1)=k(k+1)+\dfrac{k+1}2\in\mathbb Z.$$

递推证明    假设命题对 $v-1$（$v\geqslant 1$）成立． 对于 $v\geqslant 1$，对应的 $k$ 的二进制表示具有形式 $$k=2^v+\alpha_{v+1}\cdot 2^{v+1}+\alpha_{v+2}\cdot 2^{v+2}+\cdots,$$ 其中 $\alpha_{i}\in \{0,1\}$（$i=v+1,v+2,\cdots$），于是 $$f(r)=\left(k+\dfrac 12\right) \left\lceil k+\dfrac 12\right\rceil=\left(k+\dfrac 12\right) (k+1)=\dfrac 12+\dfrac k2+k^2+k =k'+\dfrac 12 ,$$ 其中 $$k'=2^{v-1}+(\alpha_{v+1}+1)\cdot 2^v+(\alpha_{v+1}+ \alpha_{v+2})\cdot 2^{v+1}+\cdots +2^{2v}+\cdots,$$ 显然 $k'$ 中所含的 $2$ 的幂次为 $v-1$． 故由归纳假设知，$r'=k'+\dfrac 12$ 经过 $f$ 的 $v$ 次迭代得到整数，进而可得 $f^{(v+1)}(r)$ 是一个整数，这就完成了归纳证明． 综上所述，原命题得证．