请教牛顿公式的应用

abababa

题目和解答如图，我看不懂根据牛顿公式那部分，这是怎么得到$s_m-a_1s_{m-1}-a_2s_{m-2}-\cdots-a_{m-1}s_1=ma_m$的？

设 $A$ 是 $n$ 阶矩阵, 我们按如下方式构造几个序列:
$$
\begin{array}{lll}
A_{1}=A, & p_{2}=\operatorname{tr} A_{1}, & B_{1}=A_{1}-p_{1} E, \\
A_{2}=B_{1} A, & p_{2}=\frac{1}{2} \operatorname{tr} A_{2}, & B_{2}=A_{2}-p_{2} E, \\
A_{3}=B_{2} A, & p_{3}=\frac{1}{3} \operatorname{tr} A_{3}, & B_{3}=A_{3}-p_{3} E, \\
A_{n}=B_{n-1} A, & p_{n}=\frac{1}{n} \operatorname{tr} A_{n},& B_{n}=A_{n}-p_{n} E .
\end{array}
$$
证明上述 $p_{1}, p_{2}, \cdots, p_{n}$ 是 $A$ 的特征多项式
$$
\Delta_{A}(\lambda)=|\lambda E-A|=\lambda^{n}-p_{1} \lambda^{n-1}-p_{2} \lambda^{n-2}-\cdots-p_{n}
$$
的系数, 并且 $B_{n}=0$. 当 $A$ 是可逆阵时, $A^{-1}=\frac{1}{p_{n}} B_{n-1}$.
证明: 设 $A$ 的特征多项式
$$
\Delta_{A}(\lambda)=|\lambda E-A|=\lambda^{n}-a_{1} \lambda^{n-1}-a_{2} \lambda^{n-2}-\cdots-a_{n},
$$
显然 $a_{1}=\operatorname{tr} A=\operatorname{tr} A_{1}=p_{1}$, 归纳地假设 $p_{1}=a_{1}, p_{2}=a_{2}, \cdots, p_{m-1}=a_{m-1}$, 我们来证 $p_{m}=a_{m}$. 从 $A_{1}, A_{2}, \cdots, A_{n} ; B_{1}, B_{2}, \cdots, B_{n}$; 以及 $p_{1}, p_{2}, \cdots, p_{n}$ 的构造方式容易得到
$$
\begin{aligned}
A_{m} &=A^{m}-p_{1} A^{m-1}-p_{2} A^{m 2}-\cdots-p_{m-1} A \\
&=A^{m}-a_{1} A^{m-1}-a_{2} A^{m-2}-\cdots-a_{m-1} A,
\end{aligned}
$$
因此得到
$$
\begin{aligned}
p_{m} &=\frac{1}{m} \operatorname{tr} A_{m}=\frac{1}{m} \operatorname{tr}\left(A^{m}-a_{1} A^{m-1}-a_{2} A^{m-2}-\cdots-a_{m-1} A\right) \\
&=\frac{1}{m}\left(\operatorname{tr} A^{m}-a_{1} \operatorname{tr} A^{m-1}-a_{2} \operatorname{tr} A^{m-2}-\cdots-a_{m-1} \operatorname{tr} A\right) \\
&=\frac{1}{m}\left(s_{m}-a_{1} s_{m-1}-a_{2} s_{m-2}-\cdots-a_{m-1} s_{1}\right),
\end{aligned}
$$
式中 $s_{i}=\lambda_{1}^{i}+\lambda_{2}^{i}+\cdots+\lambda_{n}^{i}, \lambda_{1}, \lambda_{2}, \cdots, \lambda_{n}$ 是 $A$ 的 $n$ 个特征值.根据牛顿公式立即得到
$$
p_{m}=\frac{1}{m} \cdot m a_{m}=a_{m},
$$
这就证明了对一切 $1 \leqslant i \leqslant n, p_{i}=a_{i}$.
据凯莱-哈密顿定理知 $B_{n}=A^{n}-p_{1} A^{n-1}-p_{2} A^{n-2}-\cdots-p_{n} E=0$. 当 $A$ 可逆时, 从$B_n=B_{n-1}A-p_nE=0$和$p_n=\det A$知$A^{-1}=\frac1{p_n}B_{n-1}$.

kuing

内容我是看不懂嘀，纯粹普及一下牛顿公式及推导。

记 `S_i=x_1^i+x_2^i+\cdots+x_n^i`，用 `\sigma_i` 表示各 `x_i` 的初等对称多项式（即 `\sigma_1=\sum\limits_{1\leqslant i\leqslant n}x_i`, `\sigma_2=\sum\limits_{1\leqslant i<j\leqslant n}x_ix_j` 等）。

牛顿等幂和公式是说：

