38110 一個關於冪次和的定理

終極密碼

遊戲規則:本遊戲為猜密碼的遊戲。密碼為0到100之間的其中1個整數,電腦會提示密碼的所在範圍,玩家必須在6次之內猜到密碼才能過關。
★ 終極密碼為0到100之間 ★
您共有六次機會

唸高中時, 學數學歸納法, 有一道問題是: 證明 $1^3 + 2^3 + \cdots + n^3 = (1+2+\cdots+n)^2$。

$1^3 + 2^3 + \cdots + n^3$ 竟可表為 $1+2+\cdots+n$ 的多項式!? 那麼, 是否還有其它的 $1^k + 2^k + \cdots + n^k$ 亦可表為 $1+2+\cdots+n$ 的多項式? 這個疑惑深刻地留置於我心中。 之後, 三十年的教書期間, 也未曾好好地想過此一問題。 這些日子 (五月) 是梅雨期, 待在屋內無所事事, 深埋已久的這個疑惑又浮上我的心頭。

把 $1^k + 2^k + \cdots + n^k$ 的和記為 $S_k(n)$, 其中 $k$ 為任意正整數。 為行文的簡便, 不致混淆的情形下, 暫且把 $S_k(n)$ 簡記為 $S_k$。

由二項式定理 $$ (n+1)^{k+1} - n^{k+1} = C_k^{k+1} n^k + C_{k-1}^{k+1} n^{k-1} + \cdots + C_1^{k+1} n + C_0^{k+1} $$ 可推得 $$ (n+1) [ (n+1)^k -1 ] = C_k^{k+1} S_k + C_{k-1}^{k+1} S_{k-1} + \cdots + C_1^{k+1} S_1 $$

此式表示 $S_1, S_2, \ldots, S_k$ 之間的一個遞迴關係。 所以, 如果知道 $S_1, S_2, \ldots, S_{k-1}$ 的 $n$ 的多項式表式, 則運用此式即可推得 $S_k$ 的 $n$ 的多項式的表式。 此外, 亦可由此式看出當 $S_k$ 表為 $n$ 的多項式時, 其最高次項為 $\frac{1}{k+1} n^{k+1}$。

我們已知有: \begin{eqnarray*} S_1 &=& \frac{1}{2} n^2 + \frac{1}{2} n \\ S_2 &=& \frac{1}{3} n^3 + \frac{1}{2} n^2 + \frac{1}{6} n \\ S_3 &=& \frac{1}{4} n^4 + \frac{1}{2} n^3 + \frac{1}{4} n^2 \qquad \text{等} \end{eqnarray*} 除了利用上述遞迴關係來找出 $S_k$ 的 $n$ 之多項式表式之外, 是否 $S_k$ 還有其它的呈現方式? 經由導算, 得到下列結果: \begin{eqnarray*} S_3 &=& \frac{4}{4} S_1^2 \\ S_5 &=& \frac{8}{6} S_1^3 - \frac{1}{3} S_1^2 \\ S_7 &=& \frac{16}{8} S_1^4 - \frac{4}{3} S_1^3 + \frac{1}{3} S_1^2\\ \hbox{及} S_4 &=& \Big( \frac{6}{5} S_1 - \frac{1}{5} \Big) S_2 \\ S_6 &=& \Big( \frac{12}{7} S_1^2 - \frac{6}{7} S_1 + \frac{1}{7} \Big) S_2 \\ S_8 &=& \Big( \frac{24}{9} S_1^3 - \frac{8}{3} S_1^2 + \frac{6}{5} S_1 - \frac{1}{5} \Big) S_2 \end{eqnarray*} 這是以 $S_1$ 與 $S_2$ 為基元來呈現 $S_k$ 的一種表式。 觀察上面諸式, 隱然呈現了某些共通的規律。 事實上, 我們有下面的定理。

