具体数学习题解答——第3章 整值函数 Part1

书籍介绍：

https://book.douban.com/subject/21323941/

github仓库：

https://github.com/Doraemonzzz/Concrete-Mathematics

这次回顾第三章，整值函数。

第3章 整值函数

热身题

1

注意到

$$\begin{aligned} 2^m &\le 2^m + l < 2^{m} + 2^m\\ m &\le \log_2(2^m + l) <m+1\\ m&\le \log_2 n < m+1 \end{aligned}$$

所以

$$m = \lfloor \log_2n \rfloor$$

因此

$$\begin{aligned} m &= \lfloor \log_2n \rfloor\\ l &= n -2^{\lfloor \log_2n \rfloor} \end{aligned}$$

2

如果$x \ge \lfloor x\rfloor + 0.5$，那么结果为$\lceil x \rceil$，否则结果为$\lfloor x\rfloor$，因此结果为

$$\lceil x \rceil [x \ge \lfloor x\rfloor + 0.5] + \lfloor x \rfloor [x < \lfloor x\rfloor + 0.5]$$

3

$$\begin{aligned} m\alpha- 1&< \lfloor m \alpha\rfloor \le m\alpha\\ (m\alpha- 1)n&< \lfloor m \alpha\rfloor n \le m\alpha n\\ mn-1<mn - n/\alpha &< \lfloor m \alpha\rfloor n /\alpha \le mn \end{aligned}$$

注意到$\alpha$为无理数，所以

$$mn-1<mn - n/\alpha < \lfloor m \alpha\rfloor n /\alpha < mn$$

因此

$$\lfloor\lfloor m \alpha\rfloor n /\alpha\rfloor = mn-1$$

4

个人感觉水平0应该是计算。

5

$$\begin{aligned} \lfloor n x\rfloor&=n\lfloor x\rfloor && \Leftrightarrow \\ \lfloor n (\lfloor x\rfloor + \{x\})\rfloor &= n\lfloor x\rfloor && \Leftrightarrow\\ \lfloor n \lfloor x\rfloor +n \{x\}\rfloor&= n\lfloor x\rfloor && \Leftrightarrow\\ n \lfloor x\rfloor +\lfloor n \{x\}\rfloor &= n\lfloor x\rfloor && \Leftrightarrow\\ \lfloor n \{x\}\rfloor &= 0&& \Leftrightarrow\\ n \{x\} & < 1&& \Leftrightarrow\\ \{x\} & <\frac 1 n \end{aligned}$$

6

结论是：

$$\begin{aligned} \lfloor f(x)\rfloor&=\lfloor f(\lceil x\rceil )\rfloor\\ \lceil f(x)\rceil &=\lceil f(\lfloor x\rfloor)\rceil \end{aligned}$$

只证明第一个结论，第二个结论同理可得。

证明：

如果$x = \lceil x\rceil$，那么结论显然成立。

否则$x < \lceil x\rceil$，由$f$递减可得：

$$\begin{aligned} f(x)&> f(\lceil x\rceil) \\ \lfloor f(x)\rfloor & \ge \lfloor f(\lceil x\rceil)\rfloor \end{aligned}$$

如果$\lfloor f(x)\rfloor > \lfloor f(\lceil x\rceil)\rfloor$，注意到

$$\begin{aligned} \lfloor f(x)\rfloor& \le f(x) < \lfloor f(x)\rfloor + 1\\ \lfloor f(\lceil x\rceil)\rfloor& \le f(\lceil x\rceil) < \lfloor f(\lceil x\rceil)\rfloor + 1 \end{aligned}$$

因此

$$\begin{aligned} f(x)&\ge \lfloor f(x)\rfloor \\ &\ge \lfloor f(\lceil x\rceil)\rfloor + 1 && 根据条件\\ & > f(\lceil x\rceil) \end{aligned}$$

由函数的连续性可得存在$x\le y < \lceil x\rceil$，满足

$$f(y) = \lfloor f(x)\rfloor$$

这推出$y$为整数，但是这与$x\le y < \lceil x\rceil$矛盾。

7

$$\begin{aligned} X_{n}&=X_{n-m}+1\\ &= X_{n- m\lfloor n/m \rfloor} + \lfloor n/m \rfloor \\ &= n- m\lfloor n/m \rfloor + \lfloor n/m \rfloor\\ &= (n\text{ mod }m) + \lfloor n/m \rfloor\ \end{aligned}$$

8

利用反证法。

如果每个盒子的物品数量$< \lceil n / m\rceil$，注意到物品数量为整数，这等价于每个盒子的物品数量$\le \lceil n / m\rceil - 1$，那么物品总数

$$\le m \times (\lceil n / m\rceil-1) <m \times n / m = n$$

这就产生了矛盾。

如果每个盒子的物品数量$> \lfloor n / m\rfloor$，注意到物品数量为整数，这等价于每个盒子的物品数量$\ge \lfloor n / m\rfloor + 1$，那么物品总数

$$\ge m\times (\lfloor n / m\rfloor + 1) > m \times (n/m)=n$$

这就产生了矛盾。

9

考虑递归的转换过程：

$$(m,n)\to (mq-n, nq)$$

只要证明$mq-n < m$即可，因为如果该性质满足，那么最多经过$m-1$步，$mq-n$就会变成$1$，递归停止。

注意到

