3.1.20 #

解答 #

国内的书中关于命题 B 的证明有错误，新版的证明结论已经改为：

$$ C(n)=C(2^k-1) \le k = \lg (n+1) \le \lg n +1 $$

其中 $n=2^k - 1 $ 。 先证单调性，利用数学归纳法： 已知对于 $N=0$，满足 $C(0) \le C(1)$。 假设对于 $N=n$，满足 $C(n) \le C(n+1)$。 根据递归式，有：

$$ \begin{eqnarray*} & C(n) & \le C(\lfloor n/2 \rfloor) + 1 \newline \newline & C(n+1) & \le \begin{cases} C(\lfloor n/2 \rfloor) +1 & \text{$n$ 是偶数} \newline C(\lfloor n/2 \rfloor + 1) + 1 & \text{$n$ 是奇数} \end{cases}\newline \newline & C(n+2) & \le C(\lfloor n/2 \rfloor + 1) + 1 \end{eqnarray*} $$

又 $ C(n) \le C(n+1) ​$ ，推出 $ C(\lfloor n/2 \rfloor) + 1 \le C(\lfloor n/2 \rfloor + 1) + 1 ​$。 故 $ C(n+1) \le C(n+2) ​$，由数学归纳法，$ C(n) \le C(n+1) ​$ 成立。

已知当 $N = 2^k - 1$ 时，有 $ C(N) \le k = \lg(N+1) \le \lg N + 1$。 接下来证明在 $(2^k - 1, 2^{k + 1} -1) $ 范围内上式仍然成立。 不妨设 $0 < M < 2^k$ ，则有 $2^k - 1 < N + M < 2^{k + 1} -1 $。 转变为证：$C(N+M) \le \lg (N+M) + 1$ 。 由于 $C(N+M)$ 是一个整数，则 $\lfloor \lg(N+M) +1\rfloor = k+1$。 即求证： $C(N+M) \le k+1$。 由单调性可得 $ C(N+M) \le C(2^{k+1} - 1) \le k+1 ​$，得证。