注：本节内容为《具体数学》(原书第二版) 第三章 整值函数 3.5节 顶和底的和式习题 3.32 的推导。

背景

步入第三章，习题变得愈发困难了起来，困难到我看了答案这题还推了 6 个小时 ... 果然还是水平太菜了。

这里就仔细补全一下书上没写的推导。

原题

求

$$
\sum _ k 2^k \Big \Vert \frac x {2^k} \Big \Vert ^ 2
$$

其中 $\Vert x \Vert = \min \{x - \lfloor x \rfloor, \lceil x \rceil - x\}$ 表示 $x$ 到最近整数的距离。

推导

Prerequisite - 几个性质

首先给出几个性质，易证成立：

$$
\Vert x \Vert \leq \frac 1 2
$$

$$
\Vert x + n \Vert = \Vert x \Vert, n \in \mathbb Z
$$

$$
\Vert -x \Vert = \Vert x \Vert
$$

敛散性证明

接下来，我们开始着手处理这个级数。令 $f(x)$ 为题目中的和式。不难发现：

$$
f(-x) = \sum _ k 2^k \Big \Vert \frac {-x} {2^k} \Big \Vert ^ 2 = \sum _ k 2^k \Big \Vert \frac x {2^k} \Big \Vert ^ 2 = f(x)
$$

即 $f(x)$ 为偶函数。不失一般性，我们来考察 $x \geq 0$。

观察到，这个和式是双向无穷的。我们首先来证明这个级数收敛。

(1) 当 $k \rightarrow -\infty$ 时

$$
2^k \Big \Vert \frac {x} {2^k} \Big \Vert ^ 2 \leq 2^k \times \frac 1 4 \leq 2^k
$$

$$
\sum _ {k < 0} 2^k \Big \Vert \frac {x} {2^k} \Big \Vert ^ 2 \leq \frac 1 4 \sum _ {k < 0} 2^k = \frac 1 4
$$

所以 $k$ 为负数时级数收敛，且小于 $\displaystyle \frac 1 4$。

(2) 当 $k \rightarrow + \infty$ 时

$$
\begin{aligned}
&k \rightarrow + \infty \\
\Rightarrow & 2^k \gg x \\
\Rightarrow & \Big \Vert \frac {x} {2^k} \Big \Vert ^ 2 \rightarrow \Big ( \frac {x} {2^k} \Big ) ^ 2 \\
\Rightarrow & 2^k \Big \Vert \frac {x} {2^k} \Big \Vert ^ 2 \rightarrow \frac {x^2} {2^k}
\end{aligned}
$$

故只有有限项不等于 $\displaystyle \frac {x^2} {2^k}$。对于

$$
\frac {x} {2^k} \leq \frac 1 2 \Rightarrow k \geq 1 + \lceil \log_2 x \rceil
$$

都有第 $k$ 项等于 $\displaystyle \frac {x^2} {2^k}$。这些无限项必定收敛，因为同样是一个几何级数 ($x$ 在这里是常数)。

由此，我们证明了 $f(x)$ 对于 $\forall x \in \mathbb R$ 一定存在。

结论：$f(2x) = 2f(x)$

不难证明：

$$
\begin{aligned}
f(2x) &= \sum _ k 2^k \Big \Vert \frac {2x} {2^k} \Big \Vert ^ 2 \\
&= 2 \sum _ k 2^{k-1} \Big \Vert \frac {x} {2^{k-1}} \Big \Vert ^ 2 \\
&= 2 \sum _ k 2^{k} \Big \Vert \frac {x} {2^{k}} \Big \Vert ^ 2 \\
&= 2f(x)
\end{aligned}
$$

拆分和式

设

$$
f(x) = l(x) + r(x)
$$

其中：

$$
l(x) = \sum _ {k \leq 0} 2^k \Big \Vert \frac {x} {2^k} \Big \Vert ^ 2
$$

