數學傳播

摘要:

正整數 ^{註1 註1} 本文約定: 正整數集 ${\mathbb Z}_+=\{1, 2, 3, \ldots\}$, 自然數集 ${\mathbb N}=\{0, 1, 2, \ldots\}$。 的冪和似乎是個永恆的話題, 眾述紛紜。 本文致力於介紹一種便捷的算法 , 並且創作出一款優雅的證明。 此算法屬線性代數型, 其特色在於無需遞推。 令人驚訝的是, 冪和竟然與「賈憲三角」有著密切的關係!

開門須見山。本文之核心乃下述定義及定理。

定義: 所謂「前 $n$ 個正整數的 $p$ 次冪和」, 是指 \begin{equation} %(1) S_p(n) = \sum_{m=1}^n m^p = 1^p + 2^p + \cdots + n^p, \quad p \in {\mathbb N}. \end{equation}

定理: 冪和 $S_p(n)$ 是關於 $n$ 的、缺常數項的 $p+1$ 次多項式, 即 \begin{equation} %(2) S_p(n) = \sum_{q=1}^{p+1} a_q n^q = {\bf a}^T {\bf n}, \end{equation} 這裡 $$ {\bf a} = \Big [a_1 \quad a_2 \quad \cdots \quad a_{p+1} \Big ]^T, \qquad {\bf n} = \Big [n \quad n^2 \quad \cdots \quad n^{p+1} \Big ]^T; $$ 並且向量 ${\bf a}$ 滿足方程 \begin{equation} %(3) \left [ \begin{array}{cccccc} {1\choose 0} & -{2\choose 0} & {3\choose 0} & \cdots & (-1)^{p-1}{p\choose 0} & (-1)^p{p+1\choose 0} \\ & {2\choose 1} & -{3\choose 1} & \cdots & (-1)^{p-2}{p\choose 1} & (-1)^{p-1}{p+1\choose 1} \\ & & {3\choose 2} & \cdots & (-1)^{p-3}{p\choose 2} & (-1)^{p-2}{p+1\choose 2} \\ & & & \ddots & \vdots \quad~ & \vdots \quad~ \\ & \hbox{ 0} & & & {p\choose p-1} & -{p+1\choose p-1} \\ & & & & & {p+1\choose p} \end{array} \right ] \left [ \begin{array}{c} a_1 \\ a_2 \\ a_3 \\ \vdots \\ a_p \\ a_{p+1} \end{array} \right ] = \left [ \begin{array}{c} 0 \\ 0 \\ 0 \\ \vdots \\ 0 \\ 1 \end{array} \right ], \end{equation} 其中 $\displaystyle{p\choose q}=\frac{p!}{q!(p-q)!}$ 為二項式係數。 $\Box$

我們把位於(3)式左邊的那個矩陣作$\bf U$ ^{註2 註2} Upper triangular matrix, 上三角陣。, 其代表元素為

