38208 冪次和表為n之多項式的係數律則

終極密碼

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

證明等式 $1^2 + 2^2 + \cdots + n^2 = \frac{1}{3} n^3 + \frac{1}{2} n^2 + \frac{1}{6} n$ 及 $1^3 + 2^3 + \cdots + n^3 = \frac{1}{4} n^4 + \frac{1}{2} n^3 + \frac{1}{4} n^2$, 幾乎是學過數學歸納法的人必有的經驗。 證明是一回事, 較為深刻的應當是提問: 這些等式是如何知道的?

這裡, 我們換個角度來看此問題。 假定我們已經知道一般 $1^k + 2^k + \cdots + n^k$ 是可表為一個 $n$ 的多項式, 且其最高次項為 $\frac{1}{k+1} n^{k+1}$ (註), 那麼, 知道了多項式的各項係數, 便等同於找出了這些等式。

把 $1^k + 2^k + \cdots + n^k$ 表為 $n$ 的多項式 $F_k(n)$ 時, 其通項 $n^{k-m}$ 的係數記為 $A_m$。 由 $F_k(0) = 0$, 知 $F_k(n)$ 的常數項為 $0$; 把 $F_k(n)$ 的最高次項記為 $A_{-1} n^{k+1}$。 因此 $$ F_k(n) = A_{-1} n^{k+1} + A_0 n^k + A_1 n^{k-1} + \cdots + A_{k-1} n $$ 除了已知 $A_{-1} = \frac{1}{k+1}$ 之外, $A_0, A_1, \ldots, A_{k-1}$ 的呈現是否具有規律? 我們有 \begin{eqnarray*} F_1(n) &=& \frac{1}{2} n^2 + \frac{1}{2} n \\ F_2(n) &=& \frac{1}{3} n^3 + \frac{1}{2} n^2 + \frac{2}{12} n \\ F_3(n) &=& \frac{1}{4} n^4 + \frac{1}{2} n^3 + \frac{3}{12} n^2 + 0 \cdot n \\ F_4(n) &=& \frac{1}{5} n^5 + \frac{1}{2} n^4 + \frac{4}{12} n^3 + 0 \cdot n^2 - \frac{1}{30} n \end{eqnarray*} 觀察上面實例, 規律似乎存在。如果存在, 它是什麼樣子?

首先, 由 \begin{eqnarray*} &&1^k + 2^k + \cdots + n^k = A_{-1} n^{k+1} + A_0 n^k + A_1 n^{k-1} + \cdots + A_{k-1} n\\ \hbox{所以} && 1^k + 2^k + \cdots + (n-1)^k\\ &=& A_{-1} (n-1)^{k+1} + A_0 (n-1)^k + A_1 (n-1)^{k-1} + \cdots + A_{k-1} (n-1) \hskip 1cm\qquad~ \\ &=& A_{-1} [ n^{k+1} - C_1^{k+1} n^k + C_2^{k+1} n^{k-1} - C_3^{k+1} n^{k-2} + \cdots ] \\ && + A_0 [ n^k - C_1^k n^{k-1} + C_2^k n^{k-2} - C_3^k n^{k-3} + \cdots ] \\ && + A_1 [ n^{k-1} - C_1^{k-1} n^{k-2} + C_2^{k-1} n^{k-3} - C_3^{k-1} n^{k-4} + \cdots ] \\ && \quad \vdots \\ && + A_{k-1} [n-1] \end{eqnarray*} 上面二式相減得 \begin{eqnarray*} [ A_{-1} C_1^{k+1} \!-\!1 ] n^k \!-\! [ A_{-1} C_2^{k+1} \!-\! A_0 C_1^k ] n^{k-1} \!+\! [ A_{-1} C_3^{k+1} \!-\! A_0 C_2^k \!+\! A_1 C_1^{k-1} ] n^{k-2} \qquad~ \\ - [ A_{-1} C_4^{k+1} - A_0 C_3^k + A_1 C_2^{k-1} - A_2 C_1^{k-2} ] n^{k-3} + \cdots = 0 \end{eqnarray*} 因為上式是一個 $n$ 的恆等式, 故其每項係數皆為 $0$, 因此有: \begin{eqnarray*} 1 - A_{-1} C_1^{k+1} = 0 \hskip 1cm&&\nonumber \\ A_0 C_1^k - A_{-1} C_2^{k+1} = 0 \hskip 1cm&&(1.0) \nonumber \\ A_1 C_1^{k-1} - A_0 C_2^k + A_{-1} C_3^{k+1} = 0 \hskip 1cm&&(1.1) \nonumber \\ A_2 C_1^{k-2} - A_1 C_2^{k-1} + A_0 C_3^k - A_{-1} C_4^{k+1} = 0 \hskip 1cm&&(1.2) \nonumber\\ \vdots\hskip 6cm &&\quad \vdots\nonumber\\ \hbox{一般為} A_m C_1^{k-m} - A_{m-1} C_2^{k-m+1} + A_{m-2} C_3^{k-m+2} - \cdots + (-1)^{m+1} A_{-1} C_{m+2}^{k+1} = 0 \hskip 1cm&& (1.m)\hskip 1cm \qquad~\nonumber \end{eqnarray*} 因 $C_1^{k-m} = k-m$, 所以上面的一般式可化約為: $$ A_m = \frac{1}{2} A_{m-1} C_1^{k-m+1} - \frac{1}{3} A_{m-2} C_2^{k-m+2} + \cdots + (-1)^m \frac{1}{m+2} A_{-1} C_{m+1}^{k+1} $$