$$
r(x) = \sum _ {k > 0} 2^k \Big \Vert \frac {x} {2^k} \Big \Vert ^ 2
$$

处理 $l(x)$

不难证明：

$$
\begin{aligned}
l(x + 1) & = \sum _ {k \leq 0} 2^k \Big \Vert \frac {x+1} {2^k} \Big \Vert ^ 2 \\
& = \sum _ {k \leq 0} 2^k \Big \Vert \frac {x} {2^k} + 2^{-k} \Big \Vert ^ 2 \\
\end{aligned}
$$

注意到，由于 $k \leq 0$ ，所以 $2^{-k} \in \mathbb Z$，更具性质：

$$
\begin{aligned}
l(x + 1) & = \sum _ {k \leq 0} 2^k \Big \Vert \frac {x} {2^k} \Big \Vert ^ 2 = l(x)
\end{aligned}
$$

除此之外，类似于前面敛散性的证明，我们还能给出 $l(x)$ 的范围：

$$
l(x) = \sum _ {k \leq 0} 2^k \Big \Vert \frac {x} {2^k} \Big \Vert ^ 2 \leq \frac 1 4 \sum _ {k \leq 0} 2^k = \frac 1 2
$$

处理 $r(x)$

$r(x)$ 的处理稍显复杂。首先，我们来考察 $0 \leq x < 1$ 的情况，我们不难发现，由于

$$
\forall k > 0 \Rightarrow \frac {x} {2^k} \leq \frac 1 2, (0 \leq x < 1)
$$

所以，有

$$
\forall k > 0, 0 \leq x < 1 \Rightarrow \Big \Vert \frac x {2^k} \Big \Vert = \frac x {2^k}
$$

故，对于 $0 \leq x < 1$

$$
r(x) = \frac {x^2} 2 + \frac {x^2} {2^2} + \cdots = x^2
$$

接下来我们来考察 $r(x+1)$ ，同样，$0 \leq x < 1$

$$
r(x+1) = \frac {(x-1)^2} {2} + \frac {(x+1)^2} 4 + \frac {(x+1)^2} 8 + \cdots = x^2 + 1
$$

看到第一项可能会感到非常困扰，但是没有关系，借助我们在最开始得到的几个性质，我们可以很轻松地进行转化:

$$
\Big \Vert \frac {x+1} 2 \Big \Vert = \Big \Vert \frac {x+1} 2 - 1 \Big \Vert = \Big \Vert \frac {x-1} 2 \Big \Vert
$$

注意到，此时 $\displaystyle\frac {x-1} 2 \in [\frac 1 2, \frac 1 2]$，故在平方处理之后可以直接脱去 $\Vert \cdot \Vert$。

但是现在看这 $r(x+1)$ 很难找到规律，我们不妨多列几项 (只列出有变化的项)：

上表的解释：「第$k$项的值$t_k$」代表这一项写作 $\displaystyle \frac {x+t_k} {2^k}$，如果不写，则代表就是普通的：$\displaystyle \frac {x+n} {2^k}$

所以，上表列出的数，我们究竟怎样才能表达出来呢？不难得出结论，这其实就是一个位移过的模数。我们需要将 $x+n$ 映射到 $(-2^{k-1}, 2^{k-1}]$，那我们也便不难得出，这个 $t$ 其实就是下式：

$$
\begin{aligned}
t_k(n) &= (n+2^{k-1}) \pmod {2^k} - 2^{k-1} \\
&= (n+2^{k-1}) - 2^k \Big \lfloor \frac {n+2^{k-1}} {2^k} \Big \rfloor - 2^{k-1} \\
&= n - 2^k \Big \lfloor \frac {n+2^{k-1}} {2^k} \Big \rfloor
\end{aligned}
$$

可能还看不出这个式子为什么是对的。其实，$(n+2^{k-1}) \pmod {2^k} - 2^{k-1}$ 这个我通过短时间观察得到的结果很难说明正确性，但是我们化简后的结果就可以。我们可以证明：