定理:

  1. 當 $k$ 為奇數時, $S_k$ 恆可表為一個純 $S_1$ 的多項式, 其最高次項為 $\frac{2^m}{k+1} S_1^m$, 其中 $k=2m-1$; 最低次項則為 $C \cdot S_1^2$, 其中 $C$ 為一個相應於 $k$ 的常數 (此時, 限於 $k \ge 3$)。
  2. 當 $k$ 為偶數時, $S_k$ 恆可表為一個純 $S_1$ 的多項式與 $S_2$ 的乘積, 其最高次項為
    $\frac{3 \cdot 2^{m-1}}{k+1} S_1^{m-1} \cdot S_2$, 其中 $k=2m$; 最低次項則為 $C \cdot S_2$, 其中 $C$ 為一個相應於 $k$ 的常數。
  3. 承 (1) 與 (2), $S_k$ 表為 $S_1$ 與 $S_2$ 的多項式時, 其係數和恆為 $1$。

證明

(1)(2): 首先, 由 $$ n^{k+1} - (n-1)^{k+1} = C_k^{k+1} n^k - C_{k-1}^{k+1} n^{k-1} + \cdots + (-1)^{k-1} C_1^{k+1} n + (-1)^k $$ 可導得另一個遞迴關係式: $$ n^{k+1} - (-1)^k n = C_k^{k+1} S_k - C_{k-1}^{k+1} S_{k-1} + \cdots + (-1)^{k-1} C_1^{k+1} S_1 $$ 與之前的遞回關係式: $$ (n+1)^{k+1} - (n+1) = C_k^{k+1} S_k + C_{k-1}^{k+1} S_{k-1} + \cdots + C_1^{k+1} S_1 $$ 兩者相加得到另一遞迴關係式: $$ [(n+1)^{k+1} - (n+1)] + [ n^{k+1} - (-1)^k n ] = 2 [ C_k^{k+1} S_k + C_{k-2}^{k+1} S_{k-2} + \cdots ] $$

(i) 當 $k$ 為奇數時, 關係式成為 \begin{equation} %(a) (n+1)^{k+1}+ n^{k+1} - 1 = 2 [ C_k^{k+1} S_k + C_{k-2}^{k+1} S_{k-2} + \cdots + C_1^{k+1} S_1 ] \label{a} \end{equation} 取 $$f_k(n) = (n+1)^{k+1} + n^{k+1} - 1,$$ 由 $$f_k(0) = f_k(-1) = 0,$$ 知 $f_k(n)$ 有因式 $n(n+1)$, 但 $$n(n+1) = 2 S_1,$$ 因此 $f_k(n)$ 有因式 $S_1$。

如果我們能夠證明, 無論 $k$ 為任何奇數, $f_k(n)$ 恆可表為一個純 $S_1$ 的多項式, 又加以 $S_3=S_1^2$, $S_5 = \frac{4}{3} S_1^3 - \frac{1}{3} S_1^2$ 等初始條件的滿足, 則由此遞迴關係式, 經數學歸納, 即是證得了 $S_k$ 恆可表為一個純 $S_1$ 的多項式。

因 $k$ 為奇數, 令 $k = 2m - 1$, $m \gt 1$, 因此 $$ f_k(n) = (n+1)^{2m} + n^{2m} - 1 $$ 記為 $$ F_m(n) = (n+1)^{2m} + n^{2m} - 1 $$

(ii) 當 $k$ 為偶數時, 關係式成為 \begin{equation} %(b) (n+1)^{k+1} + n^{k+1} - (2n+1) = 2 [ C_k^{k+1} S_k + C_{k-2}^{k+1} S_{k-2} + \cdots + C_2^{k+1} S_2 ] \label{b} \end{equation} 取 $$g_k(n) = (n+1)^{k+1} + n^{k+1} - (2n+1),$$ 由 $$g_k(0) = g_k(-1) = g_k(- \frac{1}{2}) = 0,$$ 知 $g_k(n)$ 有因式 $n(n+1)(2n+1)$, 但 $$n(n+1)(2n+1) = 6 S_2,$$ 因此 $g_k(n)$ 有因式 $S_2$。