由此而得 \begin{eqnarray*} A_{-1} &=& \frac{1}{k+1} \\ A_{0} &=& \frac{1}{2} = \frac{1}{2} C_0^k = a_0 \cdot C_0^k \hskip 3.7cm (\text{記}\ \frac{1}{2} = a_0 (=A_0)) \\ A_1 &=& \frac{1}{2} A_0 C_1^k - \frac{1}{3} A_{-1} C_2^{k+1} \\ &=& ( \frac{1}{2} a_0 - \frac{1}{6} ) C_1^k = a_1 \cdot C_1^k \hskip 3cm (\text{記}\ \frac{1}{2} a_0 - \frac{1}{6} = a_1) \\ A_2 &=& \frac{1}{2} A_1 C_1^{k-1} - \frac{1}{3} A_0 C_2^k + \frac{1}{4} A_{-1} C_3^{k+1} \\ &=& \frac{1}{2} a_1 C_1^k C_1^{k-1} - \frac{1}{3} a_0 C_2^k + \frac{1}{12} C_2^{k} \\ &=& (a_1 - \frac{1}{3} a_0 + \frac{1}{12}) C_2^k = a_2 \cdot C_2^k \hskip 2cm (\text{記}\ a_1 - \frac{1}{3} a_0 + \frac{1}{12} = a_2) \end{eqnarray*} 以此類推, $A_3$ 可表為 $a_3 \cdot C_3^k$; $A_4$ 可表為 $a_4 \cdot C_4^k$ 等等。

假定 $A_{m-1}$ 可表為 $a_{m-1} \cdot C_{m-1}^k$, 則由 \begin{eqnarray*} A_m &=& \frac{1}{2} A_{m-1}C_1^{k-m+1} - \frac{1}{3} A_{m-2} C_2^{k-m+2} + \cdots + (-1)^m \frac{1}{m+2} A_{-1} C_{m+1}^{k+1}\\ \Rightarrow A_m &=& \frac{1}{2} a_{m-1} \cdot C_{m-1}^k C_1^{k-m+1} \!-\! \frac{1}{3} a_{m-2} \cdot C_{m-2}^k C_2^{k-m+2} \!+\! \cdots\!+\! (-1)^m \frac{1}{(m\!+\!1)(m\!+\!2)} C_m^k \\ &=& \frac{1}{2} a_{m-1} \cdot m \cdot C_m^k - \frac{1}{3} a_{m-2} \cdot \frac{m(m-1)}{2!} \cdot C_m^k \!+\! \cdots\!+\! (-1)^m \frac{1}{(m\!+\!1)(m\!+\!2)} C_m^k \\ &=& \Big[ \frac{1}{2} C_1^m \cdot a_{m-1} - \frac{1}{3} C_2^m \cdot a_{m-2} + \cdots + (-1)^{m-1} \cdot \frac{1}{m+1} C_m^m \cdot a_0\\ &&+ (-1)^m \frac{1}{(m+1)(m+2)}\Big] C_m^k \end{eqnarray*} 所以 $A_m$ 亦可表為 $a_m \cdot C_m^k$。

故由數學歸納, 我們得到如下結論:

定理: $1^k \!+\! 2^k \!+\! \cdots \!+\! n^k$ 表為 $n$ 之多項式 $F_k(n)$ 時, 其通項 $n^{k-m}$ 的係數為 $A_m \!=\! a_m \cdot C_m^k$, 其中 $$a_m = \frac{1}{2} C_1^m \cdot a_{m-1} - \frac{1}{3} C_2^m \cdot a_{m-2} + \cdots + (-1)^{m-1} \frac{1}{m+1} C_m^m \cdot a_0 + (-1)^m \frac{1}{(m+1)(m+2)}$$