1. $\displaystyle 2^k \Big \lfloor \frac {n+2^{k-1}} {2^k} \Big \rfloor \in \mathbb Z$，因为性质 $\Vert x + n \Vert = \Vert x \Vert, n \in \mathbb Z$ 我们可以证明这个值和原来的值相等
2. $\displaystyle t_k(n) \in (-2^{k-1},2^{k-1}]$ (可以很容易地通过讨论 $n$ 是否小于等于 $2^{k-1}$ 证明)，也就是说可以证明 $\displaystyle \frac {n+t_k(n)}{2^k} \in (-\frac 1 2, \frac 1 2]$，可以直接脱去 $\Vert \cdot \Vert$

此外，不难看出，对于没有改变，即正常的项，我们定义的 $t_k(n)$ 仍旧适用，因为此时 $t_k(n) = n$。

接下来，我们需要用归纳来证明一个很强的结论：

$$
r(x+n) = x^2 + n, 0 \leq x < 1, n \in \mathbb N
$$

我们来着手证明它。注意：根据我们前面对 $t_k (n)$ ，我们可以改写 $r(x+n)$：

$$
r(x+n) = \sum _ {k > 0} \frac {(x + t_k(n))^2} {2^k}
$$

而我们也就可以通过计算其的二次项系数、一次项系数、常数项，证明它等于 $x^2 + n$。显然，二次项系数等于一，所以我们的主要工作就在于如何证明一次项系数等于 $0$，常数项等于 $n$。这里我们用归纳法进行证明。

归纳假设一 (一次项系数为 $0$):

$$
\begin{aligned}
&\sum_{k>0}-2\frac {t_k(n)} {2^k} = 0 \Leftrightarrow \sum_{k>0}\frac {t_k(n)} {2^k} = 0 \\
\Leftrightarrow&\sum_{k>0}\frac {n} {2^k} - \Big \lfloor \frac {n+2^{k-1}} {2^k} \Big \rfloor = 0 \\
\Leftrightarrow&\sum_{k>0}\frac {n} {2^k} = \sum_{k>0} \Big \lfloor \frac {n+2^{k-1}} {2^k} \Big \rfloor
\end{aligned}
$$

对于 $n+1$

$$
\begin{aligned}
&~\sum_{k>0}\frac {t_k(n+1)} {2^k} \\
=&~\sum_{k>0}\frac {n+1} {2^k} - \Big \lfloor \frac {n+1+2^{k-1}} {2^k} \Big \rfloor \\
=&~\sum_{k>0}\frac {n} {2^k} + \sum_{k>0}\frac {1} {2^k} - \sum_{k>0}\Big \lfloor \frac {n+1+2^{k-1}} {2^k} \Big \rfloor \\
=&~1 + \sum_{k>0} \Big \lfloor \frac {n+2^{k-1}} {2^k} \Big \rfloor - \sum_{k>0}\Big \lfloor \frac {n+1+2^{k-1}} {2^k} \Big \rfloor \\
=&~1 + \sum_{k>0} \Big ( \Big \lfloor \frac {n+2^{k-1}} {2^k} \Big \rfloor - \Big \lfloor \frac {n+1+2^{k-1}} {2^k} \Big \rfloor \Big )
\end{aligned}
$$

现在问题变得有趣了起来。观察我们得到的新的和式，思考对于某个 $k$ ，其项的值为 $-1$ 时的二进制位表示的意义。我们发现，这种情况是 唯一的 ！因为，这代表 $n$ 在加上了 $1 + 2^{k-1}$ 后恰好能被 $2^k$ 整除，即代表 $n$ 的二进制数的第 $0$ 位到第 $k-2$ 位为 $1$ ，第 $k-1$ 位为零。这样的形式对于每个数而言必定是唯一的，因为一个数末尾连续的 $1$ 的个数是唯一确定的！所以，整个和式的值就是 $-1$。

前面所说的位表示的示意：

$$
0\underbrace{11\cdots11}_{k-1}
$$

