求证含阶乘与幂次的求和恒等式：寻求非归纳法证明

不用归纳法的话，我们可以通过拆分并化简求和项，结合基本的阶乘与求和变形来推导。先把原恒等式明确下来：

$$\sum_{k=0}^{n-1}\frac{n{k-1}}{k!}(n-k)(n-k+1)=\frac{n^{{n-1}}{(n-1)!}+\sum_{k=0}}{n-1}\frac{n^k}{k!}$$

步骤1：整理左边的表达式 #

首先把左边的 $n^{k-1}$ 改写为 $\frac{n^k}{n}$，这样左边可以写成：
$$L = \frac{1}{n}\sum_{k=0}^{n-1}\frac{nk}{k!}(n-k)(n-k+1)$$

我们的目标是证明 $L = \frac{n^{n-1}}{(n-1)!} + S$，其中 $S = \sum_{k=0}^{n-1}\frac{nk}{k!}$。等价于证明 $L - S = \frac{n^{n-1}}{(n-1)!}$。

步骤2：化简 $L - S$ 的表达式 #

将 $L - S$ 展开：
$$L - S = \frac{1}{n}\sum_{k=0}^{n-1}\frac{nk}{k!}\left[(n-k)(n-k+1) - n\right]$$

先计算括号内的多项式：
$$(n-k)(n-k+1) - n = (n-k)^2 + (n-k) - n = n^2 - 2nk + k^2 - k = n(n-2k) + k(k-1)$$

代入后拆分求和项：
$$L - S = \frac{1}{n}\left[ \sum_{k=0}^{n-1}\frac{nk}{k!}n(n-2k) + \sum_{k=0}^{n-1}\frac{nk}{k!}k(k-1) \right]$$
$$= \sum_{k=0}^{n-1}\frac{nk}{k!}(n-2k) + \frac{1}{n}\sum_{k=0}^{n-1}\frac{nk}{k!}k(k-1)$$

步骤3：分别计算两个求和项 #

第一个求和项：$\sum_{k=0}^{n-1}\frac{nk}{k!}(n-2k)$

拆分后利用求和的线性性：
$$\sum_{k=0}^{n-1}\frac{nk}{k!}(n-2k) = n\sum_{k=0}^{n-1}\frac{nk}{k!} - 2\sum_{k=0}^{n-1}\frac{nk}{k!}k$$

注意到 $\sum_{k=0}^{n-1}\frac{nk}{k!}k = n\sum_{k=1}^{n-1}\frac{n{k-1}}{(k-1)!} = n\left(S - \frac{n^{n-1}}{(n-1)!}\right)$（k=0时项为0，将求和索引转为m=k-1后，求和范围是m=0到n-2，对应S减去k=n-1的项）。

代入后：
$$= nS - 2n\left(S - \frac{n^{n-1}}{(n-1)!}\right) = -nS + \frac{2n^n}{(n-1)!}$$

第二个求和项：$\frac{1}{n}\sum_{k=0}^{n-1}\frac{nk}{k!}k(k-1)$

当k=0或k=1时，$k(k-1)=0$，所以求和从k=2开始：
$$\sum_{k=2}^{n-1}\frac{nk}{k!}k(k-1) = \sum_{k=2}^{n-1}\frac{nk}{(k-2)!} = n^2\sum_{m=0}{n-3}\frac{n^m}{m!}$$
（令m=k-2转换求和索引）

而 $\sum_{m=0}^{n-3}\frac{nm}{m!} = S - \frac{n^{n-1}}{(n-1)!} - \frac{n^{n-2}}{(n-2)!}$，代入后：
$$\frac{1}{n} \times n^2\left(S - \frac{n^{n-1}}{(n-1)!} - \frac{n^{n-2}}{(n-2)!}\right) = n\left(S - \frac{n^{n-1}}{(n-1)!} - \frac{n^{n-2}}{(n-2)!}\right)$$

步骤4：合并两项并化简 #

把两个求和项的结果相加：
$$L - S = \left(-nS + \frac{2n^n}{(n-1)!}\right) + n\left(S - \frac{n^{n-1}}{(n-1)!} - \frac{n^{n-2}}{(n-2)!}\right)$$

展开并抵消同类项：
$$= -nS + \frac{2n^n}{(n-1)!} + nS - \frac{n^n}{(n-1)!} - \frac{n^{n-1}}{(n-2)!}$$

注意到 $\frac{n^{n-1}}{(n-2)!} = \frac{n^{n-1}(n-1)}{(n-1)!} = \frac{n^n - n^{n-1}}{(n-1)!}$，代入后：
$$= \frac{n^n}{(n-1)!} - \frac{n^n - n^{n-1}}{(n-1)!} = \frac{n^{n-1}}{(n-1)!}$$

这就证明了 $L - S = \frac{n^{n-1}}{(n-1)!}$，也就是原恒等式成立。

内容的提问来源于stack exchange，提问作者Simon Parker