其次, 由 $$ 1^k + 2^k + \cdots + n^k = A_{-1} n^{k+1} + A_0 n^k + A_1 n^{k-1} + \cdots + A_{k-1} n $$ 所以 \begin{eqnarray*} &&\hskip -25pt 1^k + 2^k + \cdots + (n+1)^k\\ &=& A_{-1} (n+1)^{k+1} + A_0 (n+1)^k + A_1 (n+1)^{k-1} + \cdots + A_{k-1} (n+1) \\ &=& A_{-1} [ n^{k+1} + C_1^{k+1} n^k + C_2^{k+1} n^{k-1} + C_3^{k+1} n^{k-2} + \cdots ] \\ && + A_0 [ n^k + C_1^k n^{k-1} + C_2^k n^{k-2} + C_3^k n^{k-3} + \cdots ] \\ && + A_1 [ n^{k-1} + C_1^{k-1} n^{k-2} + C_2^{k-1} n^{k-3} + C_3^{k-1} n^{k-4} + \cdots ] \\ && \quad \vdots \\ && + A_{k-1} [n+1] \end{eqnarray*} 上面二式相減得 \begin{eqnarray*} (n+1)^k &=& A_{-1} C_1^{k+1} n^k + [A_{-1} C_2^{k+1} + A_0 C_1^{k}] n^{k-1} + [A_{-1} C_3^{k+1} + A_0 C_2^k + A_1 C_1^{k-1}] n^{k-2} \\ && + [ A_{-1} C_4^{k+1} + A_0 C_3^k + A_1 C_2^{k-1} + A_2 C_1^{k-2} ] n^{k-3} + \cdots \end{eqnarray*} 比較兩邊係數得 \begin{eqnarray*} C_0^k &=& A_{-1} C_1^{k+1} \nonumber \\ C_1^k &=& A_0 C_1^k + A_{-1} C_2^{k+1} \hskip 5.6cm (2.0) \\ C_2^k &=& A_1 C_1^{k-1} + A_0 C_2^k + A_{-1} C_3^{k+1} \hskip 3.7cm (2.1) \\ C_3^k &=& A_2 C_1^{k-2} + A_1 C_2^{k-1} + A_0 C_3^k + A_{-1} C_4^{k+1} \hskip 1.8cm (2.2) \\ \vdots\ && \hskip 9cm \vdots \\ \hbox{一般為} C_{m+1}^k &=& A_m C_1^{k-m} + A_{m-1} C_2^{k-m+1} + \cdots + A_{-1} C_{m+2}^{k+1} \hskip 1cm (2.m) \end{eqnarray*} 現在把式 $(1.0) + (2.0)$, $(1.1) + (2.1)$, $(1.2) + (2.2)$, $\ldots$, $(1.m) + (2.m)$, 得 \begin{eqnarray*} C_1^k &=& 2 A_0 C_1^k \\ C_2^k &=& 2 [ A_1 C_1^{k-1} + A_{-1} C_3^{k+1} ] \\ C_3^k &=& 2 [ A_2 C_1^{k-2} + A_0 C_3^k ] \\ &\vdots& \\ C_{m+1}^k &=& 2 [A_m C_1^{k-m} + A_{m-2} C_3^{k-m+2} + \cdots ] \end{eqnarray*} 上面最後一式在

  1. $m$ 為偶數時 \begin{equation} %3.1 C_{m+1}^k = 2 [ A_m C_1^{k-m} + A_{m-2} C_3^{k-m+2} + \cdots + A_0 C_{m+1}^k ] \label{3.1} \end{equation}
  2. $m$ 為奇數時 \begin{equation} %3.2 C_{m+1}^k = 2 [ A_m C_1^{k-m} + A_{m-2} C_3^{k-m+2} + \cdots + A_1 C_m^{k-1} + A_{-1} C_{m+2}^{k+1} ] \label{3.2} \end{equation}

由於 $A_m$ 可表為 $a_m \cdot C_m^k$, 因此 \eqref{3.1} 式可化約為: \begin{equation} %4.1 1 = 2 [ C_1^{m+1} \cdot a_m + C_3^{m+1} \cdot a_{m-2} + \cdots + C_{m+1}^{m+1} \cdot a_0 ] \label{4.1} \end{equation} \eqref{3.2} 式可化約為: \begin{equation} %4.2 1 = 2 [ C_1^{m+1} \cdot a_m + C_3^{m+1} \cdot a_{m-2} + \cdots + C_m^{m+1} \cdot a_1 + \frac{1}{m+2} ] \label{4.2} \end{equation} 又由 $a_0 = \frac{1}{2}$, 式 \eqref{4.1} 可再化簡為: \begin{equation} %5 C_1^{m+1} \cdot a_m + C_3^{m+1} \cdot a_{m-2} + \cdots + C_{m-1}^{m+1} \cdot a_2 = 0 \label{5} \end{equation} 但 $$a_2 = a_1 - \frac{1}{3} a_0 + \frac{1}{12} = (\frac{1}{2} a_0 - \frac{1}{6}) - \frac{1}{3} a_0 + \frac{1}{12} = 0$$ 因此經由 \eqref{5} 式可推得 $a_4 = a_6 = \cdots = 0$, 即當 $m$ 為偶數時, $a_m$ 之值恆為 $0$。

