? ? ? ?本人最近在讀TAOCP,雖感叢書(shū)內(nèi)容浩繁捶惜，難以在有限時(shí)間內(nèi)研讀死讹，但亦收獲頗豐。本文是在讀過(guò)“1.2.1 數(shù)學(xué)歸納法”（后文的“本篇”均指TAOCP 1.2.1）之后的思考胡诗，也包含本篇的關(guān)鍵內(nèi)容子刮，以供復(fù)習(xí)參考。
數(shù)學(xué)歸納法與廣義歸納法
? ? ? ?本篇是從數(shù)學(xué)歸納法開(kāi)始的悯蝉。稍有數(shù)學(xué)基礎(chǔ)的人都明白數(shù)學(xué)歸納法的內(nèi)容：
假定需要證明P(n)對(duì)所有正整數(shù)n為真归形，那么可以：
(1) 證明P(1)為真
(2) 證明“如果P(1),P(2),......,P(n)全部為真，那么P(n+1)也為真”鼻由，這個(gè)證明應(yīng)對(duì)任何正整數(shù)成立
? ? ? ?很容易看出暇榴，使用數(shù)學(xué)歸納法證明可以看成是一個(gè)輸出“P(n)為真”的程序/算法：
E1: k<-1，輸出P(1)的證明
E2: 如果k=n蕉世，那么結(jié)果已經(jīng)輸出
E3: 輸出“因?yàn)橐呀?jīng)證明了P(1),P(2),......,P(k)蔼紧，所以P(k+1)為真”
E4: k<-k+1，跳轉(zhuǎn)到E2
? ? ? ?那么我們?yōu)槭裁纯梢允褂眠@樣的歸納思想與歸納法呢狠轻？雖然上面的算法看起來(lái)已經(jīng)很簡(jiǎn)明奸例、正確，但是顯然數(shù)學(xué)歸納法涉及到了無(wú)窮的概念，我們是否需要證明數(shù)學(xué)歸納法的正確性呢查吊？實(shí)際上數(shù)學(xué)歸納法的思想是將P(n)的正確性與正整數(shù)n的定義綁定谐区，而正整數(shù)的定義天生就是歸納的，我們認(rèn)為正整數(shù)的歸納定義是一種公理化的定義逻卖，無(wú)需證明宋列，因此證明方式與正整數(shù)定義如出一轍的數(shù)學(xué)歸納法也無(wú)需證明。
? ? ? ?在證明一些難以表示為P(n)這樣僅與一個(gè)正整數(shù)變量有關(guān)评也，而至少要表示成P(p,q)這樣含有多個(gè)正整數(shù)變量的命題時(shí)炼杖，上面的數(shù)學(xué)歸納法就顯得力不從心。有的方法會(huì)曲線救國(guó)：先證明P(1,1)盗迟，再證明“P(1,1),P(2,1),......,P(p,1)為真可證明P(p+1,1)”與“P(p,1),P(p,2),......,P(p,q)為真可以證明P(p,q+1)”這兩條命題坤邪，分兩步得出結(jié)果。這不失為一個(gè)解決方案罚缕，但它沒(méi)有摸到歸納法的精髓罩扇。
? ? ? ?雖然數(shù)學(xué)歸納法作為一種古老的方法，依賴的是正整數(shù)的公理化歸納定義怕磨，但由它發(fā)展而來(lái)的廣義歸納法則是使用了集合與關(guān)系的理論，不僅能支持證明P(p,q),P(p,q,s)這樣的與正整數(shù)有關(guān)的命題消约，還擴(kuò)充了命題自變量的范圍肠鲫。
通過(guò)思考數(shù)學(xué)歸納法，我們可以樸素地將其思想總結(jié)為這樣：
如果我們能夠：
(1) 證明：“最開(kāi)始”的命題或粮；
(2) 證明：如果“所有排在前面”的命題都已經(jīng)被證明导饲，可以通過(guò)這些命題證明本命題。
那么就能證明這個(gè)命題“序列”里的任意一個(gè)命題氯材。
? ? ? ?經(jīng)過(guò)總結(jié)渣锦，我們可以提出在任意集合上的“良序”關(guān)系，借助這個(gè)關(guān)系氢哮，達(dá)到歸納證明的目的袋毙，不管集合的元素是不是同一類、是不是可數(shù)冗尤。
集合S上的良序關(guān)系@具備以下性質(zhì)：
(i) 傳遞性
(ii) 任意S上的x听盖、y，三種可能性：x@y裂七，y@x皆看，x=y恰有一種成立
(iii) 對(duì)S的任意非空子集A，A上存在元素x背零，使得A的任意元素y腰吟，都有x@y或x=y
? ? ? ?廣義歸納法推廣歸納法，在上面良序關(guān)系的基礎(chǔ)上說(shuō)明了：如果在P(y)對(duì)于所有x@y均為真的假定下能夠證明P(x)徙瓶，那么P(x)對(duì)S中的所有x為真毛雇。
? ? ? ?對(duì)于從良序關(guān)系的定義嫉称，我們可以看到一點(diǎn)“樸素”的歸納法思想：(i)與(ii)保障了集合元素上有全序，我們可以構(gòu)建“所有排在前面的命題”的列表用于證明當(dāng)前命題禾乘；(iii)保障了“最開(kāi)始的命題”的存在澎埠。顯然，正整數(shù)集上的“小于”關(guān)系就是良序關(guān)系始藕。類似地蒲稳，如果我們能夠?qū)ψ址蟂定義一個(gè)良序關(guān)系，那么就可以對(duì)等長(zhǎng)字符串集合T<sub>n</sub>（包含所有用來(lái)自S的字符構(gòu)成的長(zhǎng)為n的字符串）也定義一個(gè)良序：如果存在k (1 <= k <= n)使xj=yj對(duì)于1 <= j < k 恒成立,而xky<sub>k</sub>伍派，那么在T<sub>n</sub>上(x<sub>1</sub>,x<sub>2</sub>,...,<sub>n</sub>)(y1,y2,...,yn).
歸納法成果：算法正確性證明
? ? ? ?許多算法包括分支江耀、循環(huán)結(jié)構(gòu)，應(yīng)該如何使用有限的證明篇幅說(shuō)明可能執(zhí)行任意次分支诉植、循環(huán)的算法的正確性呢祥国？再?gòu)?fù)雜的算法也可以用流程圖表示它的有限個(gè)分支、循環(huán)步驟晾腔，利用廣義歸納法舌稀，我們可以找出每一個(gè)步驟之前的前提/斷言/不變量，然后證明經(jīng)過(guò)這個(gè)步驟之后灼擂，后續(xù)步驟的前提/斷言/不變量是正確的壁查。這要求在流程圖中：
如果指向某方框的至少一個(gè)箭頭上的斷言在執(zhí)行方框內(nèi)操作之前為真，那么離開(kāi)該方框的相關(guān)箭頭上的所有斷言在執(zhí)行方框內(nèi)操作之后都為真剔应。
? ? ? ?這樣一來(lái)睡腿，我們就可以用歸納的方法，說(shuō)明在算法每一個(gè)步驟（方框）前的斷言都為真峻贮，也就包括“算法終止”的步驟席怪，保證了算法終止時(shí)結(jié)論的正確性。
歸納思想成果：動(dòng)態(tài)編程
? ? ? ?動(dòng)態(tài)編程思想主要是：存儲(chǔ)可重用的中間計(jì)算結(jié)果纤控；使用較小規(guī)模的計(jì)算問(wèn)題答案擴(kuò)展到較大規(guī)模的問(wèn)題計(jì)算挂捻。這便應(yīng)用了歸納思想。在經(jīng)典的“曼哈頓地圖路徑”問(wèn)題中嚼黔，動(dòng)態(tài)編程將輸入慢慢從(2,2)擴(kuò)展到(m,n)细层，實(shí)際上就是手動(dòng)執(zhí)行歸納的每一步。在現(xiàn)實(shí)的大部分問(wèn)題中唬涧，解題使用(1,1)->(1,n),(m,1)->(m,n)的手段較多疫赎，并不會(huì)真正定義嚴(yán)格的良序并使用廣義歸納法。但是碎节，如果要解決與字符串有關(guān)的問(wèn)題捧搞，可以應(yīng)用前文所提的良序定義與廣義歸納法，使算法正確性更加容易證明。
