数学ゲーム(30) - 非専門的シンギュラリティー研究所

フェルマーの小定理パズル(7)

「数学ゲーム(24) - 非専門的シンギュラリティー研究所」、「数学ゲーム(25) - 非専門的シンギュラリティー研究所」で考察した二項定理を証明するプログラムを作ることを考えます。

まず二項定理の証明を見ていきます。

二項定理の証明

(1) 可換環 $R$ に対して多項式環 $R[X]$ が存在します。多項式 $f$ の $X^k$ の係数を $f_k$ とします。多項式 $f, g$ に対して $\displaystyle (fg)_k = \sum_{i=0}^{k} f_i g_{k-i}$ が成り立ちます。
(2) 多項式 $f$ の $n$ 乗を $f^n$ 、 $f^n$ の $X^k$ の係数を $f^n_k$ とします。
(3) $b = X + 1$ とおきます。
(4) $b^n_0 = b^n_n = 1$ が成り立ちます。( $n$ は自然数、 $n \ge 1$ )
(5) $b^{n+1}_k = b^n_k + b^n_{k-1}$ が成り立ちます。( $n, k$ は自然数、 $1 \le k \le n-1$ )
(6) $b^n_k$ は整数となります。( $n, k$ は自然数、 $0 \le k \le n$ )
(7) $\displaystyle c(n, k) = \frac{n!}{k! \ (n-k)!}$ ( $n, k$ は自然数、 $0 \le k \le n$ ) とおきます。
(8) $c(n, 0) = c(n, n) = 1$ が成り立ちます。( $n$ は自然数、 $n \ge 1$ )
(9) $c(n+1, k) = c(n, k) + c(n, k-1)$ が成り立ちます。( $n, k$ は自然数、 $1 \le k \le n-1$ )
(10) $f^n_k = c(n, k)$ が成り立ちます。( $n, k$ は自然数、 $0 \le k \le n$ )
(11) $c(n, k)$ は整数となります。( $n, k$ は自然数、 $0 \le k \le n$ )

(1) 可換環 $R$ に対して多項式環 $R[X]$ が存在します。多項式 $f$ の $X^k$ の係数を $f_k$ とします。多項式 $f, g$ に対して $\displaystyle (fg)_k = \sum_{i=0}^{k} f_i g_{k-i}$ が成り立ちます。

$R[X]$ の元を自然数をインデックスとする有限個以外は $0$ の $R$ の元の集合 $f = \{f_k\}_{k \in \mathbb{N}}$ と定義します。( $k < 0$ のときは $f_k = 0$ とします)

すべての $k$ に対して $f_k = 0$ である $f$ を $0$ とします。
$f_0 = 1$ であり、それ以外のすべての $k$ に対して $f_k = 0$ である $f$ を $1$ とします。
$\{f_k\}_{k \in \mathbb{N}} + \{g_k\}_{k \in \mathbb{N}} = \{f_k + g_k\}_{k \in \mathbb{N}}$ とします。すると、 $R$ が可換環であることから加法の結合法則、交換法則が成り立ち、 $0$ は加法の単位元となります。
$\{-f_k\}_{k \in \mathbb{N}}$ は $f = \{f_k\}_{k \in \mathbb{N}}$ の加法の逆元 $-f$ となります。 $\{f_k\}_{k \in \mathbb{N}} - \{g_k\}_{k \in \mathbb{N}} = \{f_k\}_{k \in \mathbb{N}} + - \{g_k\}_{k \in \mathbb{N}}$ とします。 $\{f_k\}_{k \in \mathbb{N}} - \{g_k\}_{k \in \mathbb{N}} = \{f_k - g_k\}_{k \in \mathbb{N}}$ となります。
$\displaystyle \{f_k\}_{k \in \mathbb{N}} \cdot \{g_k\}_{k \in \mathbb{N}} = \left\{\sum_{i=0}^{k} f_i g_{k-i}\right\}_{k \in \mathbb{N}}$ とします。すると、 $R$ が可換環であることから乗法の交換法則が成り立ち、 $1$ は乗法の単位元となります。
$R$ が可換環であることから分配法則が成り立ちます。

