这个结论如何证明

lemondian

爪机专用

kuing.cjhb.site/forum.php?mod=viewthread&tid=8187

hbghlyj

\[
\begin{aligned}
f(x) & =s_0 x^n+s_1 x^{n-1}+\cdots+s_{n-1} x+s_n \\
& =\prod_{i=1}^n\left(x-x_i\right)\\
p_i&\left(x_1, \ldots, x_n\right)=x_1^i+\cdots x_n^i
\end{aligned}
\]

爪机专用 发表于 2025-2-8 14:29
kuing.cjhb.site/forum.php?mod=viewthread&tid=8187

定理：对任意正整数 $k$，我们有 $
\left\{\begin{aligned}
k s_k+\sum_{i=0}^{k-1} s_i p_{k-i} & =0 \text { 若 } k \leq n \\
\sum_{i=0}^n s_i p_{k-i} & =0 \text { 若 } k>n
\end{aligned}\right.$
对于所有 $i > n$ 定义 $s_i = 0$，就不用区分 $k\le n$ 和 $k>n$ 两种情况，合并为下面的：

定理：对任意正整数 $k$，我们有\[
k s_k+\sum_{i=0}^{k-1} s_i p_{k-i}=0
\]

hbghlyj

设 $k=n$,\[
f(x_j)=\sum_{i=0}^k s_{k-i} x_j^i=0
\]
对 $j$ 求和，\[
k s_k+\sum_{i=1}^k s_{k-i} p_i=0
\]
设 $k>n$,
\[
\sum_{i=0}^n s_i p_{k-i}=0
\]
添加变量 $\alpha_i$，令
\[
f_1(x)=f(x) \prod_{i=k-n+1}^k\left(x-\alpha_i\right)
\]
然后在 $f_1$ 而非 $f$ 上运行之前的论证，并将所有 $\alpha_i$ 设为 0。由于
\[
s_i=(-1)^i \sum_{j_1<\ldots<j_i} x_{j_1} \cdots x_{j_i}
\]
任何包含某个 $\alpha_i$ 的项都将为 0，因此我们想要的恒等式成立。

战巡 发表于 2024-6-11 12:20
韦达定理而已...

对于任意$x_i, i\in\{1,2,...,j\}$，都有

注意：以上简单方法只证明了当 $k \geq n$ 时的情形。对于 $k < n$ 的情形，则可以分析展开中各单项式来论证（例如参见 web.stanford.edu/~marykw/classes/CS250_W19/Netwons_Identities.pdf）。
现在，改而假设 $k<n$。我们希望证明
\[
k s_k+\sum_{i=1}^k s_{k-i} p_i=0
\]
如果我们合并同类项，只需证明下式任意
\[
x_1^{a_1} \cdots x_n^{a_n}, \text { 其中每个 } a_i \text{ 非负整数，}
\]
的系数为 0。由于 $a_i$ 非零的最多有 $k$ 个，因此我们可以从该单项式中删去至少 $n-k$ 个根 $x_i$ 而不改变它的值。这样我们便知道该单项式的系数必定为 0。因为从某种意义上，我们将 $n-k$ 个根 $x_i$ 设为 0，此时所处理的是一个次数为 $k$ 的多项式 $f$；我们已知在这种情况下恒等式成立，即合并后的项系数为 0。

hbghlyj

本节我们给出牛顿恒等式的一个组合证明。组合证明通常是 (a) 通过给出两种数量之间的双射来证明它们相等，或者 (b) 通过用两种不同的方法计算相同的数量来证明两者相等。在讨论牛顿恒等式之前，下面的例子有助于理解 (b) 的方法。如果你之前见过这个例子或想直接看恒等式，可以跳过它。

定理 3.1. 令 $k \leq n$ 为正整数或非负整数。则
\[
k!\binom{n}{k}=n(n-1)(n-2) \cdots(n-k+1)
\]
证明。考虑一个有 $n$ 个元素的集合 $S$。令 $N_k$ 表示 $S$ 中所有不重复元素的长度为 $k$ 的序列数量。

一方面，我们可以先选出 $S$ 中一个无序的 $k$ 元子集，再将其排成有序。可供选择的子集有 $\binom{n}{k}$ 个，对每个子集有 $k!$ 种排列方式：这说明左边与 $N_k$ 相等。

另一方面，我们可以在构造序列的过程中每次选定一个元素，先选序列的第一个元素，再选第二个，依此类推。可供选择的第一个元素有 $n$ 个，接下来有 $n-1$ 个，等等。这说明右边也与 $N_k$ 相等。

现在，依照 Zeilberger, Doron. “A Combinatorial Proof of Newton’s Identities.” Discrete
Mathematics, Vo. 49 (1985): 319. sciencedirect.com/science/article/pii/0012365X84901717?via%3Dihub，我们给出牛顿恒等式简洁表述的组合证明：

定理 3.2. 固定一个正整数 $k$。有
\[
k s_k+\sum_{i=0}^{k-1} s_i p_{k-i}=0
\]
证明。考虑集合 $\mathscr{A}(n, k)$，它由三元组 $(A, j, \ell)$ 组成，其中：
(i) $A$ 是 $[n]$ 的一个子集，且 $|A|$ 至多为 $k$。（$[n]$ 表示整数集 $\{1,\ldots,n\}$。）
(ii) $j$ 是 $[n]$ 的一个元素。
(iii) $\ell=k-|A|$
(iv) 如果 $\ell$ 为 0，则 $j$ 属于 $A$。

定义 $(A, j, \ell)$ 的权重为
\[
w(A, j, \ell)=(-1)^{|A|}\left(\prod_{a \in A} x_a\right) \cdot x_j^{\ell}
\]
例如，
\[
w(\{1,3,5\}, 2,3)=(-1)^3 x_1 x_3 x_5 \cdot x_2^3 .
\]
要证明定理，只需证明定理中的和就是对 $\mathscr{A}(n, k)$ 中所有元素的权重求和，并且该和为 0。

首先，我们证明定理中的和就是对所有 $\mathscr{A}(n, k)$ 中元素的权重求和。用引言中的恒等式，我们有
\[\tag{*}
\begin{aligned}
k s_k+\sum_{i=0}^{k-1} s_i p_{k-i}+ & = \\
& =k(-1)^k \sum_{j_1<\ldots<j_k} x_{j_1} \cdots x_{j_k}+ \\
& \sum_{i=0}^{k-1}(-1)^i\left(x_1^{k-i}+\cdots x_n^{k-i}\right) \sum_{j_1<\ldots<j_i} x_{j_1} \cdots x_{j_i}
\end{aligned}
\]
右边有两个求和式。我们先看第一个求和式：
\[
k(-1)^k \sum_{j_1<\ldots<j_k} x_{j_1} \cdots x_{j_k} \cdot 1 .
\]
令 $A=\{j_1, \ldots, j_k\}$。当我们遍历所有指标选择时，相应遍历所有 $A$ 的选择。由于 $\ell$ 为 0，$x_j^{\ell}=1$ 在乘积中并不体现（上式中显式写出只是为了清楚），根据 (iv) 可知 $j \in A$。这样就有 $k$ 种 $j$ 的选择：
\[
\sum_{|A|=k ; j \in A ; \ell=0} w(A, j, \ell)=k \cdot \sum_{|A|=k ; \ell=0} w\left(a, j^{\prime}, \ell\right)
\]
其中 $j^{\prime}$ 是 $A$ 中任意一个元素。由此可知在 (*) 中第一个求和式正好是所有 $|A|=k$ 的元素权重之和。要看其它所有元素如何组成 (*) 的其它求和式，可以将该部分展开。

剩下就是证明对 $\mathscr{A}(n, k)$ 中所有元素的权重求和为 0。定义一个映射 $T: \mathscr{A} \rightarrow \mathscr{A}$：
\[
T(A, j, \ell)=\left\{\begin{array}{l}
(A-\{j\}, j, \ell+1) \text { 若 } j \text { 在 } A\text{ 中} \\
(A \cup\{j\}, j, \ell-1) \text { 若 } j \text { 不在 } A\text{ 中}
\end{array}\right.
\]
（直观地说，$T$ 会“加”上或“去掉”集 $A$ 中的 $j$，同时相应地调整 $\ell=k-|A|$。）那么 $T$ 会将我们带到一个不同的三元组，且其权重符号相反：
\[
w(T(A, j, \ell))=-w(A, j, \ell)
\]
并且 $T^2$ 是恒等映射（即 $T$ 是一个对合元）。因此，所有权重可以两两配对抵消，总和为 0。

hbghlyj

此处的思路来自 Eidswick, J.A. “A Proof of Newton’s Power Sum Formulas.” The American Mathematical Monthly, Vol. 75, no. 4 (April, 1968): 396-397. digitalcommons.unl.edu/mathfacpub/50/。另一个在编码理论背景下使用母函数的相似证明，可参见 Berlekamp, Elwyn. Algebraic Coding Theory. New York: McGraw Hill Book Co. 1968 第 212 页。

为了给出此证明，我们需要介绍并简单讨论多项式 $f$ 的 $n$-reversal，它就是将 $f$ 的系数颠倒排列后的结果。

定义 4.1. 考虑一个多项式 $f$（其根为 $x_1, \ldots, x_n$）：
\[
\begin{aligned}
f(x) & =s_0 x^n+s_1 x^{n-1}+\cdots+s_{n-1} x+s_n \\
& =\prod_{i=1}^n\left(x-x_i\right)
\end{aligned}
\]
那么 $f$ 的 $n$-reversal 为
\[
\operatorname{rev}_n(f)=s_n x^n+s_{n-1} x^{n-1}+\cdots+s_1 x+s_0
\]
为证明牛顿恒等式，我们需要下面的引理。

引理 4.2. 若 $f$ 如上所示，则 $\operatorname{rev}_n(f)=x^n f(1 / x)$，并且 $\operatorname{rev}_n(f)$ 的根是 $1 / x_i$（其中 $x_i$ 是 $f$ 的根）。

证明。通过直接观察可看出 $\operatorname{rev}_n(f)=x^n f(1 / x)$。如果 $x_i$ 是 $f$ 的根，那么 $1 / x_i$ 是 $\operatorname{rev}_n(f)$ 的根。因为 $\operatorname{rev}_n(f)$ 的次数为 $n$，它的所有根都可以写成这种形式。

另附一则推论：有兴趣的读者可以使用上述引理来证明如下推论。

推论 4.3. 令 $f$ 和 $g$ 分别是次数 $n \geq m$ 的多项式，且 $g$ 为首项系数为 1（monic）的多项式。用欧几里得算法表示 $f=q g+r$。则有如下 reversal 恒等式：
\[
\operatorname{rev}_n(f)=\operatorname{rev}_{n-m}(q) \cdot \operatorname{rev}_m(g)+x^{n-m+1} \cdot \operatorname{rev}_{m-1}(r)
\]
证明参见 Polynomial reversal
math.stackexchange.com/questions/2129417/polynomial-reversal/2129443#2129443

现在我们可以证明牛顿恒等式。由于将会出现的原因，这里的较不简洁的形式更有用：

定理 4.4. 固定一个正整数 $k$。假设 0 不是 $f$ 的根（即 $s_n \neq 0$）。则有
\[
\begin{aligned}
k s_k+\sum_{i=0}^{k-1} s_i p_{k-i} & =0 \quad \text{若 } k \leq n \\
\sum_{i=0}^n s_i p_{k-i} & =0 \quad \text{若 } k>n
\end{aligned}
\]
证明。令 $f$ 如上所示，并设 $v=\operatorname{rev}(f)$。则由上面的引理：
\[
\begin{aligned}
v(x) & =s_n x^n+s_{n-1} x^{n-1}+\ldots+s_0 \\
& =s_n \prod_{i=1}^n\left(x-x_i^{-1}\right)
\end{aligned}
\]
观察上面第一个等号，当我们在 $x=0$ 处对 $v$ 做第 $k$ 阶导数时，会得到系数 $s_k$：
\[
v^{(k)}(0)=s_k
\]
进一步可以看到 $v$ 的对数导数在 0 处的值与 $p_{k+1}$ 有关。这个证明的思路是，将 $v$ 与它的对数导数之间的关系转化为关于 $s_k$ 和 $p_{k+1}$ 的关系。因为 0 不是 $f$ 的根，也就不是 $v$ 的根，我们可以取其对数导数：
\[
V(x)=\frac{v^{\prime}(x)}{v(x)}=\sum_{i=1}^n\left(x-x_i^{-1}\right)^{-1}
\]
要理解右边的等式，可以对 $v$ 的因子化使用广义乘法法则，并注意每个因子的导数都为 1。现在声明
\[
V^{(k)}(0)=-\cdot k!\cdot p_{k+1} \quad(*)
\]
其中 $V^{(k)}$ 是 $V$ 的第 $k$ 阶导数。这是因为
\[
\begin{aligned}
V^1(x) & =-1 \sum_{i=1}^n\left(x-x_i^{-1}\right)^{-2} \\
V^2(x) & =2 \sum_{i=1}^n\left(x-x_i^{-1}\right)^{-3}
\end{aligned}
\]
等等，在 $x=0$ 处代入能得到如 $V^2(0)=-1 \cdot 2!\cdot p_3$ 之类的结果。当 $k$ 为偶数时，负号来源于 $\left(1 /-x_i^{-1}\right)^{k+1}$ 整体的符号，当 $k$ 为奇数时，负号则来自幂法则的使用。由此可知 $(*)$ 成立。为完成证明，我们再得出另一个等式，并用 $(*)$ 推导出牛顿恒等式。

现在，考虑 $[V(x) v(x)]^{(k-1)}$，即对 $V(x) v(x)$ 的第 $k$ 阶导数：
\[
\begin{aligned}
v^{(k)}(x) & =[V(x) v(x)]^{(k-1)} \\
& =\sum_{i=0}^{k-1}\binom{k-1}{i} V^{(i)}(x) v^{(k-1-i)}(x),
\end{aligned}
\]
第一个等号是因为 $V$ 是 $v$ 的对数导数，第二个等号来自乘法法则及二项式定理。用公式 $(*)$ 替换 $V^{(r)}$ 并重新排列得到
\[
\frac{v^{(k)}(0)}{k!}=-\frac{1}{k} \sum_{i=0}^{k-1} \frac{v^{(k-1-i)}(0)}{(k-1-i)!} p_{i+1}
\]
回忆 $v^{(k)}(0)=s_k$，因此
\[
\begin{array}{rlr}
-k s_k=\sum_{i=0}^{k-1} s_{k-(i+1)} p_{i+1} & \text { 若 } k \leq n \\
0 =\sum_{i=k-n-1}^{k-1} s_{k-(i+1)} p_{i+1} & \text { 若 } k>n
\end{array}
\]
这就是牛顿恒等式，只需将指标做些微调即可。

hbghlyj

此证明来自 Mead, D.G. “Netwon’s Identities.” The American Mathematical Monthly,
Vol. 99, No. 8 (1992): 749-751 jstor.org/stable/2324242?seq=1。与 Reichstein, Zinovy.“An inductive proof of Newton’s identities.” 中的方法类似，也与我们之前在 $n=k$ 情况时所见到的方法相近，都是通过将若干方程加起来实现的。我们仅介绍那里的记号，以便感受这种方法。令 $f$ 如上，为次数 $n$，根为 $x_1, \ldots, x_n$。令 $(a_1, \ldots, a_n)$ 表示
\[
\sum_{i_1<\ldots<i_n} x_{i_1}^{a_1} \cdot x_{i_2}^{a_2} \cdots x_{i_n}^{a_n}
\]
其中 $a_i$ 非负，从左到右非增。若 $a_i=0$ 当 $i>k$，我们可以只写作 $(a_1, \ldots, a_k)$ 而非 $(a_1, \ldots, a_n)$。于是
\[
\begin{aligned}
p_i & =(i) \\
s_i^{\prime} & =(1, \ldots, 1), \text { 其中 1 重复出现 } i \text{ 次数。}
\end{aligned}
\]
有了这套记号，牛顿恒等式的表述（和证明）会更简洁。例如，在 $n \geq k=3$ 时，我们可以用下式：
\[
(2)(1)=(3)+(2,1)
\]
去减去：
\[
(1)(1,1)=(2,1)+3(1,1,1)
\]
从而得到牛顿恒等式：
\[
p_3-p_2 s_1^{\prime}+p_1 s_2^{\prime}-3 s_3^{\prime}=0 \Longrightarrow 3 s_3+\sum_{i=0}^{k-1} s_i p_{k-i}=0
\]
完整证明可参见 Mead, D.G. “Netwon’s Identities.” The American Mathematical Monthly,
Vol. 99, No. 8 (1992): 749-751 jstor.org/stable/2324242?seq=1

hbghlyj

有兴趣的读者可以参考 Reichstein, Zinovy.“An inductive proof of Newton’s identities.” 的归纳法证明，以及 Ján Mináč. “Newton’s Identities Once Again!” The American MathematicalMonthly, Vol. 110, No. 3 (2003): 232-234. jstor.org/stable/3647937 的分情形证明。这些方法有时会显得缺乏动机且难以理解，但多研究几个视角往往益处大于弊处。

hbghlyj

牛顿恒等式提供了通过矩阵幂的迹来计算矩阵的特征多项式的方法，也可以用矩阵的方法推导牛顿恒等式。感兴趣可参见 Kalman, Dan. “A Matrix Proof of Newton’s Identities.” Mathematics Magazine, Vol. 73, No. 4 (2000): 313-315. jstor.org/stable/2690982

lemondian

谢谢两位的解析