所以，我们成功证明了

$$
\sum_{k>0}\frac {t_k(n+1)} {2^k} = 1-1 = 0
$$

归纳假设二 (常数项等于 $n$)：

$$
\begin{aligned}
&\sum _ {k>0} \frac {t_k (n)^2} {2^k} = n \\
\Leftrightarrow & \sum_{k>0} \frac {n^2 - 2n * 2^k \Big \lfloor \frac {n+2^{k-1}} {2^k} \Big \rfloor + \Big (2^k \Big \lfloor \frac {n+2^{k-1}} {2^k} \Big \rfloor \Big )^2} {2^k} = n \\
\Leftrightarrow & \sum_{k>0} \frac {n^2} {2^k} - 2n\Big \lfloor \frac {n+2^{k-1}} {2^k} \Big \rfloor + 2^k \Big ( \Big \lfloor \frac {n+2^{k-1}} {2^k} \Big \rfloor \Big)^2 = n
\end{aligned}
$$

对于 $n+1$

$$
\begin{aligned}
&\sum _ {k>0} \frac {t_k (n+1)^2} {2^k} \\
=&\sum_{k>0} \frac {n^2 + 2n + 1} {2^k} - 2(n+1)\Big \lfloor \frac {n+1+2^{k-1}} {2^k} \Big \rfloor + 2^k \Big ( \Big \lfloor \frac {n+1+2^{k-1}} {2^k} \Big \rfloor \Big)^2 \\
=&\sum_{k>0} \frac {n^2} {2^k} - 2n \Big \lfloor \frac {n+1+2^{k-1}} {2^k} \Big \rfloor + 2^k \Big ( \Big \lfloor \frac {n+1+2^{k-1}} {2^k} \Big \rfloor \Big)^2 \\ +& \sum_{k>0} \frac {2n+1} {2^k} - 2\Big \lfloor \frac {n+1+2^{k-1}} {2^k} \Big \rfloor
\end{aligned}
$$

先处理后一部分：

$$
\begin{aligned}
~& \sum_{k>0} \frac {2n+1} {2^k} - 2\Big \lfloor \frac {n+1+2^{k-1}} {2^k} \Big \rfloor \\
=~& 1 + 2\sum_{k>0} \frac {n} {2^{k}} - 2\sum_{k>0} \Big \lfloor \frac {n+1+2^{k-1}} {2^k} \Big \rfloor \\
=~& 1 + 2\sum_{k>0} \Big \lfloor \frac {n+2^{k-1}} {2^k} \Big \rfloor - \Big \lfloor \frac {n+1+2^{k-1}} {2^k} \Big \rfloor \\
=~& -1
\end{aligned}
$$

注意，这里用到了上一次归纳的结论。

我们再来处理前面一部分：

$$
\begin{aligned}
&\sum_{k>0} \frac {n^2} {2^k} - 2n \Big \lfloor \frac {n+1+2^{k-1}} {2^k} \Big \rfloor + 2^k \Big ( \Big \lfloor \frac {n+1+2^{k-1}} {2^k} \Big \rfloor \Big)^2 \\
=&\sum_{k>0} \frac {n^2} {2^k} - 2n \Big \lfloor \frac {n+2^{k-1}} {2^k} \Big \rfloor + 2^k \Big ( \Big \lfloor \frac {n+2^{k-1}} {2^k} \Big \rfloor \Big)^2 \\
&-2n + 2^p \Big ( \Big ( \Big \lfloor \frac {n+2^{p-1}} {2^p} \Big \rfloor + 1 \Big)^2 - \Big ( \Big \lfloor \frac {n+2^{p-1}} {2^p} \Big \rfloor \Big)^2 \Big)
\end{aligned}
$$

其中，$p$ 为使得 $n+1+2^{k-1}$ 恰好被 $2^k$ 整除的 $k$. 我们继续计算：

