【対称式】x^n+y^n+z^nの漸化式の美しい証明
$x^n+y^n, x^n+y^n+z^n$などは対称式なので，基本対称式のみの多項式で表すことができます．
この値を求める方法として，次の漸化式が知られています．
$p=x+y, q=xy$とすると
$S_n=x^n+y^n$は次の漸化式に従う
$S_n=pS_{n-1}-qS_{n-2}$
$p=x+y+z, q=xy+yz+zx, r=xyz$とすると
$S_n=x^n+y^n+z^n$は次の漸化式に従う
$S_n=pS_{n-1}-qS_{n-2}+rS_{n-3}$
いずれも数学的帰納法を使えば示すことができますが，$基本対称式\times S_n$の交代和で表せるというのは何か深い意味がありそうです．
結論から言うと，それを解に持つ方程式の係数として基本対称式が現れることを使うと，簡単に納得できます．
まずは命題2を証明してみましょう
$x,y,z$は3次方程式$t^3-pt^2+qt-r=0$の解であるから，次が成立する
$$
\begin{eqnarray}
\left\{
\begin{array}{l}
x^3-px^2+qx-r=0 \\
y^3-py^2+qy-r=0 \\
z^3-pz^2+qz-r=0
\end{array}
\right.
\end{eqnarray}
$$
それぞれ，$x^{n-3}, y^{n-3}, z^{n-3}$を両辺に掛けて
$$
\begin{eqnarray}
\left\{
\begin{array}{l}
x^n-px^{n-1}+qx^{n-2}-rx^{n-3}=0 \\
y^n-py^{n-1}+qy^{n-2}-ry^{n-3}=0 \\
z^n-pz^{n-1}+qz^{n-2}-rz^{n-3}=0
\end{array}
\right.
\end{eqnarray}
$$
これらを辺々足して整理すると，
$S_n=pS_{n-1}-qS_{n-2}+rS_{n-3}$
を得る
これを一般化すれば，以下の漸化式が成り立つ事がわかります．
$m$個の数$x_1, x_2,x_3,\ldots,x_m$について，$i$次の基本対称式を$e_i$で表すとする．
$S_n=\sum_{k=1}^{m}x_k^n$は，次の漸化式に従う．
$$
S_n=\sum_{i=1}^{m}(-1)^{m-1}e_iS_{n-i}
$$
$f(x)=(x-x_1)(x-x_2)\ldots(x-x_m)$とする。
$f(x)$を展開したとき，$x^{n-k}\ \ (k=1,2,\ldots,m)$の係数は，$-x_1,\ -x_2,\ldots,-x_m$から$k$個選んでかけ合わせたものをすべてを足し合わせたものであるから，$(-1)^ke_k$. よって，
$$f(x)=x^m+\sum_{k=1}^{m}{(-1)^ke_kx^{m-k}}$$
$k=1,2,\ldots,m$に対し，$f(x_k)=0$なので，
$$x_k^m+\sum_{k=1}^{m}{(-1)^ke_kx_k^{m-k}}=0$$
両辺に$x_k^{n-m}$を掛けて
$$x_k^n+\sum_{k=1}^{m}{(-1)^ke_kx_k^{n-k}}=0$$
$k=1,2,\ldots,m$について辺々足して
$$S_n+\sum_{k=1}^{m}{(-1)^ke_kS_{n-k}}=0 \ \ \ \therefore \ S_n=\sum_{k=1}^{m}{(-1)^{k-1}e_kS_{n-k}}$$