$$\begin{aligned} \frac n m &\le q =\left\lceil \frac n m \right\rceil< \frac n m + 1\\ n &\le m q < n + m\\ 0&\le mq- n< m \end{aligned}$$

因此结论成立。

基础题

10

注意到

$$\left\lceil \frac{2 x+1}{4}\right \rceil-\left\lfloor\frac{2 x+1}{4}\right\rfloor=\begin{cases} 1 & \frac{2 x+1}{4}不是整数\\ 0 & \frac{2 x+1}{4}是整数 \end{cases}$$

所以

$$\begin{aligned} \left\lceil\frac{2 x+1}{2}\right\rceil-\left\lceil\frac{2 x+1}{4}\right\rceil+\left\lfloor\frac{2 x+1}{4}\right\rfloor &= \left\lceil\frac{2 x+1}{2}\right\rceil-r \\ &= \left\lceil x +\frac 1 2 - r\right\rceil \\ &=\begin{cases} \left\lceil x -\frac 1 2 \right\rceil & \frac{2 x+1}{4}不是整数\\ \left\lceil x +\frac 1 2 \right\rceil & \frac{2 x+1}{4}是整数 \end{cases} \end{aligned}$$

注意到$\frac{2x+1}{4}$为整数等价于

$$x= 2k-\frac 1 2 , k\in \mathbb Z$$

所以此时

$$\left\lceil x +\frac 1 2 \right\rceil = 2k =\lceil x \rceil$$

另一方面

$$\begin{aligned} \left\lceil x -\frac 1 2 \right\rceil &=\left\lceil \lfloor x \rfloor +\{x\}-\frac 1 2 \right\rceil\\ &=\begin{cases} \lfloor x \rfloor & \{x\} \le \frac 1 2\\ \lfloor x \rfloor +1 & \{x\}> \frac 1 2 \end{cases}\\ &= \begin{cases} \lfloor x \rfloor & \{x\} \le \frac 1 2\\ \lceil x \rceil & \{x\}> \frac 1 2 \end{cases} \end{aligned}$$

综上

$$\begin{aligned} \left\lceil\frac{2 x+1}{2}\right\rceil-\left\lceil\frac{2 x+1}{4}\right\rceil+\left\lfloor\frac{2 x+1}{4}\right\rfloor &=\begin{cases} \left\lceil x -\frac 1 2 \right\rceil & \frac{2 x+1}{4}不是整数\\ \left\lceil x +\frac 1 2 \right\rceil & \frac{2 x+1}{4}是整数 \end{cases}\\ &=\begin{cases} \left\lceil x \right\rceil & \frac{2 x+1}{4}是整数或\{x\}>\frac 1 2 \\ \lfloor x \rfloor & 其他\\ \end{cases} \end{aligned}$$

11

如果$\alpha= \beta$，区间$(\alpha,\beta) =\varnothing$，所以要排除。

如果$\alpha <\beta$，假设整数$n$在该区间内，那么

$$\alpha < n < \beta$$

根据73页3.7可得，这等价于

$$\lfloor \alpha \rfloor < n < \lceil \beta\rceil$$

所以$(\alpha,\beta)$内的整数为

$$\lfloor \alpha \rfloor + 1 ,\ldots, \lceil \beta\rceil -1$$

因此整数数量为

$$\lceil \beta\rceil -1 - \lfloor \alpha \rfloor - 1 + 1 =\lceil \beta\rceil- \lfloor \alpha \rfloor - 1$$

12

假设

$$n = km + r, 0\le r < m$$

那么

$$\begin{aligned} \left\lceil \frac{n}{m}\right\rceil &= k + [r\ne 0] \\ \left\lfloor\frac{n+m-1}{m}\right\rfloor &= \left\lfloor\frac{km+r+m-1}{m}\right\rfloor \\ &=k+1 +\left\lfloor\frac{r-1}{m}\right\rfloor \\ &= k+1- [r= 0] \\ &=k + [r\ne 0] \end{aligned}$$

因此

$$\left\lceil \frac{n}{m}\right\rceil=\left\lfloor\frac{n+m-1}{m}\right\rfloor$$

13

结合课本80页的结论，$\operatorname{Spec}(\alpha)$ 和 $\operatorname{Spec}(\beta)$ 给出了正整数的划分等价于，对于任意的$n\in \mathbb Z^+$，都有

$$\begin{aligned} \left\lfloor \frac{n+1}{\alpha}\right\rfloor+\left\lfloor\frac{n+1}{\beta}\right\rfloor&=n \\ \frac{n+1}{\alpha}-\left\{ \frac{n+1}{\alpha}\right\}+\frac{n+1}{\beta}-\left\{ \frac{n+1}{\beta}\right\}&=n\\ (n+1)\left(\frac 1\alpha + \frac 1 \beta - 1\right) &= \left\{ \frac{n+1}{\alpha}\right\}+\left\{ \frac{n+1}{\beta}\right\} - 1 \end{aligned}$$

接着分两个方向证明。

$\Rightarrow$：

注意到

$$\left\{ \frac{n+1}{\alpha}\right\}+\left\{ \frac{n+1}{\beta}\right\} - 1 \in [-1, 1)$$

因此

$$\begin{aligned} \left| (n+1)\left(\frac 1\alpha + \frac 1 \beta - 1\right)\right| &\le 1,\forall n\in \mathbb Z^+ \\ \left|\left(\frac 1\alpha + \frac 1 \beta - 1\right)\right| &\le \frac 1 { n+1},\forall n\in \mathbb Z^+ \\ \end{aligned}$$

