趣题: 取整函数项的和

趣题: 取整函数项的和 #

题目 #

计算 $$f(n) =\sum_{k = 1}^{\infin}\lfloor\frac{n+2^k}{2^{k+1}}\rfloor$$

Solution 1 #

计算发现 $f(0) = 0, f(1) = 1, f(2) = 2, f(3) = 3$ , 不妨猜测 $f(n) = n$ . 考虑 $f(n + 1)$ , 记 $g(n, k) = \lfloor\frac{n+1+2^k}{2^{k+1}}\rfloor - \lfloor\frac{n+2^k}{2^{k+1}}\rfloor$ , 有 $g(n)$ 取值为 $0$ 或 $1$ , 当且仅当 $2^{k+1} \mid n + 1 + 2^k$ 时取 $1$ . 由于 $2^{k+1}\mid n + 1 + 2^k$ , 有 $2^{k} \mid n + 1$ 且 $2^{k+1}\nmid n + 1 $ , 故 $2^k\parallel n + 1$ . 在 $n$ 取定时这样的 $k$ 唯一, 故 $f(n+1) - f(n) = \sum_{k = 1}^{\infin}g(n, k) = 1$ , 从而 $f(n) = n$ .

Solution 2 #

由 Hermite 恒等式 $$ \sum_{i=0}^{n}\lfloor x + \frac{i}{n}\rfloor = \lfloor nx\rfloor $$ 取 $n = 2$ 有 $$\lfloor x\rfloor + \lfloor x + \frac{1}{2}\rfloor= \lfloor 2x\rfloor $$ 因此有裂项 $$ \lfloor\frac{n+2^k}{2^{k+1}}\rfloor = \lfloor\frac{n}{2^{k+1}} + \frac{1}{2}\rfloor = \lfloor\frac{n}{2^k}\rfloor - \lfloor\frac{n}{2^{k+1}}\rfloor $$ 故 $$f(n) = \lim_{k\to\infin}\lfloor n\rfloor - \lfloor\frac{n}{2^{k+1}}\rfloor = n$$