如果我們能夠證明, 無論 $k$ 為任何偶數, $g_k(n)$ 恆可表為一個純 $S_1$ 的多項式與 $S_2$ 的乘積, 又加以 $S_4 = ( \frac{6}{5} S_1 - \frac{1}{5}) S_2$, $S_6 = ( \frac{12}{7} S_1^2 - \frac{6}{7} S_1 + \frac{1}{7} ) S_2$ 等初始條件的滿足, 則由此遞迴關係式, 經數學歸納, 即是證得了 $S_k$ 恆可表為一個純 $S_1$ 的多項式與 $S_2$ 的乘積。

因 $k$ 為偶數, 令 $k = 2m - 2$, $m \gt 1$, 因此 $$ g_k(n) = (n+1)^{2m-1} + n^{2m-1} - (2n + 1) $$ 記為 $$ G_m(n) = (n+1)^{2m-1} + n^{2m-1} - (2n + 1) $$

其次, 以 $n+1$ 及 $n$ 為兩根造一個二次方程式 $$ x^2 - (2n+1) x + n(n+1) = 0 $$ 因此有 $$ \left \{ \begin{array} {l} (n+1)^{2m} - (2n+1)(n+1)^{2m-1} + n(n+1)(n+1)^{2m-2} = 0 \\[4pt] n^{2m} - (2n+1) n^{2m-1} + n(n+1) n^{2m-2} = 0 \end{array} \right . $$ 上面二式相加得 $$ [ (n+1)^{2m} + n^{2m} ] - (2n+1) [ (n+1)^{2m-1} + n^{2m-1} ] + n(n+1) [ (n+1)^{2m-2} + n^{2m-2} ] = 0 $$ 改寫為 \begin{eqnarray*} [ (n+1)^{2m} + n^{2m} - 1] - (2n+1) [ (n+1)^{2m-1} + n^{2m-1} - (2n+1) ]\qquad~ \\ + n(n+1) [ (n+1)^{2m-2} + n^{2m-2} - 1 ] + 1 - (2n+1)^2 + n(n+1) = 0 \end{eqnarray*} 但是 $$ 1 - (2n+1)^2 + n(n+1) = - 3n(n+1) = - 6 S_1 $$ 即得 \begin{equation} %(A) F_m(n) - (2n+1) \cdot G_m(n) + 2 S_1 \cdot F_{m-1}(n) - 6 S_1 = 0 \label{A} \end{equation}

假定 $G_m(n)$ $(= g_k(n))$ 果真是一個純 $S_1$ 的多項式與 $S_2$ 的乘積, 此時,

令 $G_m(n) = h_m(S_1) \cdot S_2$, 則 \begin{eqnarray*} (2n+1) \cdot G_m(n) &=& h_m(S_1) \cdot (2n+1) S_2 \\ &=& h_m(S_1) \cdot \Big(\frac{8}{3} S_1^2 + \frac{1}{3} S_1\Big) \hskip 3cm \text{(註1)} \end{eqnarray*} 也就是說 $(2n+1) \cdot G_m(n)$ 可表為一個純 $S_1$ 的多項式。

因此我們可以說: 假定 $G_m(n)$ 可表為一個純 $S_1$ 的多項式與 $S_2$ 的乘積, 則由遞迴關係式 \eqref{A}, 經數學歸納, 便得到 $F_m(n)$ 恆可表為一個純 $S_1$ 的多項式。

再回到以 $n+1$ 及 $n$ 為兩根所造的二次方程式 $$ x^2 - (2n+1) x + n(n+1) = 0 $$ 我們也有 $$ \left \{ \begin{array} {l} (n+1)^{2m-1} - (2n+1)(n+1)^{2m-2} + n(n+1)(n+1)^{2m-3} = 0 \\[3pt] n^{2m-1} - (2n+1) n^{2m-2} + n(n+1) n^{2m-3} = 0 \end{array} \right . $$ 上面二式相加得 $$ [ (n+1)^{2m-1} + n^{2m-1} ] - (2n+1) [ (n+1)^{2m-2} + n^{2m-2} ] + n(n+1) [ (n+1)^{2m-3} + n^{2m-3} ] = 0 $$ 改寫為 \begin{eqnarray*} [ (n+1)^{2m-1} + n^{2m-1} - (2n+1) ] - (2n+1) [ (n+1)^{2m-2} + n^{2m-2} - 1 ]\qquad~\\ + n(n+1) [ (n+1)^{2m-3} + n^{2m-3} - (2n+1) ] + n(n+1)(2n+1) = 0 \end{eqnarray*} 但是 $$ n(n+1)(2n+1) = 6S_2 $$ 即得 \begin{equation} %(B) G_m(n) - (2n+1) \cdot F_{m-1}(n) + 2 S_1 \cdot G_{m-1}(n) + 6 S_2 = 0 \label{B} \end{equation} 假定 $F_{m-1}(n)$ ($= f_{k-1}(n)$) 果真能夠表為一個純 $S_1$ 的多項式, 因 $f_{k-1}(n)$ 有因式 $S_1$, 此時, 令 $F_{m-1}(n) = k_{m-1}(S_1) \cdot S_1$, 則 \begin{eqnarray*} (2n+1) \cdot F_{m-1}(n) &=& k_{m-1}(S_1) \cdot (2n+1) S_1 \\ &=& 3 k_{m-1}(S_1) \cdot S_2 \end{eqnarray*} 也就是說 $(2n+1) \cdot F_{m-1}(n)$ 可表為一個純 $S_1$ 的多項式與 $S_2$ 的乘積。

因此我們可以說: 假定 $F_{m-1}(n)$ 可表為一個純 $S_1$ 的多項式, 則由遞迴關係式 \eqref{B}, 經數學歸納, 便得到 $G_m(n)$ 恆可表為一個純 $S_1$ 的多項式與 $S_2$ 的乘積。

由於 \begin{eqnarray*} F_2(n) &=& (n+1)^4 + n^4 -1 = 8 S_1^2 + 8 S_1 \hskip 3.8cm \text{(註2)} \\ G_2(n) &=& (n+1)^3 + n^3 - (2n+1) = 6 S_2 \hskip 3.65cm \text{(註3)} \\ F_3(n) &=& (n+1)^6 + n^6 - 1 = 16 S_1^3 + 36 S_1^2 + 12 S_1 \hskip 2cm \text{(註4)} \\ G_3(n) &=& (n+1)^5 + n^5 - (2n+1) = (12 S_1 + 18) S_2 \hskip 1.8cm \text{(註5)} \end{eqnarray*}

這些事實滿足了數學歸納的初始條件, 經由關係式 \eqref{A} 與 \eqref{B}, 我們確定如下結論: $F_m(n)$ 恆可表為一個純 $S_1$ 的多項式, $G_m(n)$ 恆可表為一個純 $S_1$ 的多項式與 $S_2$ 的乘積。 隨之, 我們亦即證得了: $$ \left \{ \begin{array} {l} \text 當 k 為奇數時, S_k 恆可表為一個純 S_1 的多項式。 \\[5pt] \text 當 k 為偶數時, S_k 恆可表為一個純 S_1 的多項式與 S_2 的乘積。 \end{array} \right . $$

現在, 來看 $S_k$ 表為 $S_1$、 $S_2$ 的多項式時的最高次項與最低次項。

已知 $S_k$ 表為 $n$ 之多項式時, 其最高次項為 $\frac{1}{k+1} n^{k+1}$, 且 $S_1 = \frac{1}{2} n^2 + \frac{1}{2} n$, $S_2 = \frac{1}{3} n^3 + \frac{1}{2} n^2 + \frac{1}{6} n$, 因此,

  1. 當 $k$ 為奇數 ($k = 2m-1$) 時, $$ \frac{1}{k+1} n^{k+1} = \frac{1}{k+1} n^{2m} = \frac{1}{k+1} (2S_1 - n)^m = \frac{2^m}{k+1} S_1^m + \cdots $$
  2. 當 $k$ 為偶數 ($k=2m$) 時, \begin{eqnarray*} \frac{1}{k+1} n^{k+1} = \frac{1}{k+1} n^{2(m-1)+3} &=& \frac{1}{k+1} (2 S_1 - n)^{m-1} \cdot (3 S_2 - \frac{3}{2} n^2 - \frac{1}{2} n ) \\ &=& \frac{3 \cdot 2^{m-1}}{k+1} S_1^{m-1} \cdot S_2 + \cdots \end{eqnarray*}

至於最低次項的情形,

(i) 當 $k$ 為奇數時, 我們回到關係式 \eqref{a}: $$ (n+1)^{k+1} + n^{k+1} - 1 = 2 [ C_k^{k+1} S_k + C_{k-2}^{k+1} \cdot S_{k-2} + \cdots + C_1^{k+1} S_1 ] $$

即 \begin{equation} %(a') (n+1)^{k+1} + n^{k+1} - 1 - 2 C_1^{k+1} S_1 = 2 [ C_k^{k+1} S_k + C_{k-2}^{k+1} S_{k-2} + \cdots + C_3^{k+1} S_3 ] \label{a'} \end{equation} 取 $$p_k(n) = (n+1)^{k+1} + n^{k+1} - 1 - 2 C_1^{k+1} S_1$$ 則 $$ p'_k(n) = (k+1) [ (n+1)^k + n^k - 2n - 1 ] $$ 由 $$ p'_k(0) = p'_k(-1) = 0 $$ 知 $$ p'_k(n) \text{有因式 } n(n+1) $$

再由多項式的重根定理知 $p_k(n)$ 有因式 $n^2 (n+1)^2$, 即 $p_k(n)$ 有因式 $S_1^2$。 因此, 由關係式 \eqref{a'} 及 $S_3 = S_1^2$ 滿足初始條件, 經數學歸納, 便得到: $S_k$ 表為一個純 $S_1$ 的多項式時, 其最低次項為 $c \cdot S_1^2$, 其中 $c$ 是一個相應於 $k$ 的常數。

(ii) 當 $k$ 為偶數時,

由關係式 \eqref{b}: $$ (n+1)^{k+1} + n^{k+1} - (2n+1) = 2 [ C_k^{k+1} S_k + C_{k-2}^{k+1} S_{k-2} + \cdots + C_2^{k+1} S_2 ] $$ 即 \begin{equation} %(b') (n+1)^{k+1} + n^{k+1} - (2n+1) - 2 C_2^{k+1} S_2 = 2 [ C_k^{k+1} S_k + C_{k-2}^{k+1} S_{k-2} + \cdots + C_4^{k+1} S_4 ] \label{b'} \end{equation} 取 $$q_k(n) = (n+1)^{k+1} + n^{k+1} - (2n+1) - 2 C_2^{k+1} S_2$$ 由於在前文中我們已知 $(n+1)^{k+1} + n^{k+1} - (2n+1)$ 有因式 $S_2$, 因此, $q_k(n)$ 有因式 $S_2$。 又 $$ q'_k(n) = (k+1) [ (n+1)^k + n^k ] - 2 - k(k+1) (n^2 + n + \frac{1}{6}) $$ 由 $$ q'_k(0) \ne 0, q'_k(-1) \ne 0 $$ 知 $q'_k(n)$ 無因式 $n(n+1)$, 即 $q'_k(n)$ 無因式 $S_1$, 因而由多項式的重根定理知道 $q_k(n)$ 無因式 $S_1^2$。 但 $q_k(n)$ 既有因式 $S_2$ (請注意: $S_2$ 亦有因式 $S_1$) , 便知道 $q_k(n)$ 表為一個純 $S_1$ 的多項式與 $S_2$ 的乘積時, 其最低次項必為 $\lambda \cdot S_2$, 其中 $\lambda$ 是一個常數。

因此, 由關係式 \eqref{b'} 及 $S_4 = (\frac{6}{5} S_1 - \frac{1}{5}) S_2$ 滿足初始條件, 經數學歸納, 便得到: $S_k$ 表為一個純 $S_1$ 的多項式與 $S_2$ 的乘積時, 其最低次項為 $C \cdot S_2$, 其中 $C$ 是一個相應於 $k$ 的常數。

以上, 便是關於定理中之 (1) 與 (2) 的證明部分。

(3): 承 (1) 與 (2), 令 $S_k = P_k (S_1, S_2)$, 由於 $S_k = S_k(n)$, 當 $n=1$ 時, $S_1(1) = S_2(1) = S_k(1) = 1$, 所以 $P_k(1, 1) = S_k(1) = 1$, 而 $P_k(1, 1)$ 是多項式 $P_k (S_1, S_2)$ 的係數和, 因此即證得 $S_k$ 表為 $S_1$ 與 $S_2$ 的多項式時, 其係數和恆為 $1$。

註 1: \begin{eqnarray*} n S_1 &=& \Big(\frac{2n+1}{2} - \frac{1}{2} \Big) S_1 = \frac{2n+1}{2} S_1 - \frac{1}{2} S_1 = \frac{3}{2} S_2 - \frac{1}{2} S_1 \\ n S_2 &=& n \cdot \frac{(2n+1) S_1}{3} = \frac{1}{3} S_1 \cdot n [ (n+1) + n ] = \frac{1}{3} S_1 \cdot (2 S_1 + n^2) \\ &=& \frac{2}{3} S_1^2 + \frac{1}{3} S_1 \cdot n^2 = \frac{2}{3} S_1^2 + \frac{1}{3} S_1 ( 2 S_1 - n ) = \frac{4}{3} S_1^2 - \frac{1}{3} n S_1 \\ &=& \frac{4}{3} S_1^2 - \frac{1}{3} ( \frac{3}{2} S_2 - \frac{1}{2} S_1 ) = \frac{4}{3} S_1^2 - \frac{1}{2} S_2 + \frac{1}{6} S_1\\ &&\hskip -25pt (2n+1) S_2 = 2 n S_2 + S_2 = \frac{8}{3} S_1^2 + \frac{1}{3} S_1 \end{eqnarray*}

註 2: \begin{eqnarray*} F_2(n) &=& (n+1)^4 + n^4 - 1 = 2 n^3 (n+1) + 2 n^2 (n+1) +4 n (n+1) \\ &=& 2n (n+1) [ n^2 + n ] + 8 S_1 = 8 S_1^2 + 8 S_1 \end{eqnarray*}

註 3: \begin{eqnarray*} G_2(n) &=& (n+1)^3 + n^3 - (2n+1) = n (n+1)(2n+1) \\ &=& 6 S_2 \end{eqnarray*}

註 4 與 註 5: 仿 (註 2) 與 (註 3) 之法, 利用 (註 1) 的結果, 即得 \begin{eqnarray*} F_3(n) &=& 16 S_1^3 + 36 S_1^2 + 12 S_1 \\ G_3(n) &=& ( 12 S_1 + 18 ) S_2 \end{eqnarray*} 附記: 若 $S_k$ 表為 $S_1$ 與 $S_2$ 的多項式而不受制於定理中之 (1) 與 (2) 的型式時, 其表出的形式並非唯一。 例如 $S_5 = \frac{4}{3} S_1^3 - \frac{1}{3} S_1^2$, 但也有 $S_5 = \frac{3}{2} S_2^2 - \frac{1}{2} S_1^2$。

(這裡, 作者非常感謝審核先生對此非唯一性的提醒)

---本文作者為國立科學園區實驗高中退休數學教師---

文章 推薦

電腦模擬與賭局

假設玩家A和B進行賭博。玩家A有m元,玩家B則有n元,然後擲1個公正的硬幣。如果出現正面就算玩家A贏,反面就算玩家B贏。每次賭注都是1元,如果A贏則A變m+1元、而B變n−1元,並稱此為1回合。雙方不斷地進行賭博,直到某方的錢歸零為止。在這個賭博中,有以下兩個問題:(1)玩家A和玩家B贏的機率各是多少?(2)每投1次硬幣決勝負,都稱為1回合,平均要幾回合,賭局才會結束(某方錢輸光)?....閱讀更多