令$n\to \infty$可得

$$\begin{aligned} \left| \frac 1\alpha + \frac 1 \beta - 1 \right| &\le 0\\ \frac 1\alpha + \frac 1 \beta &= 1 \end{aligned}$$

$\Leftarrow$：

如果

$$\frac 1\alpha + \frac 1 \beta = 1$$

要证明

$$(n+1)\left(\frac 1\alpha + \frac 1 \beta - 1\right) = \left\{ \frac{n+1}{\alpha}\right\}+\left\{ \frac{n+1}{\beta}\right\} - 1$$

只需证明

$$\left\{ \frac{n+1}{\alpha}\right\}+\left\{ \frac{n+1}{\beta}\right\} - 1=0$$

注意到$\frac{n+1}{\alpha}$和$\frac{n+1}{\beta}$都是无理数，且和为整数：

$$\frac{n+1}{\alpha}+ \frac{n+1}{\beta}=n+1$$

因此下式成立：

$$\left\{ \frac{n+1}{\alpha}\right\}+\left\{ \frac{n+1}{\beta}\right\} - 1=0$$

结论得证。

14

注意到

$$x \bmod y = z \bmod y \Leftrightarrow x-z = ky, k\in\mathbb Z$$

所以该命题等价于

$$\begin{aligned} (x \bmod ny) - x &= ky, k\in \mathbb Z\\ x- ny\lfloor x/ (ny)\rfloor - x & = ky , k\in \mathbb Z\\ - ny\lfloor x/ (ny)\rfloor & = ky, k\in \mathbb Z\\ -n\lfloor x/ (ny)\rfloor & = k,k\in \mathbb Z \end{aligned}$$

因此结论成立。

15

考虑71页3.24

$$n=\left\lceil\frac{n}{m}\right\rceil+\left\lceil\frac{n-1}{m}\right\rceil+\cdots+\left\lceil\frac{n-m+1}{m}\right \rceil$$

取

$$n=\left\lceil m x\right\rceil$$

利用60页3.11可得

$$\begin{aligned} \left\lceil m x\right\rceil &=\left\lceil\frac{\lceil m x \rceil}{m}\right\rceil+\left\lceil\frac{\lceil m x \rceil-1}{m}\right\rceil+\cdots+\left\lceil\frac{\lceil m x \rceil-m+1}{m}\right \rceil \\ &=\left\lceil\frac{ m x }{m}\right\rceil+\left\lceil\frac{m x -1}{m}\right\rceil+\cdots+\left\lceil\frac{ m x -m+1}{m}\right \rceil\\ &= \left\lceil x\right\rceil+\left\lceil x-\frac{ 1}{m}\right\rceil+\cdots+\left\lceil x-\frac{m-1}{m}\right \rceil \end{aligned}$$

16

这里$n$应该是指整数，所以

$$n \bmod 2=\begin{cases} 0 & n = 2k, k\in \mathbb Z\\ 1 & n = 2k+1, k\in \mathbb Z \end{cases}= \left(1-(-1)^{n}\right) / 2$$

对于另一种情形：

$$n \bmod 3=\begin{cases} 0 & n = 3k, k\in \mathbb Z\\ 1 & n = 3k+1, k\in \mathbb Z\\ 2 & n = 3k+2, k\in \mathbb Z\\ \end{cases}$$

现在需要用下式统一表达

$$a+b \omega^{n}+c \omega^{2 n}$$

因此

$$\begin{aligned} &\begin{cases} a + b\omega^{3k} + c \omega^{6k} = 0\\ a + b\omega^{3k+1} + c \omega^{6k+2} = 1\\ a + b\omega^{3k+2} + c \omega^{6k+4} = 2 \end{cases}\\ &\begin{cases} a + b + c = 0\\ a + b\omega + c \omega^2 = 1\\ a + b\omega^2 + c \omega^4 = 2 \end{cases}\\ \end{aligned}$$

求解可得

$$\begin{cases} a = 1\\ b = -\frac{\omega}{\omega- 1}\\ c= \frac{1}{\omega - 1} \end{cases}$$

因此

$$n \bmod 3=1- \frac{\omega^{n+1} -\omega^{2n} }{\omega - 1}$$

17

根据86页3.26可得

$$\sum_{0 \le k<m}\lfloor x+k / m\rfloor = \lfloor m x\rfloor$$

另一方面

$$\begin{aligned} \sum_{0 \le k<m}\lfloor x+k / m\rfloor = &\sum_{0 \le k<m}\sum_{j}[1 \le j \le x+k / m]\\ =& \sum_{j} \sum_{0 \le k<m}[1 \le j \le x+k / m]\\ =& \sum_{j} \sum_{0 \le k<m}[m(j-x) \le k][1\le j]\\ =& \sum_{j} \sum_{k }[m(j-x) \le k] [0 \le k][k < m][1\le j]\\ =& \sum_{j} \sum_{k}[m(j-x) \le k] [0 \le k][k < m][1\le j\le \lceil x \rceil -1 ]\\ &+\sum_{j} \sum_{k}[m(j-x) \le k] [0 \le k][k < m][\lceil x \rceil \le j < x+1]\\ =& \sum_{j=1}^{\lceil x \rceil -1} \sum_{k=0}^{m-1} 1 +\sum_{j=\lceil x \rceil} \sum_{k}[m(j-x) \le k < m] \\ =& m(\lceil x \rceil -1)+(m- \lceil m(\lceil x \rceil-x)\rceil )\ 根据 77页公式\\ =&m\lceil x \rceil -\lceil m(\lceil x \rceil-x)\rceil\\ =& m\lceil x \rceil- m\lceil x \rceil - \lceil m(-x)\rceil\\ =& \lfloor mx\rfloor \end{aligned}$$

