《用电脑证明组合恒等式》由会员分享，可在线阅读，更多相关《用电脑证明组合恒等式（7页珍藏版）》请在金锄头文库上搜索。
1、用電腦證明組合恆等式柳柏濂1998年1月, 在美國數學會 (AMS) 第104屆年會上, 美國 Temple 大學的 D. Zeil-berger 和 Pennsylvania 大學的 H. S. Wilf共同獲得美國數學會的 Steele 重大貢獻獎。他們的獲獎論文是1990年刊登在 美國數學會雜誌(J. Am. Math. Soc. 3卷147-158)上的“有理函數確證組合恆等式”。(Rationalfunctions certify combinatorial identi-ties)。 這篇簡短的論文, 提供了一個證明組合恆等式的全新方法。 從而, 開闢了一個機器證明的新天地。Zei
2、lberger和 Wilf 的方法,被稱為WZ 方法。 要闡述 WZ 方法如何使組合恆等式的證明進入計算機的代數系統中, 讓我們先從電腦證明恆等式談起。一. 舉例能代替證明嗎?這不是一個小學生提出來的問題, 而是一個數學家發出的挑戰性的詰問。的確, 從我們在初中開始學習平面幾何證明的那一刻起, 數學老師就把那金科玉律般的警句灌入我們的腦中: “舉例不能代替邏輯證明!”1986年, 數學家和計算機科學家洪加威先生就在 中國科學 的一篇文章 (2) 中,向那種傳統的觀念挑戰, 他的論文題目便是:“能用例證來證明幾何定理嗎?”。計算機的誕生, 計算機科學的發展, 機器證明理論的深入, 使數學研究傳統
3、的模式發生了變化。 既然, 計算機是一種擅長於數值處理工具, 那麼, 用量的表達代替形的描述, 用數值計算來代替邏輯推理, 便自然成為處理數學問題的新思維。我們從代數恆等式的證明將可以悟出:有時, 舉例的確可以代替證明。為了簡便敘述; 我們考察一個簡單的例子。 請讀者專注於我們所用的方法, 而不要發出“殺雞用牛刀”的責難。例如: 要證明代數恆等式(x + 1)(x2 x + 1) = x3+ 1(1)我們只須對 x 任意取4個數 (舉例)。 例如x = 1,0,1,2。 先後代入 (1) 式, 得0 = 0(當 x = 1)1 = 1(當 x = 0)4546數學傳播25卷3期 民90年9月2
4、 = 2(當 x = 1)9 = 9(當 x = 2)於是可以斷言: (1) 式恆成立。上述證明是可行的。 它的邏輯基礎是:若 (1) 式非恆等式, 則方程 x3+ 1 (x +1)(x2 x + 1) = 0 是一個3次方程。 根據高斯定理 (n 次代數方程至多有 n 個根)它至多只能有3個不同的根。 但由上面舉例證明, 它有4個不同的根, 矛盾!這種“舉例”方法, 就是用電腦證明代數恆等式的精髓。我們要證明恆等式f(x) = g(x)(2)其中 f(x) 和 g(x) 都是多項式, 且它們的最高次數是 n。 我們只須用 n+1 個不同的數,算得 n+1 個等式成立, (舉 n+1 個例子)
5、,則可證明 (2) 是恆等式。可能讀者會說: 用舉例方法證明恆等式(2), 方法是簡單, 但算起來可不容易。 但是,如果我們加入電腦這一武器, 算起來也就得心應手了。 要知道, 計算可是電腦的強項啊!從“有限”能推斷“無限”, 這正是數學的魅力所在。計算代替 (蘊含) 推理, 舉例達到證明。用電腦, 我們成功地實現了代數恆等式的證明。二. 先試用“萬金油”。我們剛剛為代數恆等式的機器證明歡呼, 可是, 用上述的賦值法, 即使我們有電腦,也不能證明組合恆等式。 因為組合恆等式是包含有二項式係數的恆等式, 如果把它看作一個方程的話, 我們面對的往往不是一個整式方程。翻開任一本離散數學, 你都會遇到
6、大量的組合恆等式問題, 作為一種技巧, 數學家會用一種模型方法去證明一些簡單的恆等式。例如, 恆等式Xk0nk! = 2n(3)可以用兩種方法去求一個 n 元集的所有子集個數, 從而輕易地建立起它們的恆等關係。 然而, 對於較複雜的大量組合恆等式, 數學家採用一種行之有效的代數技巧。 H. S. Wilf把它稱為“Snakeoil”。 我們姑且譯之為“萬金油”方法, 用數學語言來說, 這是生成函數方法。 它的基本原理是: 不直接用代數變換推導恆等式, 而轉去求帶參數的整個族的生成函數, 然後, 讀出生成函數的係數。最有幫助的級數 (生成函數) 通常是Xr0nr! xr= (1 + x)n(4)
7、Xr0rk! xr=xk (1 x)k+1(k 0)(5)Xn01 n+12nn! xn=1 2x(114x)(6)(註?nr? = 0, 當 r n)。為了說明萬金油方法, 我們考察兩個例子。例1: 求證Xk0k n k! =15h?1 +52?n+1用電腦證明組合恆等式47?1 52?n+1i (n = 0,1,2,.)(7)證明步驟如下:(i) 判斷和式依賴的自由變量是 n, 令f(n) =Xk0k n k!(ii) 設 F(x) 是 f(n) 的冪級數生成函數, 即令F(x) =Xnf(n)xn=XnxnXk0k n k!(iii) 交換兩個求和次序, 並利用已知的生成函數, 把和寫成
8、函數形式。F(x) =Xk0Xnk n k! xn=Xk0xkXnk n k! xnk(為了用(4)=Xk0xk(1 + x)k=Xk0(x + x2)k=1 1 x x2(8)(iv) 求出生成函數的係數, 便是 f(n)。易見, (8) 式是 Fibonacci 數的生成函數。 (見 數學傳播22卷第2期拙作 3), 它的展開式的 xn項係數便是 (7) 式的右邊。 至此, 便完成了 (7) 的證明。細心的讀者不難發現, 上述 (7) 式的證明中, 我們僅從左邊推導出右邊。 這既是證明, 也可看作求和。 因此, 用萬金油方法, 不僅僅可以證明組合恆等式, 也可以發現組合恆等式。我們再從下例
9、, 領略一下萬金油的“療效”。例2: 求證 Xkmk! n + km!=Xkmk! nk! 2k,(m,n 0) (9)證: 左邊乘以 xn, 對 n 0 求和並交換求和次序得Xkmk! xkXn0n + km! xn+k=Xkmk! xkxm (1 x)m+1=xm (1 x)m+1(1 +1 x)m=(1 + x)m (1 x)m+1如果用 xn乘右邊, 類似上述求和, 得Xkmk! 2kXn0nk! xn=1 1 xXkmk! (2x 1 x)k=1 1 x(1 +2x 1 x)m=(1 + x)m (1 x)m+1於是, (9) 式成立。用萬金油方法, 可以成功地發現和證明一大類組合恆
10、等式。 例如, 在組合數學中的一批反演公式以及超幾何函數中的恆等式。 如果說, 直接用簡單的組合恆等式去證明其它恆等式的方法是內部方法的話, 那麼, 萬金油48數學傳播25卷3期 民90年9月方法便是組合恆等式證明的外部方法。 這種方法近乎是程序性的, 然而它需要更多的人工技巧。 那麼, 能否尋求一種用計算機符號運算程序來證明組合恆等式的方法呢? 近年來,機器證明在幾何學上的成功更激勵數學家在組合恆等式的計算機證明上躍躍欲試。1990年, 美國費城的兩位數學家合作,找到了這樣的一種方法。三. 電腦, 還是要用電腦!Zeilberger, 1950年生於以色列海法。1976年在 Weizmann
11、 科學研究院獲博士學位。 後赴美, 先在費城 Drexel 大學任教, 後在費城 Temple 大學任教授。Wilf, 1931年生於費城, 在麻省理工學院上學, 1958年, 在哥倫比亞大學獲博士學位。 先在伊利諾大學任教, 1962年在賓州大學任教, 現任 Thomas. A. Scott 教授。他們刊登在 美國數學雜誌 上的獲獎論文。 提供了一個證明組合恆等式的新方法,用這一方法, 可統一處理一些從未解決的極難恆等式的證明。 更重要的, 它展示了用電腦證明組合恆等式的前景。下面, 讓我們追溯一下 Wilf 和 Zeil-berger 考慮問題的思路。若要證明一個恆等式XkU(n,k) =
12、 rhs(n),n = 0,1,2,.(10)我們可以把它變形, 用右邊的 rhs(n)除兩邊, 便得到一個標準形式 XkF(n,k) = 1,n = 0,1,2,.(11)這樣, 我們便把 (10) 式的證明, 轉化為 (11),即證明一個和式與 n 無關。為此, 把 (11) 式用 n+1 代替 n, 然後減去 (11) 得XkF(n + 1,k) F(n,k) = 0,n = 0,1,.(12)如果存在一個很好的函數 G(n,k), 使得F(n+1,k)F(n,k)=G(n,k+1)G(n,k)(13)這樣, (12) 式便能“壓縮”, 即k=KXk=LF(n + 1,k) F(n,k)
13、=k=KXk=LG(n,k + 1) G(n,k)= G(n,K + 1) G(n,L)(14)如果函數G(n,k)具有性質 G(n,)= 0, 則在 (14) 中, 令 K,L , 便知(12) 成立。由此想法, Wilf 和 Zeiberger 便得到下列定理。定理1: 設 (F,G) 滿足 (13), 並且lim kG(n,k) = 0,n = 0,1,2,.(15)則恆等式P kF(n,k) = 常數, n = 0,1, 2,. 成立。為了明瞭用 WZ 定理證明組合恆等式的過程, 我們先從一個最簡單的例子談起。用電腦證明組合恆等式49假設要證明恆等式Xknk! = 2n,n 0(16)
14、仿照 (11), 便得F(n,k) =nk! /2n,n 0(17)現在需要求函數 G(n,k), 它就是G(n,k) = n k 1! /2n+1(18)驗證 G(n,k) 合乎定理要求, 即 (13) 和 (15)成立。 經計算, 不難得到n + 1k! /2n+1nk! /2n= nk! /2n+1+n k 1! /2n+1, n 0及limnn k 1! /2n+1= 0,n 0,於是 (16) 成立。從上述過程, 我們看到證明組合恆等式的關鍵在於從 F 尋找 G, 若滿足 (13), (15)的 G 找出來, 我們就可以斷言, 恆等式已經由 WZ 對 (F,G) 所證明。讀者急於知道
15、的問題也許是: 如何從 F尋找 G?WZ方法應用於證明這樣的一類組合恆等式, 它的標準形 (11) 的函數 F, 具有使F(n + 1,k) F(n,k)和F(n,k 1) F(n,k)(19)都是 n 和 k 的有理函數的性質。 於是由 (13)的F(n + 1,k) F(n,k)= G(n,k + 1) G(n,k)得F(n + 1,k) F(n,k) 1=G(n,k + 1) F(n,k)G(n,k) F(n,k)進一步,F(n + 1,k) F(n,k) 1=G(n,k + 1) F(n,k)G(n,k) F(n,k 1)F(n,k1) F(n,k) (20)注意到條件 (19), 我
16、們令G(n,k) F(n,k 1)= R(n,k)(21)這裡 R(n,k) 是 n 和 k 的有理函數。 於是(20) 寫成F(n + 1,k) F(n,k) 1= R(n,k + 1) R(n,k) F(n,k 1) F(n,k)(21) 式可以寫成G(n,k) = R(n,k)F(n,k 1)(22)因此, 我們可以簡化尋找 G(n,k) 的方法。要得到 WZ 對 (F,G), 只需得到有理函數R(n,k), 並加以驗證便可。考察下列例子, 可以幫助我們進一步領會 WZ 方法的證明步驟。例3: 證明Xk(1)knk! 2kk! 4nk=2nn! , n 0(23)50數學傳播25卷3期 民90年9月證明: 易見F(n,k) = (1)knk