$$
\begin{aligned}
&~\sum_{k>0} \frac {n^2} {2^k} - 2n \Big \lfloor \frac {n+2^{k-1}} {2^k} \Big \rfloor + 2^k \Big ( \Big \lfloor \frac {n+2^{k-1}} {2^k} \Big \rfloor \Big)^2 \\
&~-2n + 2^p \Big ( \Big ( \Big \lfloor \frac {n+2^{p-1}} {2^p} \Big \rfloor + 1 \Big)^2 - \Big ( \Big \lfloor \frac {n+2^{p-1}} {2^p} \Big \rfloor \Big)^2 \Big) \\
=&~n - 2n + 2^p \Big( 2 \Big \lfloor \frac {n+2^{p-1}} {2^p} \Big \rfloor + 1 \Big)
\end{aligned}
$$

现在，这个状态非常难以化简，但是没有关系！我们完全可以再次进行二进制表示分析。首先我们给出 $n$ 的二进制表示：

$$
\boxed{1\cdots} ~ \underbrace{011\cdots 1}_{p}
$$

$\displaystyle \Big \lfloor \frac {n+2^{p-1}} {2^p} \Big \rfloor$ :

$$
\boxed{1\cdots}
$$

$\displaystyle 2\Big \lfloor \frac {n+2^{p-1}} {2^p} \Big \rfloor + 1$ :

$$
\boxed{1\cdots} ~1
$$

$\displaystyle 2^p \Big( 2 \Big \lfloor \frac {n+2^{p-1}} {2^p} \Big \rfloor + 1 \Big)$ :

$$
\boxed{1\cdots} ~1~\underbrace{00\cdots 0}_{p}
$$

而这就等于 $2n + 2$:

$$
\boxed{1\cdots} ~ \underbrace{011\cdots 1}_{p} 0 + 2 = \boxed{1\cdots} ~1~\underbrace{00\cdots 0}_{p}
$$

将我们得到的结果拼接起来：

$$
\begin{aligned}
&\sum _ {k>0} \frac {t_k (n+1)^2} {2^k} \\
=&-n + (2n + 2) - 1 = n + 1
\end{aligned}
$$

由此，证明了第二个归纳假设。

由此我们完成了 $r(x+n) = r(x) + n, 0 \leq x < 1, n \in \mathbb N$ 的证明。

计算 $f(x)$

所以，一般来说，我们可以得到

$$
\begin{aligned}
f(x) &= 2^{-m} f(2^m x) \\
&= 2^{-m} f(\lfloor 2^m x \rfloor + \{ 2^m x \}) \\
&= 2^{-m} (\lfloor 2^m x \rfloor + f(\{2^m x\})) \\
&= 2^{-m} \lfloor 2^m x \rfloor + 2^{-m} f(\{2^m x\})
\end{aligned}
$$

其中，

$$
\begin{aligned}
f(\{2^m x\}) = l(\{2^m x\}) + r(\{2^m x\})) \leq \frac 1 2 + 1
\end{aligned}
$$

所以对 $\forall m \in \mathbb Z$，有

$$
\begin{aligned}
|f(x) - x| &\leq | 2^{-m} \lfloor 2^m x \rfloor + 2^{-m} \times \frac 3 2 - x | \\
&\leq | 2^{-m} \lfloor 2^m x \rfloor - x | + 2^{-m} \times \frac 3 2 \\
&= | 2^{-m} 2^m x - 2^{-m} \{2^m x\} - x | + 2^{-m} \times \frac 3 2 \\
&= | x - 2^{-m} \{2^m x\} - x | + 2^{-m} \times \frac 3 2 \\
&= | - 2^{-m} \{2^m x\} | + 2^{-m} \times \frac 3 2 \\
&\leq 2^{-m} \times \frac 5 2
\end{aligned}
$$

所以 $|f(x) - x| = 0$，即对于 $x \geq 0$ 我们有 $f(x) = x$

由于我们已经证明了 $f(x)$ 为偶函数，故最终得到答案：

$$
f(x) = |x|
$$