18

$$\begin{aligned} S&= \sum_{0 \le j<\lceil n \alpha\rceil} \sum_{k>n}\left[j \alpha^{-1} \le k<(j+v) \alpha^{-1}\right]\\ &= \sum_{0 \le j<n \alpha} \sum_{k>n}\left[j \alpha^{-1} \le k<(j+v) \alpha^{-1}\right]\\ &\le \sum_{k>n}\left[j \alpha^{-1} \le k<(n\alpha +v) \alpha^{-1}\right]\\ & \le \sum_{k}\left[n \le k<n+\alpha^{-1}v \right]\\ &= \lceil \alpha^{-1}v + n\rceil - \lceil n\rceil \\ &=\lceil \alpha^{-1}v\rceil \end{aligned}$$

作业题

19

设

$$m= \left\lfloor\log _{b} x\right\rfloor$$

那么该等式等价于

$$\begin{aligned} m&\le \log _{b}\lfloor x\rfloor < m+1 \\ b^m &\le \lfloor x\rfloor < b^{m+1} \end{aligned}$$

如果$b$是整数，那么上式等价于

$$\begin{aligned} b^m &\le x < b^{m+1}\\ \log_b x - 1 &< m \le \log_b x \end{aligned}$$

显然$m$满足该条件。

如果$b$不是整数，那么取$x=b$，我们有

$$\begin{aligned} \left\lfloor\log _{b} x\right\rfloor & = 1\\ \lfloor\log _{b}\lfloor x\rfloor \rfloor&= 0 \end{aligned}$$

此时结论不成立。

因此充要条件是$b$是整数。

20

$$\begin{aligned} \sum_{\alpha \le i \le \beta, i=kx, k\in \mathbb Z} i &= \sum_{\alpha /x \le k \le \beta /x, k\in \mathbb Z} kx\\ &= \sum_{\lceil \alpha /x \rceil \le k \le \lfloor \beta /x \rfloor, k\in \mathbb Z} kx\\ &= x\frac{(\lceil \alpha /x \rceil+ \lfloor \beta /x \rfloor)(\lfloor \beta /x \rfloor-\lceil \alpha /x \rceil + 1)}{2} \end{aligned}$$

21

对于自然数$n$，其十进制表示为

$$n=\sum_{i=0}^{l-1}a_i 10^i$$

如果$a_{l-1}=1$，那么

$$\begin{aligned} n &\ge 10^{l-1}\\ n & \le 10^{l-1}+\sum_{i=0}^{l-2}9\times 10^i\\ &= 2\times 10^{l-1} -1 \\ 10^{l-1}&\le n \le 2\times 10^{l-1} -1 \end{aligned}$$

将$n=2^m$代入可得

$$\begin{aligned} 10^{l-1}&\le 2^m \le 2\times 10^{l-1} -1\\ (l-1)\log_210 &\le m \le \log_2(2\times 10^{l-1} -1) < 1 + (l-1)\log_210 \end{aligned}$$

所以对于固定的$l$，只有一个整数$m$满足条件，注意到$2^{M}$的十进制表示位数为$\lfloor \log_{10}2^M\rfloor + 1\triangleq k$，因此结果为

$$k= \lfloor \log_{10}2^M\rfloor + 1$$

22

假设$n$的二进制表示为

$$n=\sum_{i=0}^{l-1} n_i \times 2^i, l = \lfloor \log_{2}n\rfloor + 1$$

那么

$$\begin{aligned} S_n &=\sum_{k \ge 1}\left\lfloor n / 2^{k}+\frac{1}{2}\right\rfloor\\ &= \sum_{k \ge 1}\left\lfloor \left(\sum_{i=0}^{l-1} n_i \times 2^i\right) /2^k+\frac{1}{2}\right\rfloor\\ &=\sum_{k =1}^{l}\left\lfloor \left(\sum_{i=0}^{l-1} n_i \times 2^i\right) /2^k+\frac{1}{2}\right\rfloor\\ &=\sum_{k =1}^{l}\left\lfloor \left(\sum_{i=k}^{l-1} n_i \times 2^{i-k}\right) +\frac{n_{k-1}+1}{2} + \left(\sum_{i=1}^{k-2} n_i \times 2^{i-k}\right)\right\rfloor \\ &= \sum_{k =1}^{l} \left(\sum_{i=k}^{l-1} n_i \times 2^{i-k}\right) + \sum_{k =1}^{l} \left\lfloor \frac{n_{k-1}+1}{2} \right\rfloor\\ &=\sum_{i=1}^{l-1}n_i \sum_{k=1}^{i}2^{i-k}+\sum_{i=0}^{l-1} n_i\\ &=\sum_{i=1}^{l-1}n_i (2^i-1)+\sum_{i=0}^{l-1} n_i\\ &=\sum_{i=0}^{l-1}n_i 2^i\\ &= n \end{aligned}$$

对于$T_n$，我们有

