证明幂和递推公式：$S_{k+1}(n) = n S_k(n) - \sum_{i=1}^{n-1} S_k(i)$

我来一步步帮你把这个递推关系理清楚，结合提示的双重求和和表格辅助，保证你能吃透整个过程~

先明确定义 #

• 已知基础求和公式：$S_{1}(n) = \sum_{i=1}^n i = \frac{n(n+1)}{2}$
• 对任意 $n, k\geq 1$，高阶求和定义为：$S_{k+1}(n) = \sum_{i=1}^n i^{k+1}$

第一步：证明提示中的双重求和等式 $S_{k+1}(n) = \sum_{j=1}^n \sum_{i=j}^n i^k$ #

我们先从 $i^{k+1}$ 的本质入手：$i^{k+1} = i \cdot i^{k$，而$i$个$i}k$相加正好等于$i \cdot i^k$，也就是：
$$i^{k+1} = \sum_{j=1}^i i^k$$

把这个代入$S_{k+1}(n)$的定义里，就得到：
$$S_{k+1}(n) = \sum_{i=1}^n i^{k+1} = \sum_{i=1}^n \sum_{j=1}^i i^k$$

接下来交换求和顺序：原来的求和是先固定$i$，让$j$从1跑到$i$；交换后变成先固定$j$，让$i$从$j$跑到$n$（因为当$j$固定时，所有大于等于$j$的$i$都包含对应的$i^k$项）。这样双重求和就转化为：
$$\sum_{j=1}^n \sum_{i=j}^n i^k$$

用一个具体例子（$n=3, k=1$）的表格辅助理解：

• 按行求和就是原定义的$S_2(3)=1²⁺²2+3^2=14$
• 按列求和就是交换顺序后的双重求和，结果也是14，完美验证等式成立。

第二步：从双重求和推导目标递推式 #

我们已经得到：
$$S_{k+1}(n) = \sum_{j=1}^n \sum_{i=j}^n i^k$$

注意到$\sum_{i=j}^n i^{k$其实就是$S_k(n)$减去前$j-1$项的和，也就是$\sum_{i=j}}n i^k = S_k(n) - S_k(j-1)$（这里规定$S_k(0)=0$，因为从1到0的和为0）。把这个代入上式：
$$S_{k+1}(n) = \sum_{j=1}^n \left( S_k(n) - S_k(j-1) \right)$$

现在拆分这个求和式：

1. 第一部分：$\sum_{j=1}^n S_k(n)$ 是$n$个$S_k(n)$相加，结果为$n \cdot S_k(n)$
2. 第二部分：$\sum_{j=1}^n S_k(j-1)$，当$j=1$时，$j-1=0$，$S_k(0)=0$；当$j$从2到$n$时，$j-1$从1到$n-1$，所以这个求和等价于$\sum_{i=1}^{n-1} S_k(i)$（令$i=j-1$做变量替换）

把两部分合并起来，就得到：
$$S_{k+1}(n) = n S_k(n) - \sum_{i=1}^{n-1} S_k(i)$$

再用刚才的例子验证：$n=3, k=1$时，右边为$3 \cdot S_1(3) - (S_1(1)+S_1(2)) = 3 \times 6 - (1+3) = 18-4=14$，和左边$S_2(3)=14$完全一致，推导正确！

内容的提问来源于stack exchange，提问作者L. Li