记 $\sigma(k)$ 为正整数 $k$ 的所有正约数之和。设 $n$ 为正整数, 求证: $\sum_{k=1}^n \sigma(k)=\sum_{k=1}^n k\left\lfloor\frac{n}{k}\right\rfloor$ 。
Denote by $\sigma(k)$ the sum of all positive divisors of positive integer $k$. For any positive integer $n$, prove that $\sum_{k=1}^n \sigma(k)=\sum_{k=1}^n k\left\lfloor\frac{n}{k}\right\rfloor$.
因为$\sigma(k)$ 是 k 的所有因子的和, 因此考虑交换求和符号的顺序来证明这个问题. 例如$n=6$时, 我们列一个$6 \times 6$的数据表, 其中第$k$行所有的非零元素都是$k$的因子.
1 0 0 0 0 0
1 2 0 0 0 0
1 0 3 0 0 0
1 2 0 4 0 0
1 0 0 0 5 0
1 2 3 0 0 6
这样, 按照行相加恰好就是要证明等式的左边, 按照列相加, 恰好就是要证明等式的右边.
定义函数$f(j, k)= \begin{cases}1, & j \mid k \\ 0, & j \nmid k\end{cases}$, 则
$$ \begin{aligned} & \sum_{k=1}^n \sigma(k) \\ = & \sum_{k=1}^n \sum_{j=1}^n j \cdot f(j, k) \\ = & \sum_{j=1}^n \sum_{k=1}^n j \cdot f(j, k) \\ = & \sum_{j=1}^n j \cdot \sum_{k=1}^n f(j, k) \\ = & \sum_{j=1}^n j \cdot\left\lfloor\frac{n}{j}\right\rfloor \\ = & \sum_{k=1}^n k \cdot\left\lfloor\frac{n}{k}\right\rfloor \end{aligned} $$
添加微信
可以更快获取解答（请注明有偿答疑）
最后修改于1月22日
下一篇：问题111: 一架小飞机有 4 排座位，每排有 3 个座位。已经有八名乘客登机，他们在这些座位中随机就坐.