$$\begin{aligned} T_n &=\sum_{k \ge 1}2^k\left\lfloor n / 2^{k}+\frac{1}{2}\right\rfloor^2\\ &= \sum_{k \ge 1}2^k\left\lfloor \left(\sum_{i=0}^{l-1} n_i \times 2^i\right) /2^k+\frac{1}{2}\right\rfloor^2\\ &=\sum_{k =1}^{l}2^k\left\lfloor \left(\sum_{i=0}^{l-1} n_i \times 2^i\right) /2^k+\frac{1}{2}\right\rfloor^2\\ &=\sum_{k =1}^{l}2^k\left\lfloor \left(\sum_{i=k}^{l-1} n_i \times 2^{i-k}\right) +\frac{n_{k-1}+1}{2} + \left(\sum_{i=1}^{k-2} n_i \times 2^{i-k}\right)\right\rfloor^2 \\ &=\sum_{k =1}^{l}2^k\left(\left(\sum_{i=k}^{l-1} n_i \times 2^{i-k}\right) +n_{k-1} \right)^2 \\ &= \sum_{k =1}^{l}2^k\left(\left(\sum_{i=k}^{l-1} n_i \times 2^{i-k}\right) ^2+2\left(\sum_{i=k}^{l-1} n_i \times 2^{i-k}\right)n_{k-1} + n_{k-1}^2 \right) \end{aligned}$$

这样是很难的计算的，下面从递归的角度考虑。

假设$n=2^m(2l+1)$，即

$$n=\sum_{i=m}^{l-1} n_i 2^i=2^m + \sum_{i=m+1}^{l-1} n_i 2^i$$

那么

$$n-1=2^m -1+ \sum_{i=m+1}^{l-1} n_i 2^i$$

对于$k> m +1$，

$$\begin{aligned} \left\lfloor n / 2^{k}+\frac{1}{2}\right\rfloor &=\left\lfloor \sum_{i=m+1}^{l-1} n_i 2^{i-k} + 2^{m-k} +\frac 1 2\right\rfloor\\ &= \left\lfloor \sum_{i=m+1}^{k-2}n_i 2^{i-k} +\sum_{i=k}^{l-1} n_i 2^{i-k} +\frac{n_{k-1}}{2} +\frac 1 2\right\rfloor\\ &= \sum_{i=k}^{l-1} n_i 2^{i-k} + n_{k-1} \\ \left\lfloor (n-1) / 2^{k}+\frac{1}{2}\right\rfloor &=\left\lfloor \sum_{i=m+1}^{l-1} n_i 2^{i-k} + 2^{m-k}-\frac 1 {2^k} +\frac 1 2\right\rfloor\\ &= \left\lfloor \sum_{i=m+1}^{k-2}n_i 2^{i-k} +\sum_{i=k}^{l-1} n_i 2^{i-k} -\frac 1 {2^k}+\frac{n_{k-1}}{2} +\frac 1 2\right\rfloor\\ &= \sum_{i=k}^{l-1} n_i 2^{i-k} + n_{k-1} \end{aligned}$$

这里利用了如下事实：

$$\begin{aligned} \sum_{i=m+1}^{k-2}n_i 2^{i-k} &\le \sum_{i=m+1}^{k-2}2^{i-k}\\ &< 2^{m+1-k}\\ &\le \frac 1 4 (因为m+1 \le k -2)\\ \sum_{i=m}^{k-2}n_i 2^{i-k}&\ge n_m 2^{m-k}\\ &\ge 2^{m-k}\\ \sum_{i=m}^{k-2}n_i 2^{i-k} -\frac 1 {2^k} &\ge 2^{m-k} -\frac 1 {2^k}\\ &\ge 0 \\ \sum_{i=m}^{k-2}n_i 2^{i-k} -\frac 1 {2^k} &< \frac 1 4 \end{aligned}$$

对于$k< m + 1$，

$$\begin{aligned} \left\lfloor n / 2^{k}+\frac{1}{2}\right\rfloor &=\left\lfloor 2^{m-k} + \sum_{i=m+1}^{l-1} n_i 2^{i-k}+\frac{1}{2}\right\rfloor\\ &= 2^{m-k} + \sum_{i=m+1}^{l-1} n_i 2^{i-k}\\ \left\lfloor (n-1) / 2^{k}+\frac{1}{2}\right\rfloor &=\left\lfloor 2^{m-k} -1/2^k + \sum_{i=m+1}^{l-1} n_i 2^{i-k}+\frac{1}{2}\right\rfloor\\ &= 2^{m-k} + \sum_{i=m+1}^{l-1} n_i 2^{i-k} \end{aligned}$$

对于$k=m+1$，

$$\begin{aligned} \left\lfloor n / 2^{k}+\frac{1}{2}\right\rfloor &=\left\lfloor (2^m(2l+1)) / 2^{k}+\frac{1}{2}\right\rfloor\\ &= \left\lfloor (2^{m}(2l+1)) / 2^{m+1}+\frac{1}{2} \right\rfloor\\ &=\left\lfloor (2l+1) / 2+\frac{1}{2} \right\rfloor\\ &= l+1 \\ \left\lfloor (n-1) / 2^{k}+\frac{1}{2}\right\rfloor &=\left\lfloor (2^m(2l+1) -1) / 2^{k}+\frac{1}{2}\right\rfloor\\ &= \left\lfloor (2^{m}(2l+1)) / 2^{m+1}-\frac 1 {2^k}+\frac{1}{2} \right\rfloor\\ &=\left\lfloor l+ 1 -\frac 1 {2^k} \right\rfloor\\ &= l\\ \end{aligned}$$