由此, 我們更簡化了前述所得到的定理中關於 $F_k(n)$ 的通項 $n^{k-m}$ 的係數 $A_m = a_m \cdot C_m^k$, 其中的 $a_m$ 為: $$ \left \{ \begin{array} {l} \text{當 $m$ 為偶數時},\ a_m = 0, m = 2, 4, 6, \ldots \\ \text{當 $m$ 為奇數時},\ a_m = - (\frac{1}{3} C_2^m \cdot a_{m-2} \!+\! \frac{1}{5} C_4^m \cdot a_{m-4} \!+\! \cdots \!+\! \frac{1}{m} C_{m-1}^m \cdot a_1) + \frac{m}{2(m+1)(m+2)} \\ \hskip 1.3cm ( \text{或寫成: } a_m = - \frac{1}{m+1} [ C_3^{m+1} \cdot a_{m-2} + C_5^{m+1} \cdot a_{m-4} + \cdots + c_m^{m+1} \cdot a_1 - \frac{m}{2(m+2)} ] ) \end{array} \right . $$

例: 由 \begin{eqnarray*} a_0 &=& \frac{1}{2} \\ a_1 &=& \frac{1}{2 \cdot 2 \cdot 3} = \frac{1}{12} \\ a_3 &=& -a_1 + \frac{3}{2 \cdot 4 \cdot 5} = - \frac{1}{120} \\ a_5 &=& - \frac{10}{3} a_3 - a_1 + \frac{5}{2 \cdot 6 \cdot 7} = \frac{1}{252} \\ \vdots\ && \end{eqnarray*}

當 $k=6$ 時 \begin{eqnarray*} A_0 &=& \frac{1}{2} C_0^6 = \frac{1}{2} \\ A_1 &=& \frac{1}{12} C_1^6 = \frac{1}{2} \\ A_3 &=& - \frac{1}{120} C_3^6 = - \frac{1}{6} \\ A_5 &=& \frac{1}{252} C_5^6 = \frac{1}{42} \end{eqnarray*} 因此 $$ 1^6 + 2^6 + \cdots + n^6 = \frac{1}{7} n^7 + \frac{1}{2} n^6 + \frac{1}{2} n^5 - \frac{1}{6} n^3 + \frac{1}{42} n $$

註: 由二項式定理可得 $$ (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 + 1 $$ 經由此式, 得下列諸式: $$ \left \{ \begin{array} {rclrl} 2^{k+1} &-& 1^{k+1} &=& C_k^{k+1} \cdot 1^k + C_{k-1}^{k+1} \cdot 1^{k-1} + \cdots + C_1^{k+1} \cdot 1 + 1 \\ 3^{k+1} &-& 2^{k+1} &=& C_k^{k+1} \cdot 2^k + C_{k-1}^{k+1} \cdot 2^{k-1} + \cdots + C_1^{k+1} \cdot 2 + 1 \\ \vdots\quad~&&&& \\ (n\!+\!1)^{k+1} &-& n^{k+1} &=& C_k^{k+1} \cdot n^k + C_{k-1}^{k+1} \cdot n^{k-1} + \cdots + C_1^{k+1} \cdot n + 1 \end{array} \right . $$ 上面諸式相加, 得遞迴關係式: \begin{eqnarray*} (n+1)^{k+1} - 1 &=& C_k^{k+1} F_k(n) + C_{k-1}^{k+1} F_{k-1}(n) + \cdots + C_1^{k+1} F_1(n) + n,\qquad~ \\ \text{其中 }\hskip .2cm~ F_k(n) &=& 1^k + 2^k + \cdots + n^k, \qquad k = 1, 2, 3, \ldots \end{eqnarray*} 運用此式, 便知道, 對任意正整數 $k$, $1^k + 2^k + \cdots + n^k$ 確可表為一個 $n$ 的多項式, 且其最高次項為 $\frac{1}{k+1} n^{k+1}$。

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

文章 推薦

電腦模擬與賭局

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