$\displaystyle ( (fg)h )_k = \sum_{i=0}^{k} (fg)_i h_{k-i} = \sum_{i=0}^{k} \left(\sum_{j=0}^{i}f_jg_{i-j}\right) h_{k-i} = \sum_{i=0}^{k} \sum_{j=0}^{i}f_jg_{i-j} h_{k-i}$
$\displaystyle ( f(gh) )_k = \sum_{j=0}^{k} f_j (gh)_{k-j} = \sum_{j=0}^{k} f_j \left(\sum_{s=0}^{k-j}g_sh_{k-j-s}\right) = \sum_{j=0}^{k} \sum_{s=0}^{k-j}f_jg_sh_{k-j-s} = \sum_{j=0}^{k} \sum_{s+j=j}^{k}f_jg_sh_{k-j-s} = \sum_{j=0}^{k} \sum_{i=j}^{k}f_jg_{i-j}h_{k-i}$
であることから $( (fg)h )_k = ( f(gh) )_k$ となって

乗法の結合法則が成り立ちます。

よって $R[X]$ は可換環となります。

$R[X]$ は $R$ と独立な $X$ を含む可換環の最小のもので、 $f, g \in R[X]$ に対して $\displaystyle (fg)_k = \sum_{i=0}^{k} f_i g_{k-i}$ が成り立ちます。

(4) $b^n_0 = b^n_n = 1$ が成り立ちます。( $n$ は自然数、 $n \ge 1$ )

$n$ に関する帰納法で証明します。

$n = 1$ のときは(3)から成り立ちます。

$n = \nu$ のときに成り立つと仮定します。
(仮定) $b^\nu_0 = b^\nu_\nu = 1$
仮定と(1)から
$\displaystyle b^{\nu+1}_0 = (b^\nu b)_0 = \sum_{i=0}^{0} b^\nu_i b_{0-i} = b^\nu_0 b_{0-0} = b^\nu_0 b_{0} = 1$
$\displaystyle b^{\nu+1}_{\nu+1} = (b^\nu b)_{\nu+1} = \sum_{i=0}^{\nu+1} b^\nu_i b_{\nu+1-i} = b^\nu_\nu b_{\nu+1-\nu} = b^\nu_\nu b_{1} = 1$
よって $n = \nu+1$ のときにも成り立ちます。

(5) $b^{n+1}_k = b^n_k + b^n_{k-1}$ が成り立ちます。( $n, k$ は自然数、 $1 \le k \le n-1$ )

(1)と(4)から
$\displaystyle b^{n+1}_{k} = (b^n b)_{k} = \sum_{i=0}^{n+1} b^n_i b_{n+1-i} = \sum_{i=k-1}^{k} b^n_i b_{n+1-i} = b^n_{k-1} b_{1} + b^n_{k} b_{0} = b^n_{k-1} + b^n_{k}$
となって成り立ちます。

(6) $b^n_k$ は整数となります。( $n, k$ は自然数、 $0 \le k \le n$ )

(4)と(5)から成り立ちます。

(8) $c(n, 0) = c(n, n) = 1$ が成り立ちます。( $n$ は自然数、 $n \ge 1$ )

(7)から
$\displaystyle c(n, 0) = \frac{n!}{0! \ (n-0)!} = \frac{n!}{0! \ n!} = 1$
$\displaystyle c(n, n) = \frac{n!}{n! \ (n-n)!} = \frac{n!}{n! \ 0!} = 1$
となって成り立ちます。

(9) $c(n+1, k) = c(n, k) + c(n, k-1)$ が成り立ちます。( $n, k$ は自然数、 $1 \le k \le n-1$ )

$c(n+1, k) - c(n, k) - c(n, k-1) = 0$ を示します。(7) より
$\begin{eqnarray*} & & c(n+1, k) - c(n, k) - c(n, k-1) \\ & = & \frac{(n+1)!}{k! \cdot (n+1-k)!} - \frac{n!}{k! \cdot (n-k)!} - \frac{n!}{(k-1)! \cdot (n-k+1)!} \\ & = & \frac{(n+1) \cdot n!}{k! \cdot (n-k+1) \cdot (n-k)!} - \frac{n!}{k! \cdot (n-k)!} - \frac{n!}{\frac{k!}{k} \cdot (n-k+1) \cdot (n-k)!} \\ & = & \frac{n!}{k! \cdot (n-k)!} \cdot \left(\frac{n+1}{n-k+1} - 1 - \frac{k}{n-k+1}\right) \\ & = & 0 \end{eqnarray*}$
となり成り立ちます。