因此

$$\begin{aligned} T_n &= T_{n-1}+ 2^{m+1}\left( l+1\right)^2 - 2^{m+1}l^2\\ &= T_{n-1}+2^{m+1} (2l+1)\\ &=T_{n-1}+ 2n \end{aligned}$$

其中

$$n= 2^m (2l+1)$$

注意到

$$T_0 = 0$$

因此

$$T_n = n(n+1)$$

23

由定义可得，

$$a_n= k$$

当且仅当

$$1+\sum_{j=1}^{k-1}j=1+\frac{k(k-1)}{2} \le n \le \sum_{j=1}^{k}j=\frac{k(k+1)}{2}$$

对其化简可得

$$\begin{aligned} 2+k^2 - k &\le 2n \le k^2 + k\\ 2+\left(k-\frac 1 2 \right)^2 -\frac1 4 &\le 2n \le \left(k+\frac 1 2 \right)^2 -\frac1 4\\ \left(k-\frac 1 2 \right)^2 & \le 2n -\frac 7 4 \\ \left(k+\frac 1 2 \right)^2 &\ge 2n +\frac 14\\ \sqrt{2n+\frac 1 4} -\frac 1 2 &\le k \le \sqrt{2n -\frac 7 4}+ \frac 12 \le \sqrt{2n }+ \frac 12 \end{aligned}$$

注意到

$$\sqrt{2n }+ \frac 12 - \left(\sqrt{2n+\frac 1 4} -\frac 1 2\right) < 1$$

所以该区间长度小于$1$，因此

$$k= \left\lfloor\sqrt{2 n}+\frac{1}{2}\right\rfloor$$

24

设

$$\begin{aligned} u&=\frac{1}{\alpha}\\ v&= \frac{\alpha+1}{\alpha} \end{aligned}$$

那么

$$v- u =1$$

考虑第80页定义的$N(\alpha, n)$，我们有

$$\begin{aligned} N(v, n) - N(u,n) &= \lceil(n+1) / v\rceil-1 -\left(\lceil(n+1) / u\rceil-1\right)\\ &= \lceil(n+1) / v\rceil - \lceil(n+1) / u\rceil\\ &= \lfloor(n+1) / v\rfloor - \lfloor(n+1) / u\rfloor + [(n+1) / v是整数] -[(n+1) / u是整数]\\ &= (n+1) / v - \{(n+1) / v\}-(n+1) / u + \{(n+1) / u\}+ [(n+1) / v是整数] -[(n+1) / u是整数] \end{aligned}$$

注意到

$$(n+1) / v - (n+1) / u= n+1$$

所以

$$\begin{aligned} N(v, n) - N(u,n) &= (n+1) / v - \{(n+1) / v\}-(n+1) / u + \{(n+1) / u\}+ [(n+1) / v是整数] -[(n+1) / u是整数]\\ &=n +1 \end{aligned}$$

考虑$n$在两个集合中出现的次数之差，显然为

$$N(v,n) - N(v,n-1) -\left(N(u,n) - N(u,n-1)\right)=1$$

因此对于任意$n\in \mathbb N$，$n$出现在$\text{Spec}(v)$的次数为其出现在$\text{Spec}(u)$的次数加$1$。

25

利用反证法，如果存在$n$，使得

$$K_{n+1}<n +1$$

那么

$$\begin{aligned} 1+\min \left(2 K_{\lfloor n / 2\rfloor}, 3 K_{\lfloor n / 3\rfloor}\right) & < n + 1\\ \min \left(2 K_{\lfloor n / 2\rfloor}, 3 K_{\lfloor n / 3\rfloor}\right) & < n \\ K_{\lfloor n / 2\rfloor} & < n/2 或\\ K_{\lfloor n / 3\rfloor} & < n/3 \end{aligned}$$

注意到$\lfloor n / 2\rfloor,\lfloor n / 3\rfloor$严格小于$n$，并且依然是一个反例，所以经过有限步后必然后可以得到

$$K_i < i, i < 3$$

这就与实际情况相矛盾，因此原结论成立。

26

利用数学归纳法即可。

$n=0$时结论显然成立，假设$n=k-1$时结论成立，下面证明$n=k$时结论也成立。

注意到我们有

$$\begin{aligned} \frac{q}{q-1}\left(\frac{q}{q-1}\right)^{k-1} &\le \frac{q}{q-1} D_{k-1}^{(q)}\le \frac{q}{q-1}q\left(\frac{q}{q-1}\right)^{k-1}\\ \left(\frac{q}{q-1}\right)^{k} &\le \frac{q}{q-1} D_{k-1}^{(q)}\le q\left(\frac{q}{q-1}\right)^{k} \end{aligned}$$

注意到$q$为整数，并且除了$q=2$的情形，$ q\left(\frac{q}{q-1}\right)^{k}$都不是整数，因此总有

$$\left(\frac{q}{q-1}\right)^{k} \le \left\lceil \frac{q}{q-1} D_{k-1}^{(q)} \right\rceil = D^{(q)}_k\le q\left(\frac{q}{q-1}\right)^{k}$$

所以$n=k$时结论也成立。

27

这部分参考了习题解答。

