3.1.20

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

国内的书中关于命题 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 \\
\\
& C(n+1) & \le
\begin{cases}
C(\lfloor n/2 \rfloor) +1 & \text{$ n $ 是偶数} \\
C(\lfloor n/2 \rfloor + 1) + 1 & \text{$ n $ 是奇数}
\end{cases}\\
\\
& 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 ​$,得证。

上一题 下一题