以下の対称式 \(x^n + y^n\) の基本対称式による漸化式を導出する。 \[ (x^n + y^n) = (x^{n-1} + y^{n-1}) - xy(x^{n-2} + y^{n-2}) \]
まず、\((x + y)(x^{n-1} + y^{n-1})\) を求めてみる。 \[ \begin{aligned} (x + y)(x^{n-1} + y^{n-1}) &= xx^{n-1} + xy^{n-1} + yx^{n-1} + yy^{n-1} = x^n + y^n + xy^{n-1} + x^{n-1}y \end{aligned} \] すると、以下のように基本対称式による漸化式が求まる。 \[ \begin{aligned} x^n + y^n &= (x + y)(x^{n-1} + y^{n-1}) - (x^{n-1}y + xy^{n-1})\\ &= (x + y)(x^{n-1} + y^{n-1}) - xy(x^{n-2} + y^{n-2})\\ \end{aligned} \]
ここで、\(n=1\) のとき、この基本対称式による漸化式は以下のように成り立っている。 \[ \begin{aligned} x + y &= (x + y)(x^{0} + y^{0}) - (x^{0}y + xy^{0}) = 2(x + y) - (x + y)\\ \end{aligned} \]
以下の二項定理 \((x + y)^n\) の式から導出する。 \[ (x + y)^n = \sum_{k=0}^{n}\dbinom{n}{k}x^{n-k}y^k = (x^n + y^n) + \sum_{k=1}^{n-1}\dbinom{n}{k}x^{n-k}y^k \] これより、 \[ (x^n + y^n) = (x + y)^n - \sum_{k=1}^{n-1}\dbinom{n}{k}x^{n-k}y^k \] ここで、\(n\to n-1\)とすると、 \[ (x^{n-1} + y^{n-1}) = (x + y)^{n-1} - \sum_{k=1}^{n-1-1}\dbinom{n-1}{k}x^{n-1-k}y^k \] さらに、両辺に \((x + y)\) を掛けると、 \[ (x + y)(x^{n-1} + y^{n-1}) = (x + y)^{n-1+1} - (x + y)\sum_{k=1}^{n-1-1}\dbinom{n-1}{k}x^{n-1-k}y^k \] ここで、\((x^n + y^n) - (x + y)(x^{n-1} + y^{n-1})\) は、 \[ \begin{aligned} (x^n + y^n) - (x + y)(x^{n-1} + y^{n-1}) &= (x + y)^n - (x + y)^{n-1+1} - \sum_{k=1}^{n-1}\dbinom{n}{k}x^{n-k}y^k + (x + y)\sum_{k=1}^{n-1-1}\dbinom{n-1}{k}x^{n-1-k}y^k\\ &= - \sum_{k=1}^{n-1}\dbinom{n}{k}x^{n-k}y^k + x\sum_{k=1}^{n-1-1}\dbinom{n-1}{k}x^{n-1-k}y^k + y\sum_{k=1}^{n-1-1}\dbinom{n-1}{k}x^{n-1-k}y^k\\ &= - \sum_{k=1}^{n-1}\dbinom{n}{k}x^{n-k}y^k + \sum_{k=1}^{n-1-1}\dbinom{n-1}{k}x^{n-k}y^k + \sum_{k=1}^{n-1-1}\dbinom{n-1}{k}x^{n-1-k}y^{k+1}\\ \end{aligned} \] ここで、\(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\) より、 \[ \begin{aligned} &= - \sum_{k=1}^{n-1}\dbinom{n-1}{k-1}x^{n-k}y^k - \sum_{k=1}^{n-1}\dbinom{n-1}{k}x^{n-k}y^k + \sum_{k=1}^{n-1-1}\dbinom{n-1}{k}x^{n-k}y^k + \sum_{k=1}^{n-1-1}\dbinom{n-1}{k+1-1}x^{n-(1+k)}y^{k+1}\\ \end{aligned} \] ここで、第４項にて \(k+1\to k\) とすると、 \[ \begin{aligned} &= - \sum_{k=1}^{n-1}\dbinom{n-1}{k-1}x^{n-k}y^k - \sum_{k=1}^{n-1}\dbinom{n-1}{k}x^{n-k}y^k + \sum_{k=1}^{n-1-1}\dbinom{n-1}{k}x^{n-k}y^k + \sum_{k=2}^{n-1}\dbinom{n-1}{k-1}x^{n-k}y^k\\ &=\sum_{k=2}^{n-1}\dbinom{n-1}{k-1}x^{n-k}y^k - \sum_{k=1}^{n-1}\dbinom{n-1}{k-1}x^{n-k}y^k + \sum_{k=1}^{n-1-1}\dbinom{n-1}{k}x^{n-k}y^k - \sum_{k=1}^{n-1}\dbinom{n-1}{k}x^{n-k}y^k\\ \end{aligned} \] ここで、第２項の \(k=1\)、第４項の \(k=n-1\) しか残らないことがわかる。 \[ \begin{aligned} &=-\left(\dbinom{n-1}{1-1}x^{n-1}y^{1} + \dbinom{n-1}{n-1}x^{n-(n-1)}y^{n-1}\right) =-\left(\dbinom{n-1}{0}x^{n-1}y + \dbinom{n-1}{n-1}xy^{n-1}\right)\\ \end{aligned} \] ここで、\(\binom{n-1}{0} = \binom{n-1}{n-1} = 1\) より、 \[ \begin{aligned} (x^n + y^n) - (x + y)(x^{n-1} + y^{n-1}) &= -(x^{n-1}y + xy^{n-1})\\ \end{aligned} \] ゆえに、 \[ (x^n + y^n) - (x + y)(x^{n-1} + y^{n-1}) = -(x^{n-1}y + xy^{n-1}) \] であるので、以下のように基本対称式による漸化式が求まる。 \[ \begin{aligned} (x^n + y^n) &= (x + y)(x^{n-1} + y^{n-1}) - \left(x^{n-1}y + xy^{n-1}\right)\\ &= (x + y)(x^{n-1} + y^{n-1}) - xy(x^{n-2} + y^{n-2})\\ \end{aligned} \]