证明：

假设

$$D^{(3)}_n =2 ^{l}\times (2k+1) - a, a=0或1$$

那么

$$D^{(3)}_{n+l} =3 ^{l}\times (2k+1) -a$$

如果$a=0$，那么$D^{(3)}_n$为偶数，此时$D^{(3)}_{n+l}$为奇数。

如果$a=1$，那么$D^{(3)}_n$为奇数，此时$D^{(3)}_{n+l}$为偶数。

这说明$D^{(3)}_n$有无限多个偶数和奇数。

28

此题太难，见习题解答。

29

这部分内容在课本74页。

因为$\varepsilon < v\alpha ^{-1}, S-v^\prime \in [0, v\alpha ^{-1}]$，所以

$$\begin{aligned} |S-v^{\prime}-\varepsilon| &< v \alpha^{-1} \end{aligned}$$

因此

$$\begin{aligned} |s(\alpha, n, v)| &=\left|-s\left(\alpha^{\prime},\lceil n \alpha\rceil, v^{\prime}\right)-S+\varepsilon+\{0 \text { 或者 } 1\} \right|\\ &= \left|-s\left(\alpha^{\prime},\lfloor n \alpha\rfloor, v^{\prime}\right)- \left(\left\lfloor \lceil n \alpha\rceil \alpha^{\prime}\right\rfloor-\left\lfloor \lceil n \alpha\rceil \alpha^{\prime}-v^{\prime}\right\rfloor-v^{\prime}\right) -S+\varepsilon+\{0 \text { 或者 } 1\} \right| \\ &= \left|-s\left(\alpha^{\prime},\lfloor n \alpha\rfloor, v^{\prime}\right)+v^{\prime}-\{0 \text { 或者 } 1\} -S+\varepsilon+\{0 \text { 或者 } 1\} \right|\\ &\ge \left|s\left(\alpha^{\prime},\lceil n \alpha\rceil, v^{\prime}\right)\right| - |S-v^{\prime}-\epsilon| - 2\\ &> \left|s\left(\alpha^{\prime},\lceil n \alpha\rceil, v^{\prime}\right)\right| - v \alpha^{-1} - 2\\ &> \left|s\left(\alpha^{\prime},\lceil n \alpha\rceil, v^{\prime}\right)\right| -\alpha^{-1} -2 \end{aligned}$$

两边取上界可得

$$D(\alpha, n) \ge D\left(\alpha^{\prime},\lfloor\alpha n\rfloor\right)-\alpha^{-1}-2$$

30

注意到

$$\alpha +\alpha^{-1} = m= X_0$$

对上式平方可得

$$\begin{aligned} \alpha^{2^1} + \alpha^{-2^1}+2 &= X_0^2\\ \alpha^{2^1} + \alpha^{-2^1} &= X_0^2 -2=X_1\\ \end{aligned}$$

类似的，利用归纳法不难得到

$$\alpha^{2^n} + \alpha^{-2^n} = X_n$$

注意到

$$0<\alpha^{-1} < 1$$

因此

$$X_n = \left\lceil\alpha^{2^{n}} \right\rceil$$

31

利用等价变换：

$$\begin{aligned} &\lfloor x\rfloor+\lfloor y\rfloor+\lfloor x+y\rfloor \le \lfloor 2 x\rfloor+\lfloor 2 y\rfloor \\ \Leftrightarrow&\lfloor x\rfloor+\lfloor y\rfloor+\lfloor \lfloor x\rfloor+\{x\} +\lfloor y\rfloor+\{y\} \rfloor \le \lfloor 2 (\lfloor x\rfloor+\{x\})\rfloor+\lfloor 2 (\lfloor y\rfloor+\{y\})\rfloor \\ \Leftrightarrow&\lfloor x\rfloor+\lfloor y\rfloor+\lfloor x\rfloor+\lfloor y\rfloor+\lfloor \{x\} +\{y\} \rfloor \le 2 \lfloor x\rfloor +\lfloor 2\{x\}\rfloor+2 \lfloor y\rfloor +\lfloor 2\{y\}\rfloor \\ \Leftrightarrow& \lfloor \{x\} +\{y\} \rfloor \le \lfloor 2\{x\}\rfloor + \lfloor 2\{y\}\rfloor \end{aligned}$$

如果$\{x\}\ge 0.5$且$\{y\}\ge 0.5$，那么

$$\lfloor \{x\} +\{y\} \rfloor =1\le 2=\lfloor 2\{x\}\rfloor + \lfloor 2\{y\}\rfloor$$

如果$\{x\}$和$\{y\}$之间只有一项$\ge 0.5$，那么

$$\lfloor \{x\} +\{y\} \rfloor =0\le 1=\lfloor 2\{x\}\rfloor + \lfloor 2\{y\}\rfloor$$

如果$\{x\}$和$\{y\}$都$< 0.5$，那么

$$\lfloor \{x\} +\{y\} \rfloor =0\le 0=\lfloor 2\{x\}\rfloor + \lfloor 2\{y\}\rfloor$$

32

这题参考了习题解答。

记

$$\begin{aligned} f(x) &=\sum_{k} 2^{k}\left\|x / 2^{k}\right\|^{2}\\ &= \sum_{k\le 0}2^{k}\left\|x / 2^{k}\right\|^{2} + \sum_{k\ge 1}2^{k}\left\|x / 2^{k}\right\|^{2}\\ &\triangleq l(x) + r(x) \end{aligned}$$

