重新发现 Calkin's identity

考虑和式 $\sum_{i=0}^{n-1} \left(\sum_{j=0}^i \binom n j\right)^3$ 的结果。 设答案为 $S$，我们考虑另一个和式： $$ \sum_{i,j,k}\binom n i \binom n j \binom n k \cdot \left( \max\{i,j,k\} - \min\{i,j,k\} \right) $$ 它有一种算法，就是枚举每个间隔，假设 $[i,i+1]$ 这个间隔在 $\max - \min$ 内，有 $2^{3n} - \left(\sum_{j=0}^i \binom n j\right)^3 - \left(\sum_{j=0}^{n-i-1} \binom n j\right)^3$ 种方案，这是容斥掉在它两边的情况得到的。对 $i$ 求和，得到的就是 $n2^{3n} - 2S$。 另一种算法，是考虑到一个优秀的性质：$2(\max\{i,j,k\} - \min\{i,j,k\}) = |i - j| + |j - k| + |k - i|$。 这样一来，和式就被变成了只和两个变量独立的情况。也就是 $$ \sum_{i,j,k}\binom n i \binom n j \binom n k \cdot \left( \max\{i,j,k\} - \min\{i,j,k\} \right) = \frac 3 2 \cdot 2^n \sum_{i,j} \binom n i \binom n j |i - j| $$ 后者的推导并不困难： $$ \begin{aligned} & \quad \sum_{i,j} \binom n i \binom n j |i - j| \\ & = 2\sum_{i\ge j} \binom n i \binom n j (i - j) \\ & = 2n\sum_{i\ge j} \left[ \binom {n-1}{i - 1} \binom n j - \binom n i \binom{n - 1}{j - 1} \right]\\ & = 2n\sum_{d \ge 0} \sum_{d = i - j} \left[ \binom {n-1}{j + d - 1} \binom n {n - j} - \binom n {j + d} \binom{n - 1}{n - j} \right]\\ & = 2n\sum_{d \ge 0} \left[ \binom {2n-1}{n + d - 1} - \binom{2n - 1}{n + d} \right]\\ & = 2n \binom{2n-1}{n-1} = n\binom{2n}{n} \end{aligned} $$ 联立两式，我们就有 $$ \begin{aligned} \frac 3 2 \cdot 2^n \cdot n \binom {2n}n &= n2^{3n} - 2S\\ S &= n 2^{3n - 1} - 3n \cdot 2^{n-2} \binom{2n}{n} \end{aligned} $$