求证幂和序列的递推关系（原标题过长已简化）

嘿，我来帮你理清这个递推关系的证明思路——你尝试用二重和的方向是完全对的，只是在交换求和顺序或者拆解的时候差了一步，我一步步给你讲清楚：

首先明确我们的定义：

• ( S_k(n) = \sum_{i=1}^n i^k )，也就是前n个正整数的k次幂和；
• 我们要证的是 ( S_{k+1}(n) = nS_k(n) - \sum_{i=1}^{n-1} S_k(i) )。

方法一：从左边 ( S_{k+1}(n) ) 拆解推导 #

注意到 ( i^{k+1} = i \cdot i^k )，而整数i可以写成从1到i的1的和：( i = \sum_{j=1}^i 1 )。把这个代入 ( S_{k+1}(n) )：
$$S_{k+1}(n) = \sum_{i=1}^n i^{k+1} = \sum_{i=1}^n \left( i \cdot i^k \right) = \sum_{i=1}^n \left( \left( \sum_{j=1}^i 1 \right) \cdot i^k \right)$$

接下来交换求和顺序：原来的求和是先对j从1到i，再对i从1到n。我们可以把它转换成先对j从1到n，再对i从j到n（因为当j≤i时，i的取值范围就是从j到n），这样就得到你提到的二重和：
$$S_{k+1}(n) = \sum_{j=1}^n \sum_{i=j}^n i^k$$

现在处理这个二重和：内层的 ( \sum_{i=j}^n i^k ) 其实就是 ( S_k(n) - S_k(j-1) )（因为 ( S_k(n) ) 是前n项和，减去前j-1项的和就得到从j到n的和），这里我们规定 ( S_k(0) = 0 )（空和的默认值）。把这个代入进去：
$$\sum_{j=1}^n \sum_{i=j}^n i^k = \sum_{j=1}^n \left( S_k(n) - S_k(j-1) \right)$$

把这个求和拆成两部分：
$$= \sum_{j=1}^n S_k(n) - \sum_{j=1}^n S_k(j-1)$$

第一部分里，( S_k(n) ) 是常数，一共加n次，所以等于 ( nS_k(n) )。第二部分我们做变量替换：令 ( i = j-1 )，当j从1到n时，i就从0到n-1，所以：
$$= nS_k(n) - \sum_{i=0}^{n-1} S_k(i)$$

因为 ( S_k(0) = 0 )，去掉i=0的项不影响结果，所以：
$$= nS_k(n) - \sum_{i=1}^{n-1} S_k(i)$$

这样就正好等于我们要证明的右边，推导完成！

方法二：从右边反向验证 #

如果你想从右边往左边推，也很直观：
首先，( nS_k(n) = n \sum_{i=1}^n i^k = \sum_{i=1}^n n i^k )。然后看要减去的部分 ( \sum_{i=1}^{n-1} S_k(i) = \sum_{i=1}^{n-1} \sum_{m=1}^i m^k )，交换这个二重和的顺序（先对i从m到n-1，再对m从1到n-1）：
$$\sum_{i=1}^{n-1} S_k(i) = \sum_{m=1}^{n-1} \sum_{i=m}^{n-1} m^k = \sum_{m=1}^{n-1} (n - m) m^k$$

现在把右边整体写出来：
$$nS_k(n) - \sum_{i=1}^{n-1} S_k(i) = \sum_{i=1}^n n i^k - \sum_{m=1}^{n-1} (n - m) m^k$$

把变量m换成i，再拆分第一项中i=n的情况：
$$= n \cdot n^k + \sum_{i=1}^{n-1} n i^k - \sum_{i=1}^{n-1} (n - i) i^k$$

合并后面的两个求和，化简括号里的项：
$$= n^{k+1} + \sum_{i=1}^{n-1} \left[ n i^k - (n - i)i^k \right]$$
$$= n^{k+1} + \sum_{i=1}^{n-1} i^{k+1}$$

最后把两部分合并，就是前n个正整数的k+1次幂和：
$$= \sum_{i=1}^n i^{k+1} = S_{k+1}(n)$$

这样也验证了等式成立。

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