首先注意到

$$\begin{aligned} \|-x\|^{2}&= \min (-x-\lfloor -x\rfloor,\lceil -x\rceil+x)^2\\ &= \min (-x+\lceil x\rceil,-\lfloor x\rfloor+x)^2\\ &= \|x\|^{2} \end{aligned}$$

所以

$$f(x)=f(-x)$$

因此只需考虑$x\ge 0$的情形。

根据定义，$|x|$有如下性质：

到当$0\le x <\frac 1 2$时，

$$\|x\| = x$$

对于$n\in \mathbb Z$，

$$\|x+n\| = \|x\|$$

利用这两个性质继续讨论。

对于$l(x)$，注意到

$$\|x\|\le \frac 1 2$$

因此

$$\begin{aligned} l(x)&= \sum_{k\le 0}2^{k}\left\|x / 2^{k}\right\|^{2}\\ &\le \frac 1 2\sum_{k\le 0}2^{k}\\ &\le \frac 1 2 \end{aligned}$$

另一方面，

$$\begin{aligned} l(x+1)&= \sum_{k\le 0}2^{k}\left\|(x+1) / 2^{k}\right\|^{2}\\ &=\sum_{k\le 0}2^{k}\left\|x / 2^{k} + 2^{-k}\right\|^{2}\\ &=\sum_{k\le 0}2^{k}\left\|x / 2^{k} \right\|^{2}\\ &=l(x) \end{aligned}$$

对于$r(x)$，利用第一个性质可得，当$0\le x <1$时，

$$\begin{aligned} r(x)&=\sum_{k\ge 1}2^{k}\left\|x / 2^{k}\right\|^{2}\\ &=\sum_{k\ge 1}2^{k}\left(x / 2^{k}\right)^{2}\\ &= x^2 \\ & < 1 \end{aligned}$$

此时$1\le x + 1 < 2$，所以

$$\begin{aligned} r(x+1)&=\sum_{k\ge 1}2^{k}\left\|(x+1) / 2^{k}\right\|^{2}\\ &=2\left\|(x-1) / 2\right\|^{2}+\sum_{k\ge 2}2^{k}\left\|(x+1) / 2^{k}\right\|^{2}\\ &= (x-1)^2/2 + \sum_{k\ge 2}(x+1)^2 / 2^{k}\\ &=(x-1)^2/2 + (x+1)^2/2\\ &= x^2 + 1\\ &=r(x)+1 \end{aligned}$$

结合上述两点，可得当$0\le x < 1$时，我们有

$$f(x+1) =f(x)+1$$

特别，此时

$$f(x) =l(x)+r(x) <\frac 3 2$$

下面利用归纳法证明，当$0\le x < 1$时，对于任意$n\in \mathbb N$，我们有

$$f(x+n) =f(x)+n$$

注意到这等价于

$$r(x+n)=r(x)+n$$

补充：

在证明之前，注意到

$$\begin{aligned} f(2x)&= \sum_{k} 2^{k}\left\|2x / 2^{k}\right\|^{2}\\ &=\sum_{k} 2^{k}\left\|x / 2^{k-1}\right\|^{2}\\ &=2f(x) \end{aligned}$$

后续的证明中要利用到该结论。

补充结束。

基本情形已证，假设$n\le m$时结论成立，下面证明$n=m+1$时结论也成立。

如果$m=2m_1$，那么

$$\begin{aligned} r(x+m+1)&=\sum_{k\ge 1}2^{k}\left\|(x+m+1) / 2^{k}\right\|^{2}\\ &=2\sum_{k\ge 1}2^{k-1}\left\|((x+1)/2+m_1) / 2^{k-1}\right\|^{2} (注意0<(x+1)/2<1)\\ &=2f((x+1)/2+m_1) \\ &=2 f((x+1)/2) + 2m_1 (由归纳假设) \\ &= f(x+1) + m\\ &= f(x) + m +1 \end{aligned}$$

如果$m=2m_1+1$，那么

$$\begin{aligned} r(x+m+1)&=\sum_{k\ge 1}2^{k}\left\|(x+m+1) / 2^{k}\right\|^{2}\\ &=2\sum_{k\ge 1}2^{k-1}\left\|(x/2+m_1+1) / 2^{k-1}\right\|^{2} (注意0<x/2<1)\\ &=2f(x/2+m_1+1) \\ &=2 f(x/2) + 2m_1+2 (由归纳假设) \\ &= f(x) + m +1 \end{aligned}$$

所以结论对$k=m+1$依然成立。

利用该结论，我们有（这里$m\in \mathbb Z^+$）

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

所以

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

对于第一项，注意到

$$\begin{aligned} 2^{-m}\lfloor 2^m x\rfloor -x &\le 2^{-m} 2^m x -x \\ &=0\\ &> 2^{-m} ( 2^m x-1) -x\\ &> 2^{-m}\\ |2^{-m}\lfloor 2^m x\rfloor -x | & < 2^{-m} \end{aligned}$$

对于第二项，利用之前的结论可得

$$2^{-m} |f(\{ 2^m x\} )| < 2^{-m} \times 3/2$$

令$m\to \infty$可得

$$|f(x)-x| =0\Rightarrow f(x) =x$$

结合$f(x)=f(-x)$，最终的结论是

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

重点

6, 21, 22, 24, 27, 28, 29, 32