\begin{equation} %(4) u_{ij} = \left \{ \begin{array}{lcl} (-1)^{j-i} \displaystyle{j\choose i-1}, & \quad & \hbox{當 } i \le j; \\ 0, & \quad & \hbox{當 } i \gt j. \end{array} \right. \end{equation} 再者, 記 $[\underbrace{0\quad \cdots\quad 0\quad 1}_{p+1}]^T={\bf e}$. 於是, 可將(3)式簡寫為 $$ {\bf Ua} = {\bf e}. (3') $$ 如果您很細心的話, 想必已經發現了:

1. 祇要將 $\bf U$ 轉置, ${\bf U}^T$ 中的所有非零元素便構成了缺一層斜邊的、正負項 交錯的賈憲三角;
2. $\bf e$ 是 ${\mathbb R}^{p+1}$ 的標準基底向量(standard basis vectors)之一。

不證明, 未可信! 筆者思索出的證明分為三個步驟, 請跟我來------

第一步 縮和(telescoping sum)

由二項式定理, 有 \begin{eqnarray*} (m-1)^{r+1} &=& \sum_{q=0}^{r+1} {r+1\choose q}(-1)^{r+1-q}m^q \\ &=& \Big [\sum_{q=0}^r {r+1\choose q} (-1)^{r+1-q} m^q \Big ] + m^{r+1}, \end{eqnarray*} 移項 ^{註3 註3} 注意, $\Sigma$ -和式中的各項皆須變號,即改 $(-1)^{r+1-q}$ 為 $(-1)^{r-q}$ 。, 得 \begin{equation} %(5) \sum_{q=0}^r (-1)^{r-q} {r+1\choose q} \cdot m^q = m^{r+1} - (m-1)^{r+1}. \end{equation}

在(5)式中依次令 $m=1, 2, \cdots, n$, 一舉獲得 $n$ 個等式。 纍加諸式, 縮和其右端, 列豎式如下: $$ \begin{array}{lclclclcl} & & \sum_{q=0}^r(-1)^{r-q}{r+1\choose q} & \cdot & 1^q & = & 1^{r+1} & - & 0^{r+1} \\ & & \sum_{q=0}^r(-1)^{r-q}{r+1\choose q} & \cdot & 2^q & = & 2^{r+1} & - & 1^{r+1} \\ & & {\vdots} & & & {\vdots} & & {\vdots} \\ +) & & \sum_{q=0}^r(-1)^{r-q}{r+1\choose q} & \cdot & n^q & = & n^{r+1} & - & (n-1)^{r+1} \\ \hline & & \sum_{q=0}^r(-1)^{r-q}{r+1\choose q} & \cdot & S_q(n) & = & n^{r+1} & - & 0^{r+1} \end{array} $$ 由此,我們得出重要的等式 \begin{equation} %(6) \sum_{q=0}^r(-1)^{r-q}{r+1\choose q}\cdot S_q(n)=n^{r+1}. \end{equation}

第二步 佈陣 ^{註4 註4} 構造矩陣。

將(6)式左邊寫為兩個 $r+1$ 維向量相乘的形式, 得 $$ \Bigg [(-1)^r {r+1\choose 0} \quad (-1)^{r-1} {r+1\choose 1} \quad \cdots \quad {r+1\choose r} \Bigg ] \left [ \begin{array}{c} S_0(n) \\ S_1(n) \\ \vdots \\ S_r(n) \end{array} \right ] = n^{r+1}. (6') $$

在 $(6')$ 式中依次令 $r=0, 1, \cdots, p$, 總共得到 $p+1$ 個等式。合併眾式如下: \begin{equation} %(7) \left [ \begin{array}{cccccc} {1\choose 0} & & & & & \\ -{2\choose 0} & {2\choose 1} & & \hbox{ 0} & & \\ {3\choose 0} & -{3\choose 1} & {3\choose 2} & & & \\ \vdots & \vdots & \vdots & \ddots & & \\ (-1)^{p-1}{p\choose 0} & (-1)^{p-2}{p\choose 1} & (-1)^{p-3}{p\choose 2} & \cdots & {p \choose p-1} & \\ (-1)^p{p+1\choose 0} & (-1)^{p-1}{p+1\choose 1} & (-1)^{p-2}{p+1\choose 2} & \cdots & -{p+1\choose p-1} & {p+1\choose p} \end{array} \right ] \left [ \begin{array}{c} S_0(n) \\ S_1(n) \\ S_2(n) \\ \vdots \\ S_{p-1}(n) \\ S_p(n) \end{array} \right ] = \left [ \begin{array}{c} n \\ n^2 \\ n^3 \\ \vdots \\ n^p \\ n^{p+1} \end{array} \right ]. \end{equation} 我們把位於(7)式左邊的那個矩陣記作 ${\bf L}$ ^{註5 註5} Lower triangular matrix, 下三角陣。, 顯然其轉置 \begin{equation} %(8) {\bf L}^T = {\bf U}. \end{equation}

再者, 記$[S_0(n)\quad S_1(n)\quad\cdots\quad S_p(n)]^T=\bf s$ 。於是, 可將(7)式簡寫為 $$ {\bf Ls} = \bf n. (7') $$

第三步 抽矢 ^{註6 註6} 在矩陣中抽取(行/列)向量。~矢, 原義為「箭」, 此處指「矢量」------向量的別稱。

顯而易見, ${\bf L}$ 的行列式 $\det{\bf L}=(p+1)!\not=0$, 故 ${\bf L}$ 可逆。 以其逆 ${\bf L}^{-1}$ 同時左乘 $(7')$ 式兩邊, 得 \begin{equation} %(9) {\bf s} = {\bf L}^{-1} {\bf n}, \end{equation}

從而 $ S_p(n) = \text{row}({\bf s}, p+1) = \text{row}({\bf L}^{-1}, p+1) ~{\bf n}. ~ $^{註7 註7} $\text{row}({\bf M}, r)$ 表示抽取矩陣 $\bf M$ 的第 $r$ 行。

可見, 前述 ${\bf a}^T=\text{row}({\bf L}^{-1}, p+1)$。至此(2)式得證!

另外,由於 ${\bf L}^{-1}{\bf L}={\bf E}$ ^{註8 註8} ${\bf E}=\text{diag}[\underbrace{1\quad \cdots\quad 1}_{p+1}]$為單位矩陣。, 因而 $$ \text{row}({\bf L}^{-1}, p+1){\bf L} = \text{row}({\bf E}, p+1). $$ 把 $\text{row}({\bf L}^{-1}, p+1)={\bf a}^T$ 及 $\text{row}({\bf E}, p+1)= [\underbrace{0\quad \cdots\quad 0\quad 1}_{p+1}]={\bf e}^T$ 代入上式, 得 \begin{equation} %(10) {\bf a}^T{\bf L} = {\bf e}^T. \end{equation}

最終, 我們有 $$ {\bf Ua}\buildrel (8)\over={\bf L}^T{\bf a} = {\bf L}^T({\bf a}^T)^T = ({\bf a}^T{\bf L})^T\buildrel (10)\over=({\bf e}^T)^T = {\bf e}. $$ 至此 $(3')$ 式得證, 亦即(3)式成立!

算法得以證明, 僅肯定了其正確性; 至於其實用性, 目前尚無法評價。 讓我們以 $S_9(n)$ 為試金石, 看看此算法到底靈也不靈!

值得補充的是, 如若果真按照(4)式來計算 ${\bf U}$ 中的各個元素, 那定然使人難耐其繁, 好在二項式係數具有一條可愛的性質: \begin{equation} %(11) {p\choose q} = {p-1\choose q} + {p-1\choose q-1}. \end{equation} 其證明極易, 故不贅言。事實上,賈憲三角正是據此而作成的(可參閱 )。

另外, 為了便於行文, 我們引進兩個名詞: 「上斜層, 下斜層」。 稱呼 $r$ 階方陣的主對角線為第1上(下)斜層, 緊貼於第1上(下)斜層上(下)方的副對角線為第2上(下)斜層, 以此類推, 直至第 $r$ 上(下)斜層------方陣右上(左下)角的單個元素。

以下, 我們就來陳述 $S_9(n)$ 的演算流程。 對照前文所給出的定理、公式及下面這個方程, 各道工序都是易於理解的。 $$ \left [ \begin{array}{ccccccccccccccccccc} 1 & ~& -1 & ~& 1 & ~& -1 & ~& 1 & ~& -1 & ~& 1 & ~& -1 & ~& 1 & ~& -1 \\ & ~& 2 & ~& -3 & ~& 4 & ~& -5 & ~& 6 & ~& -7 & ~& 8 & ~& -9 & ~& 10 \\ & ~& & ~& 3 & ~& -6 & ~& 10 & ~& -15 & ~& 21 & ~& -28 & ~& 36 & ~& -45 \\ & ~& & ~& & ~& 4 & ~& -10 & ~& 20 & ~& -35 & ~& 56 & ~& -84 & ~& 120 \\ & ~& & ~& & ~& & ~& 5 & ~& -15 & ~& 35 & ~& -70 & ~& 126 & ~& -210 \\ & ~& & ~& & ~& & ~& & ~& 6 & ~& -21 & ~& 56 & ~& -126 & ~& 252 \\ & ~& & ~& & ~& & ~& & ~& & ~& 7 & ~& -28 & ~& 84 & ~& -210 \\ & ~& & ~& 0 & ~& & ~& & ~& & ~& & ~& 8 & ~& -36 & ~& 120 \\ & ~& & ~& & ~& & ~& & ~& & ~& & ~& & ~& 9 & ~& -45 \\ & ~& & ~& & ~& & ~& & ~& & ~& & ~& & ~& & ~& 10 \end{array} \right ] \left [ \begin{array}{c} a_1 \\ a_2 \\ a_3 \\ a_4 \\ a_5 \\ a_6 \\ a_7 \\ a_8 \\ a_9 \\ a_{10} \end{array} \right ] = \left [ \begin{array}{c} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ \end{array} \right ] $$

• (A) 指定冪次 $p=9$。
• (B1) 製作 $p+1$ 階方陣 ${\bf U}_0$, 使之符合下列要求:
  • 首行的所有元素均為1;
  • 屬於主對角線的諸元素, 從左至右依次為 $1, 2, \cdots, p+1$ ;
  • 主對角線上方的其餘元素, 皆等於各自的左鄰元與左上鄰元之和; ^{註9 註9} 依據(11)式。
  • 主對角線下方的所有元素均為0。
• (B2) 在 ${\bf U}_0$ 中, 將序號為偶數的「上斜層」全部冠以負號, 於是生成方陣 ${\bf U}$。
• (C) 採用「逆向代入法」(backward substitution)求解方程 ${\bf Ua}={\bf e}$, ^{註10 註10} 因為 ${\bf U}$ 是行-階梯形矩陣。 從而解出向量 ${\bf a}$ 。
• (D) 以 $n$ 的降冪為序, 展示 $S_p(n)={\bf a}^T{\bf n}$。

上述流程完全是機械化的, 因而可以利用數學軟體來實現。 筆者所用的是著名的Maple 8, 該軟體具有強大的符號運算功能。 下面, 請您瀏覽這段Maple程式, 它結構清晰,一目了然。

> with(LinearAlgebra):            >   end do:
> p:=9:                           > end do:
> r:=p+1:                         > for j from 1 to r do
> m:=Vector(r):                   >   for i from 1 to j do
> U:=Matrix(r,shape=triangular):  >     U[i,j]:=(-1)^(j-i)*U[i,j]:
> for j from 1 to r do            >   end do:
>   m[j]:=n^j:                    > end do:
>   U[1,j]:=1:                    > E:=IdentityMatrix(r):
>   U[j,j]:=j:                    > e:=Column(E,r):
> end do:                         > a:=BackwardSubstitute(U,e):
> for j from 3 to r do            > S:=DotProduct(a,m):
>   for i from 2 to j-1 do        > S:=sort(S);
>     U[i,j]:=U[i,j-1]+U[i-1,j-1]:

激活Maple 8, 在其工作窗口中輸入並執行以上程式, 一眨眼, 聰明的Maple便算出了下述結果。 $$ S := \frac{1}{10} n^{10} + \frac{1}{2} n^{9} + \frac{3}{4}n^8 - \frac{7}{10}n^{6} + \frac{1}{2}n^{4} - \frac{3}{20}n^2 $$ 即使將源程式的第二行改為 ${\rm p:=500:}$ , 且以低檔電腦執行之, 耗時也不過20秒而已。 算法如此快速, 其實用性毋庸置疑!

猜想, 起源於觀察。 欲全面觀察各次冪和, 最佳途徑莫過於求出(9)式中之 ${\bf L}^{-1}$, 因為它的第 $q+1$ 行給出了 $S_q(n)$ 的係數。 下面, 我們就用Maple來計算14階的 ${\bf L}^{-1}$。 為此, 將源程式的第二行改成 ${\rm p:=13:}$ , 並將其末尾四行替換成左下方的兩行 ^{註11 註11} 在程式中以 L1 表示 ${\bf L}^{-1}$。

執行修改後的程式, 輸出如右上方所示------狡猾的Maple不直接顯示超過10階的矩陣, 解決辦法是分塊顯示。例如, 指令 SubMatrix(L1, 8..14, 1..7); 可用來顯示 L1 左下角的 $7\times 7$ 子塊, 餘者仿此。人工拼接這些子塊,得到

不難發現, 在 ${\bf L}^{-1}$ 中:

1. 第1下斜層(即主對角線)的第 $r$ 個元素為 $\displaystyle\frac{1}{r}$ $(r=1, 2, \cdots, 14)$;
2. 第2下斜層的所有元素皆為 $\displaystyle\frac{1}{2}$;
3. 第3--14下斜層的符號特徵可以列表如下------Eureka! 週期性!

掌握了以上三條線索,順藤摸瓜,筆者提出下述猜想------

猜想: 對於任意 $p\in{\mathbb N}$, 冪和多項式 $$ S_p(n) = a_{p+1} n^{p+1}+a_{p} n^p + \cdots + a_{1}n $$ 之係數滿足下列條件: $$ a_{p+1} = \frac{1}{p+1}, \qquad a_p = \frac{1}{2}; (12\hbox{a}) $$

$ \hbox{sgn }a_{p-q} = \sin \frac{q\pi}{2} \qquad (q = 1, 2, \cdots, p-1). (12\hbox{b}) $^{註12 註12} $\hbox{ sgn } x=\left \{ \begin{array}{lcl} -1, & \quad & \hbox{ 若 } x \lt 0; \\ 0, & \quad & \hbox{ 若 } x = 0; \quad \hbox{ 稱為「符號函數」(signum function)。} \\ 1, &\quad & \hbox{ 若 } x \gt 0. \end{array} \right.$

事實上, (12a)式是容易證明的, 祇需解出方程(3)底端的兩行 $$ \left \{ \begin{array}{ccccc} \displaystyle{p\choose p-1}a_{p} & - & \displaystyle{p+1\choose p-1}a_{p+1} \quad & = & 0 \\ [5pt] & & \displaystyle{p+1\choose p}a_{p+1} \quad & = & 1 \end{array} \right. $$ 即可。至於(12b)式, 就留與諸位研究吧。

本文所介紹的冪和算法, 屬於 H. J. Schultz 。 他在推測 ^{註13 註13} 原文為"we make the reasonable guess that"---我們有理由猜測。 (2)式成立的基礎上, 用「未定係數法」導出了方程(3)。 無疑, 如此推導存在著漏洞。 儘管該漏洞可以被彌補: 用「縮和法 $+$ 數學歸納法」, 證明(2)式並非很困難(可參閱)------但是打了補丁的方案畢竟「真而不美」。

創作一款「真而美」的證明! 這, 便是筆者的初衷。 之後, 筆者收穫了稱心如意的證明, 進而編程解決了冪和多項式的係數計算問題。 不料, 卻又引出了更為複雜的係數結構問題, 可謂「庸人自擾」。 然而, 「探索無止境」, 這不恰是數學的魅力所在嘛!

---本文作者畢業於江蘇省南京航空航天大學---