（1）当 `k\geqslant n` 时，有
\[S_k-\sigma_1S_{k-1}+\sigma_2S_{k-2}-\cdots+(-1)^n\sigma_nS_{k-n}=0;\]（2）当 `1\leqslant k\leqslant n` 时，有
\[S_k-\sigma_1S_{k-1}+\sigma_2S_{k-2}-\cdots+(-1)^{k-1}\sigma_{k-1}S_1+(-1)^k\sigma_kk=0.\]
证明：
（1）因为
\[x^{k-n}(x-x_1)(x-x_2)\cdots(x-x_n)=x^k-\sigma_1x^{k-1}+\sigma_2x^{k-2}-\cdots+(-1)^n\sigma_kx^{k-n},\]分别令 `x=x_1`, `x_2`, \ldots, `x_n` 然后求和，左边全是零，右边就是 `S_k-\sigma_1S_{k-1}+\sigma_2S_{k-2}-\cdots+(-1)^n\sigma_nS_{k-n}`，所以等式成立；

（2）令
\[f(x)=(x-x_1)(x-x_2)\cdots(x-x_n)=x^n-\sigma_1x^{n-1}+\sigma_2x^{n-2}-\cdots+(-1)^n\sigma_n,\]求导有
\[f'(x)=f(x)\sum_{i=1}^n\frac1{x-x_i}=nx^{n-1}-\sigma_1(n-1)x^{n-2}+\sigma_2(n-2)x^{n-3}-\cdots+(-1)^{n-1}\sigma_{n-1},\]
两边乘 `x^{k+1}`，得
\[f(x)\sum_{i=1}^n\frac{x^{k+1}}{x-x_i}=nx^{n+k}-\sigma_1(n-1)x^{n+k-1}+\sigma_2(n-2)x^{n+k-2}-\cdots+(-1)^{n-1}\sigma_{n-1}x^{k+1},\quad(*)\]由于
\[\frac{x^{k+1}}{x-x_i}=\frac{x^{k+1}-x_i^{k+1}}{x-x_i}+\frac{x_i^{k+1}}{x-x_i}=x^k+x_ix^{k-1}+x_i^2x^{k-2}+\cdots+x_i^{k-1}x+x_i^k+\frac{x_i^{k+1}}{x-x_i},\]故
\[\sum_{i=1}^n\frac{x^{k+1}}{x-x_i}=nx^k+S_1x^{k-1}+S_2x^{k-2}+\cdots+S_{k-1}x+S_k+\sum_{i=1}^n\frac{x_i^{k+1}}{x-x_i},\]所以式 (*) 化为
\[\begin{aligned} &f(x)(nx^k+S_1x^{k-1}+S_2x^{k-2}+\cdots+S_{k-1}x+S_k)+f(x)\sum_{i=1}^n\frac{x_i^{k+1}}{x-x_i}\\ ={}&nx^{n+k}-\sigma_1(n-1)x^{n+k-1}+\sigma_2(n-2)x^{n+k-2}-\cdots+(-1)^{n-1}\sigma_{n-1}x^{k+1}, \end{aligned} \quad(**)\]比较式 (**) 等号两边的 `x^n` 的系数，等号右边是 `(-1)^k\sigma_k(n-k)`，至于等号左边，注意后面 `f(x)\sum\limits_{i=1}^n\frac{x_i^{k+1}}{x-x_i}` 的次数小于 `n`，不必考虑，只需考虑前面的展开，即
\[\bigl( x^n-\sigma_1x^{n-1}+\sigma_2x^{n-2}-\cdots+(-1)^n\sigma_n \bigr)(nx^k+S_1x^{k-1}+S_2x^{k-2}+\cdots+S_{k-1}x+S_k)\]的展开，易知其 `x^n` 的系数为 `S_k-\sigma_1S_{k-1}+\sigma_2S_{k-2}-\cdots+(-1)^{k-1}\sigma_{k-1}S_1+(-1)^k\sigma_kn`，所以
\[S_k-\sigma_1S_{k-1}+\sigma_2S_{k-2}-\cdots+(-1)^{k-1}\sigma_{k-1}S_1+(-1)^k\sigma_kn=(-1)^k\sigma_k(n-k),\]即
\[S_k-\sigma_1S_{k-1}+\sigma_2S_{k-2}-\cdots+(-1)^{k-1}\sigma_{k-1}S_1+(-1)^k\sigma_kk=0.\]

注：像（2）这么巧妙的证法我是想不出来嘀……

abababa

回复 2# kuing

谢谢，那这里的$S_k$，就相当于主楼里的$s_i$吧，因为$s_i=\lambda_1^i+\cdots+\lambda_n^i$，就相当于二楼的$S_i=x_1^i+\cdots+x_n^i$。

然后$a_1=p_1=\text{tr}(A_1)=\lambda_1+\cdots+\lambda_n$，就相当于一次齐次对称多项式，
\[a_2=p_2=\frac{1}{2}\text{tr}(A_2)=\frac{1}{2}\text{tr}(B_1A_1)=\frac{1}{2}\text{tr}((A_1-p_1E)A_1)=\frac{1}{2}\text{tr}(A_1^2)-\frac{1}{2}p_1\text{tr}(A_1)\]

因为$A^2$的特征值就是$A$的特征值的平方，迹就是特征值之和，所以$\text{tr}(A_1^2)=\lambda_1^2+\cdots+\lambda_n^2$，所以
\[a_2=\frac{1}{2}(\lambda_1^2+\cdots+\lambda_n^2)-\frac{1}{2}(\lambda_1+\cdots+\lambda_n)(\lambda_1+\cdots+\lambda_n)=-\sum_{1\le i<j\le n}\lambda_i\lambda_j\]

就是二次齐次对称多项式。
\begin{align*}
a_3&=p_3=\frac{1}{3}\text{tr}(A_3)=\frac{1}{3}\text{tr}(B_2A_1)=\frac{1}{3}\text{tr}(A_2A_1-p_2A_1)=\frac{1}{3}\text{tr}(B_1A_1^2-p_2A_1)\\
&=\frac{1}{3}\text{tr}((A_1-p_1E)A_1^2-p_2A_1)=\frac{1}{3}\text{tr}(A_1^3-p_1A_1^2-p_2A_1)\\
&=\frac{1}{3}[(\lambda_1^3+\cdots+\lambda_n^3)-(\lambda_1+\cdots+\lambda_n)(\lambda_1^2+\cdots+\lambda_n^2)+(\lambda_1+\cdots+\lambda_n)\sum_{1\le i<j\le n}\lambda_i\lambda_j]\\
&=\sum_{1\le i<j<k\le n}\lambda_i\lambda_j\lambda_k
\end{align*}

递推下去，可知$a_k$就是$k$次齐次多项式带上一个正负号。
就相当于二楼里的$\sigma_k$。那这样的话，结果应该是零啊，
\[S_m-\sigma_1S_{m-1}+\sigma_2S_{m-2}-\cdots+(-1)^{m-1}\sigma_{m-1}S_1\]

因为$m\ge1$，所以上式为零。

色k

回复 3# abababa

最后一项是不是搞错了？

abababa

回复 4# 色k

是的，指数应该是$(-1)^{m-1}$，正确的应该是$S_m-\sigma_1S_{m-1}+\sigma_2S_{m-2}-\cdots+(-1)^{(m-1)}\sigma_{m-1}S_1$，我改一下。

色k

回复 5# abababa

不只是次数问题，整个最后一项，你再看看。
另外那个m和n谁大？

abababa

回复 6# 色k

最后一项应该没什么错误了吧，我检查了应该是对的，不过这里确实应该是$m\le n$，所以应该用第二个公式，这样的话我就理解了，第二个公式多了一项$(-1)^m\sigma_m\cdot m$，而这一项恰好就等于$ma_m$。

isee

回复 2# kuing


    难怪像韦达定理。这证明顺畅，但其实非常抽象，学习了

    牛顿等幂和公式，还有阿贝尔变换等等，都是平凡处一声惊雷

kuing

回复 8# isee

这证明只有前半顺畅，后半很难想出来啊……

isee

回复 9# kuing


所以牛顿“牛”~

abababa

找到以前的一个应用，具体证明不记得了，但确实是等幂和在一元二次方程中的使用：

abababa

回复 12# hbghlyj

不是书，是网上找的一个pdf文档，因为我做别的题时需要用这个牛顿公式，然后在网上搜了一下，找到一些文档，就把文档里的这部分看了，当时那部分看不懂，现在文档删了。而且这个文档我记得也不是关于牛顿公式的，而是关于凯莱-哈密顿定理的。

hbghlyj

回复 13# abababa
哦...那好吧

hbghlyj

我在wikipedia找到了1#这条结论:

Using Newton identities, the elementary symmetric polynomials can in turn be expressed in terms of power sum symmetric polynomials of the eigenvalues:
⋯⋯⋯

lemondian

\begin{aligned}
& \text{若 } \sum_{k=0}^n a_k x^{n-k}=\prod_{k=1}^n\left(x+b_k\right) \\
& \text{设 } S_k=\sum_{m=1}^n b_m^k \\
& \text{则 } S_1=a_1, S_j=\sum_{k=1}^{j-1}(-1)^{k+1} a_k S_{j-k}+(-1)^{j+1} j a_j
\end{aligned}

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
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=ihub，我们给出牛顿恒等式简洁表述的组合证明：

定理 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/poly … rsal/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