紫牛、俄羅斯方塊與數學定理的證明
數學的一大樂趣，也是數學不同於其他科學的顯著標誌，就是它可以通過證明的方式幫助我們撥雲見日，消除疑慮。在其他科學領域，我們之所以接受某些法則，是因為這些法則與現實世界一致，但一旦有新的證據出現，這些法則就有可能被推翻或者修改。在數學領域，如果某個命題被證明為真，那麼它將永遠是真實的。例如，歐幾里得早在兩千多年前就證明了質數有無數個，對於這個命題的真實性，我們無須懷疑。技術誕生之後還會退出歷史舞台，但數學定理亙古不變。偉大的數學家高德菲·哈羅德·哈代（G. H. Hardy）說過：「同畫家和詩人一樣，數學家也是規律的創造者。數學家創造的規律之所以更加持久，原因就在於這些規律中蘊藏著思想。」我常常想，要想在學術方面取得不朽的成績，最好的辦法就是證明一條新的數學定理。
數學家不僅可以證明某些事情的確定性，還可以證明某些事情是不可能的。人們有時說：「你無法證偽。」這句話的意思是，你無法證明紫色奶牛不存在，因為說不定哪天就會出現一頭這樣的奶牛。但在數學領域，你可以證偽。例如，無論你怎麼努力，都找不到和為奇數的兩個偶數，也找不到比其他質數都大的質數。第一次接觸時，證明可能會讓我們望而生畏（也許第二次、第三次時我們還會感到害怕），需要不斷練習才能逐漸適應。但是，一旦你精於此道，就會覺得其樂無窮，無論是你自己動手證明，還是看別人的證明過程。好的證明就像一個精彩的故事，讓你滿心愉悅。
接下來，我和大家分享我第一次證明某件事是不可能的經歷。小時候，我喜歡玩遊戲、做智力測試題。一天，一位朋友給我出了一道難題，讓我興致盎然。他拿出一個空的8×8棋盤和32個普通的1×2雙方塊，然後問我：「你可以用這些雙方塊，把整個棋盤都蓋住嗎？」我說：「當然可以，只要每行放4個雙方塊就行了。」
用1×2的雙方塊覆蓋8×8的棋盤
他說：「非常好！現在，我們把右下角和左上角的這兩個方格去掉。」說完，他在這兩個方格上各放了一枚硬幣，表示這兩個區域不存在。「你可以用31個雙方塊覆蓋棋盤上剩下的62個方格嗎？」
去掉右下角和左上角的兩個方格之後，雙方塊可以蓋住整個棋盤嗎？
「也許可以吧。」我答道。但是，無論我怎麼擺放，雙方塊都無法蓋住整個棋盤。於是我想，這個任務是不是不可能完成呢？
「如果你覺得這個任務無法完成，你如何證明？」朋友問道。但是，擺放雙方塊的方法有無數種，如果我不一一嘗試，怎麼能證明這是一個不可能完成的任務呢？這時候，他給了我一點兒提示：「觀察一下棋盤上的顏色。」
顏色？這與顏色有什麼關係？我突然想明白了。由於去掉的兩個方格都是淺色的，因此棋盤上還剩下32個深色方格和30個淺色方格。每個雙方塊正好覆蓋一個淺色方格和一個深色方格，所以用31個雙方塊不可能蓋住整個棋盤。太棒了！
延伸閱讀
如果你喜歡上面的證明過程，那麼你肯定也會喜歡下面這個證明過程。俄羅斯方塊遊戲中有7種形狀各異的板塊，有時候它們分別被稱為I、J、L、O、Z、T、S。
這7個板塊可以拼成一個4×7的長方形嗎？
由於每個板塊都包含4個1×1方塊，因此我們自然想知道7個板塊是不是可以拼成一個4×7的長方形，拼裝的時候可以翻轉或旋轉這些板塊。事實證明，這個任務是無法完成的。如何證明它是不可能的呢？如下圖所示，把4×7長方形塗成14個淺色方格和14個深色方格。
請注意，除了T以外，其他的板塊無論擺放到哪個位置上，都會覆蓋兩個深色方格和兩個淺色方格。而在T覆蓋的4個方格中，有三個方格的顏色一樣。因此，無論其餘6個板塊怎麼擺放，它們都會覆蓋12個淺色方格和12個深色方格。剩餘的2個淺色方格和2個深色方格只能用板塊T來覆蓋，而這是不可能的。
如果我們認為某個數學命題是真實的，怎樣才能證明它的確是真實的呢？通常，先要對我們所研究的數學對像進行描述。例如，我們說整數集合
…，–2，–1，0，1，2，3，…
包含所有整數：正數、負數和零。
之後，我們要對這些對像做出一些顯而易見的假設。例如，「兩個整數的和或積一定是整數」。（下一章將討論幾何學，屆時我們會做出這樣的假設：「對於任意兩點，都可以畫出一條經過這兩點的直線」。）這些顯而易見的命題叫作「公理」（axioms）。在這些公理的基礎上，通過邏輯推理和代數運算，我們經常可以推導出一些正確的命題，叫作「定理」（theorems）。定理有時候並不是顯而易見的。閱讀本章，你可以學會證明數學命題的基本方法。
我們先來證明一些很容易取信於人的定理。第一次聽到「兩個偶數的和是偶數」、「兩個奇數的乘積是奇數」等命題時，我們通常會默默地舉出幾個實例，檢驗之後才會斷定這個命題是真實的或者有道理的。你有時甚至會想，這個命題太顯而易見了，都可以當作公理使用了。但是，我們沒必要把它作為公理，因為利用已知的公理，可以證明這個命題為真。在證明偶數和奇數的某些屬性時，我們需要先弄明白它們的含義。
「偶數」是2的倍數。用代數語言來表述的話，就是如果n = 2k，k是整數，那麼我們說n是偶數。0是不是偶數呢？是偶數，因為0 = 2×0。現在，我們可以證明「兩個偶數的和是偶數」這個命題了。
定理：如果m和n是偶數，那麼m + n也是偶數。
這是一個典型的「如果—那麼」定理。在證明這種命題時，我們通常會對「如果」部分做出假設，然後通過邏輯和代數運算，證明可以根據假設得出「那麼」部分。在本例中，我們假設m和n是偶數，希望得出m + n也是偶數的結論。
證明：假設m和n是偶數，因此m = 2j，n = 2k，其中j和k都是整數，進而可以得出：
m + n = 2j + 2k = 2 (j + k)
由於j + k是整數，因此m + n是2的倍數，從而證明m + n必然是偶數。
注意，上述證明的依據是，兩個整數的和（即本例中的j + k）也必然是整數這條公理。在證明複雜的命題時，我們不僅需要依賴一些基本公理，還可能需要利用已經被證明的定理。數學界的一個常見做法就是在證明結束之後，在最後一行的右側頁邊添加一個標識，例如□、■或者Q. E .D。Q. E. D是拉丁語「quod erat demonstrandum」的縮寫，意思是「證明完畢」。（如果你願意，你也可以把它看作英語「quite easily done」的縮寫，意思是「太簡單了」。）如果我認為某個證明過程特別美妙，我就會在結尾處畫一個笑臉符號（
）。
在證明了「如果—那麼」定理之後，數學家們開始考慮逆命題的真實性。逆命題就是把原命題的「如果」和「那麼」這兩個部分對調之後得到的命題。上例的逆命題是：「如果m + n是偶數，那麼m和n都是偶數」。只需舉出一個「反例」（counterexample），就能很容易地證明這是一個假命題。對於這個命題而言，我們可以舉一個非常簡單的反例：
1 + 1 = 2
這個例子表明，即使兩個數不是偶數，它們的和也可以是偶數。
下面討論一條關於「奇數」的定理。奇數是指不是2的倍數的數字。如果用2除以一個奇數，餘數一定是1。用代數語言來表述，就是如果n = 2k + 1，k是整數，那麼n是奇數。有了這個定義之後，我們只需通過簡單的代數運算，就能證明「兩個奇數的乘積是奇數」這個命題。
定理：如果m和n是奇數，那麼mn也是奇數。
證明：假設m和n是奇數。那麼m = 2j + 1，n = 2k + 1，j、k是整數。根據FOIL法則：
mn = (2j + 1) (2k + 1) = 4jk + 2j + 2k + 1 = 2 (2jk + j + k) + 1
由於2jk + j + k是整數，因此mn是「某個整數的2倍 + 1」，從而證明mn是奇數。 □
它的逆命題「如果mn是奇數，那麼m和n都是奇數」是否為真呢？這個命題也是真命題，我們可以利用「反證法」（proof by contradiction）來證明。反證法是指，如果我們否定結論（「m、n都是奇數」），我們之前做出的假設就不成立。因此，從邏輯上講，結論必定是成立的。
定理：如果mn是奇數，那麼m和n都是奇數。
證明：與結論相反，我們假設m或n是偶數（或同為偶數）。這兩個數字中到底哪一個是偶數無關緊要，我們假定m是偶數，也就是說，m = 2j，j為整數。那麼，乘積mn = 2jn也是偶數，這與我們之前假設mn是奇數的前提相悖。
如果某個命題和它的逆命題都是真命題，數學界就稱之為「當且僅當定理」（if and only if theorem）。我們前面已經完成了下述定理的證明工作。
定理：當且僅當mn是奇數時，m和n都是奇數。
有理數和無理數
上述定理不會讓你感到吃驚，它們的證明過程也非常直接。只在證明某些不太直觀的定理時，我們才可以體會到其中的樂趣。到目前為止，我們接觸的都是整數，現在可以進階到分數的相關定理的證明了。「有理數」（rational number）是指可以表示為分數形式的數字。更準確的說法是，如果r = a / b，其中a和b是整數（且b ≠ 0），那麼我們說r是有理數。不能表示為分數形式的數字叫作「無理數」（irrational number）。（你或許聽說過，數字π= 3.141 59…就是無理數，我們將在本書第8章對它進行詳細介紹。）
在介紹下一個定理之前，我們有必要回顧一下分數的加法。如果分數的分母相同，進行加法運算時就極為簡單。例如：
否則，我們必須先把它們化成分母相同的形式，再進行加法運算。例如：
一般而言，在計算兩個分數 a / b和c / d的和時，我們可以為它們賦予一個公分母，例如：
接下來，我們就可以證明有理數的一些簡單屬性了。
定理：兩個有理數的平均數仍然是有理數。
證明：令x和y為有理數，必然存在a、b、c、d，滿足x = a / b，y = c / d。所以，x和y的平均數為：
由此可見，該平均數是一個分數，且分子、分母均為整數。因此，有理數x和y的平均數也是有理數。
我們想一想，這個定理有什麼含義？它的意思是，對於任意兩個有理數，即使它們非常接近，我們也總能找出一個位於它們之間的有理數。也許你忍不住會想，所有的數字都是有理數（古希臘人也曾有這樣的想法）。但是，令人吃驚的是，這個想法是錯誤的。我們以
為例，這個數字的小數形式是1.414 2…。現在，我們有很多方法，用分數來近似地表示。例如，近似等於10 / 7或者1 414 /1 000，但是這些分數的平方都不會正好等於2。是不是因為我們找得還不夠仔細呢？下面這個定理告訴我們，無論我們怎麼努力，都會無功而返。該定理的證明採用了反證法，關於無理數的定理通常都會採用這種證明方法。我們知道，所有分數都可化簡至最簡分數，即分子和分母沒有大於1的公因數。下面的證明過程就將利用分數的這個特點。
定理：是無理數。
證明：我們假設是有理數，則必然存在正整數a和b，滿足：
= a / b
其中，a / b是最簡分數。等式兩邊同時進行平方運算，就有：
2 = a2 / b2
也就是說，a2 = 2b2。由此可知，a2必然是偶數。如果a2是偶數，那麼a也必然是偶數（前文中已經證明，如果a是奇數，那麼其自乘的結果也必然是奇數）。因此，a = 2k，k是整數。將它代入上面的等式，就有：
(2k)2 = 2b2
4k2 = 2b2
b2 = 2k2
因此，b2是偶數。既然b2是偶數，b也必然是偶數。但是，a和b都是偶數，這與a / b是最簡分數的前提相矛盾。因此，是有理數這個假設不成立，這證明是無理數。
單憑邏輯的力量，就證明了一個非常令人吃驚的結果，所以我十分喜歡這個證明過程（畫了個笑臉）。本書第12章將告訴我們，無理數非常多。事實上，從嚴格意義上講，絕大多數的實數都是無理數，儘管我們在日常生活中接觸的大多是有理數。
上面這條定理有一個有趣的「推論」（corollary），推論是指由某條定理推導得出的定理。這個推論的推導過程利用了「指數定律」（law of exponentiation），即對於任意整數a、b、c：
（ab）c = abc
例如，（53）2 = 56，這是有道理的，因為：
（53）2 = (5 × 5 × 5) × (5 × 5 × 5) = 56
推論：存在無理數a和b，使得ab是有理數。
儘管現在我們只知道一個無理數，即，但足以證明這條定理，這真是太棒了！下面的證明過程可以告訴你符合條件的a和b是存在的，但不能告訴你它們的值分別是多少。我們把這種證明稱為「存在性證明」（existence proof）。
證明：我們知道是無理數，我們來看
這個數字，它是不是有理數呢？如果是，那麼令a =，b =，命題就得到了證明。如果答案是否定的，就說明我們知道的無理數又多了一個，即。令a =，b =，根據指數定律，就可以得到：
答案是一個有理數。因此，無論是有理數還是無理數，我們都可以找到a、b，使得ab是有理數。
存在性證明這種證明方法通常很巧妙，但它有時也存在不盡如人意的地方，無法告訴你想要瞭解的所有信息。（如果你感到好奇，我可以告訴你是無理數，但這不屬於本章討論的範圍。）
更能讓人心滿意足的證明方法是「構造性證明」（constructive proof），因為它告訴你的信息正好是你想要瞭解的信息。例如，我們可以證明所有的有理數a / b都是有盡或者循環小數（這是因為，隨著除法運算的進行，b除過的數字必然會再次出現，並被b除）。但是，它的反命題是否正確？有盡小數必然是有理數，例如，0.123 58 =12 358 / 100 000。循環小數呢？例如，0.123 123 123…一定是有理數嗎？答案是肯定的。下面這種巧妙的方法可以告訴我們有理數到底是什麼。我們把這個神秘數字設為w，於是：
w = 0.123 123 123…
兩邊同時乘以1 000，上式就會變成：
1 000w = 123.123 123 123…
用第二個等式減去第一個等式，就會得到：
999w = 123
w =
=
我們換另一個循環小數再試一試。這一次的循環小數並不是從小數點後第一位就開始循環，比如，如何將小數0.833 33…表示成分數形式呢？先令：
x = 0.833 33…
兩邊同時乘以100：
100x = 83.333 3…
再同時除以10：
10x = 8.333 3…
從100x中減去10x，小數點後面的所有項都抵消了：
90x = (83.333 3…) – (8.333 3…) = 75
x =
=
運用構造性證明這種證明方法，我們可以證明當且僅當某個數字的小數形式是有盡或者循環小數時，該數才是有理數。如果某數的小數形式是不循環的無盡小數，例如：
v = 0.123 456 789 101 112 131 415…
這個數字就是無理數。
棋盤覆蓋問題與歸納性證明
我們再回過頭去，證明與正整數相關的一些定理。在本書第1章，通過觀察：
我們先提出前n個奇數的和是n2的命題，然後著手證明這個命題。當時，我們使用的是巧妙的「組合性證明」（combinatorial proof）法，即通過兩種方法統計棋盤的方格數，證明了這個命題的真實性。接下來，我們用一種無須巧妙構思的方法來證明這個命題。假設我告訴你（也許你本就深信不疑）前10個奇數的和1 + 3 + … + 19是102，即100，如果你表示同意，那麼再加上第11個奇數（21），和毫無疑問是121，也就是112。換句話說，如果針對前10個奇數該命題為真，那麼針對前11個奇數該命題同樣為真。這就是「歸納證性明」（proof by induction）法的指導思想。在涉及n的證明時，我們通常會先證明命題在一開始的時候（通常是n = 1時）是正確的，然後證明如果n = k時命題成立，那麼n = k + 1時它也成立。由此可證，在n取所有值時命題都成立。歸納性證明就像爬梯子：先證明你可以踏上梯子，然後證明如果你已經爬上了一級，就可以再向上爬一級。稍稍思考其中的道理，你就會相信自己可以爬上梯子的任意一級。
例如，對於前n個奇數的和這個命題，我們的目標是證明對於所有的n≥1，都有：
1 + 3 + 5 + … + (2n – 1) = n2
我們發現，第一個奇數1的和的確是12，因此當n = 1時，這個命題肯定是正確的。接下來，我們注意到，如果前k個奇數的和是k2，即：
1 + 3 + 5 + … + (2k – 1) = k2
再加上下一個奇數（2k + 1），就有：
1 + 3 + 5 + … + (2k – 1) + (2k + 1) = k2 + (2k + 1)
= (k + 1)2
也就是說，如果前k個奇數的和是k2，那麼前k + 1個奇數的和一定是(k + 1)2。既然n = 1時命題成立，由上述證明過程可知，n取所有值時該命題也成立。
歸納性證明法是一個功能強大的證明方法。本書討論的第一個問題是前n個數字的和：
1 + 2 + 3 + … + n =
當n = 1時，該命題肯定是正確的，因為1 = （1×2） / 2。如果我們假設對於某個數字k，命題
1 + 2 + 3 + … + k =
是正確的，在上式基礎上再加上 (k + 1)，就會得到：
1 + 2 + 3 + … + k + (k + 1) =
+ (k + 1)
= (k + 1) (
+ 1)
=
這是用 k + 1代替n時的求和公式。因此，如果n = k（k是任意正數）時公式成立，那麼當n = k + 1時，該公式同樣成立。由此可證，當n取所有正值時，公式都成立。
在本章以及後續章節中，我們將見到更多的歸納性證明實例。為了幫助大家加深印象，我在這裡為大家送上「數學音樂家」戴恩·坎普（Dane Camp）和拉裡·萊塞（Larry Lesser）創作的一首歌，這首歌採用了美國民謠歌手鮑勃·迪倫（Bob Dylan）的作品《答案在風中飄蕩》（Blowing in the Wind）的旋律。
如何才能證明n取所有值時
命題都成立？
既然無法一一驗證
盲目嘗試又有何益！
面臨如此困境，
能否找到錦囊妙計？
答案啊，我的朋友，是要學會歸納性證明，
答案是要學會歸納性證明！
首先研究開始時的情況
證明命題沒有問題，
然後假設n = k時命題為真
並證明n = k + 1時仍然成立！
至此問題迎刃而解
告訴我你是否感到滿意？
既然已經說了n次，說n + 1次又何妨
答案是要學會歸納性證明！
延伸閱讀
我們在本書第5章討論了斐波那契數列數字間的幾種相互關係。下面，我們就用歸納性證明法驗證其中幾個等式。
定理：對於n≥1，
F1 + F2 + … + Fn = Fn+2–1
證明：當n = 1時，上式為 F1 = F3–1，即1 = 2–1，這顯然是成立的。假設當n = k時，命題也成立，那麼：
F1 + F2 + … + Fk = Fk+2–1
在等式兩邊同時加上下一個數字Fk+1，就會得到
F1 + F2 + … + Fk + Fk+1 = Fk+1 + Fk+2 – 1
= Fk+3 – 1
證明完畢。 □
斐波那契數列的平方和等式的證明同樣簡單。
定理：對於n≥1，
證明：當n = 1時，上式為
= F1 F2，這顯然是成立的，因為F2 = F1 =1。假設當n = k時定理也成立，那麼：
在等式兩邊同時加上
，就會得到：
證明完畢。 □
我們在本書第1章發現，「三次方的和就是和的二次方」，例如：
13 = 12
13 + 23 = (1 + 2)2
13 + 23 + 33 = (1 + 2 + 3)2
13 + 23 + 33 + 43 = (1 + 2 + 3 + 4)2
但是，我們當時無法證明。有了歸納性證明法之後，就可以輕鬆完成證明工作了。這個一般性規律是：對於n ≥1，
13 + 23 + 33 + … + n3 = (1 + 2 + 3 + … + n)2
由於我們已經知道1 + 2 + … + n =
，因此我們可以證明下面這條等價定理。
定理：對於n≥1，
13 + 23 + 33 + … + n3 =
證明：當n = 1時，命題13 = (12×22) /4成立。如果n = k時定理也成立，就有：
13 + 23 + 33 + … + k3 =
兩邊同時加上 (k + 1)3，就會得到：
證明完畢。 □
延伸閱讀
下面是立方和公式的幾何證明。
我們用兩種方法計算上圖的面積，然後進行比較。一方面，這是一個正方形，它的邊長是1 + 2 + 3 + 4 + 5，因此它的面積是 (1 + 2 + 3 + 4 + 5)2。
另一方面，我們從左上角開始，沿對角線方向觀察，就會發現這個正方形是由1個1×1的正方形，2個2×2的正方形（其中一個正方形被分割成兩半），3個3×3的正方形，4個4×4的正方形（其中一個正方形被分割成兩半）和5個5×5的正方形構成的，因此它的面積等於：
(1×12) + (2×22) + (3×32) + (4×42) + (5×52)
= 13 + 23 + 33 + 43 + 53
由於計算的面積相等，所以：
13 + 23 + 33 + 43 + 53 = (1 + 2 + 3 + 4 + 5)2
利用相同的方法可以畫出邊長為1 + 2 + … + n的正方形，並證明下面這個等式成立：
13 + 23 + 33 + … + n3 = (1 + 2 + 3 + … + n)2
歸納性證明法不僅限於證明求和問題。只要我們可以用「較小」問題（n = k時）的答案來推導出「較大」問題（n = k + 1時）的答案，歸納性證明法往往就有用武之地。下面向大家介紹一個讓我深感滿意的歸納性證明實例。問題與本章開頭討論的棋盤覆蓋問題有關，但不是證明不可能性，而是證明某種可能性。而且，我們使用的不是雙方塊，而是L形的三方塊。
因為64不是3的倍數，全部使用三方塊的話是無法覆蓋8×8棋盤的。但是，如果在棋盤上放一個1×1方塊，那麼無論這個1×1方塊放在棋盤的什麼位置，我們都可以用三方塊覆蓋棋盤的剩餘面積。而且，這個命題不僅在棋盤的規格是8×8時為真，對於2×2、4×4、16×16的棋盤，該命題同樣成立。
定理：對於所有的n≥1，都可以用三方塊和一個1×1方塊完全覆蓋規格為2n×2n的棋盤，而且1×1方塊可以放置在棋盤的任何位置上。
證明：當n = 1時，定理成立，因為任何一個2×2的棋盤都可以用一個三方塊和一個1×1方塊來覆蓋，而且1×1方塊可以擺放在棋盤的任何位置上。接下來，假設當n = k時（即棋盤大小為2k×2k時）定理也成立。我們需要完成的任務是證明在棋盤大小為2k+1×2k+1時，該定理仍然成立。如下圖所示，將1×1方塊擺放在棋盤的任意位置上，然後將棋盤分成四等分。
用三方塊覆蓋棋盤
由於放有1×1方塊的那一等分的大小為2k×2k，因此，它可以被三方塊完全覆蓋（根據假設，當n = k時，定理成立）。接下來，我們在棋盤的中心位置放一個三方塊，讓它與其餘三個等分相交。這三個等分的大小分別為2k×2k，且其中有一個1×1方格已經被覆蓋了，所以用三方塊可以完全覆蓋住它們。因此，在棋盤大小為2k+1×2k+1時，定理仍然成立。
本節最後證明的等式有很多重要應用，我們將用歸納證明法和其他幾種不同方法予以證明。這個令人感興趣的問題是：如果從20 = 1開始，將2的前n次方相加，和是多少？下面是排在前幾位的2的冪次方：
1，2，4，8，16，32，64，128，256，512，1 024…
將它們加到一起，就會得到：
大家看出其中的規律了嗎？所有的和都比2的更高次冪小1。
定理：對於n≥1，
1 + 2 + 4 + 8 +… + 2n–1 = 2n – 1
證明：如上所述，當n = 1時（以及n = 2，3，4或5時）定理成立。假設當n = k時定理成立，就有：
1 + 2 + 4 + 8 +… + 2k–1 = 2k–1
在等式兩邊同時加上更高一階的2次冪，即2k，就會得到：
1 + 2 + 4 + 8 +… + 2k–1 + 2k = (2k – 1) + 2k
= 2×2k–1
= 2k+1–1 □
在第4章和第5章，我們通過運用不同方法回答同一個計數問題，證明了多種相互關係。看了下面的內容，你也許會認為組合性證明法真的非常重要！
問題：從n名曲棍球球員（球衣號碼為1~n）中選擇若干名球員加入體育聯合會代表團，要求代表團中至少包含1名球員，一共有多少種選擇方案？
第一種解法：每名球員都有參加或者不參加代表團這兩個選擇，因此選擇方案應該是2n種。但所有球員均不參加的情況是不允許的，還需要減去1。所以，一共有2n–1種選擇方案。
第二種解法：考慮參加者的球衣號碼最大的情況。如果1是最大號碼，選擇方案只有1種；如果2是最大號碼，選擇方案有2種（2號球員可能獨自參加，也可能和1號球員一起參加）；3是最大號碼時，選擇方案有4種（3號球員必須參加，1號和2號球員各有兩個選擇）。以此類推，n是最大球衣號碼時，選擇方案有2n–1種，因為n號球員必須參加，1號至n – 1號球員各有兩個選擇（參加和不參加）。加到一起，一共有1 + 2 + 4 + … + 2n–1種選擇方案。
由於這兩種解法都是正確的，因此必然會得出相同的答案。也就是說，1 + 2 + 4 + … + 2n–1 = 2n – 1。
不過，最簡單的證明方法可能是單純的代數運算，這讓我們不禁回想起把循環小數表示成分數形式的那個方法。
代數證明：
令S = 1 + 2 + 4 + 8 + … + 2n–1
兩邊同時乘以2，就會得到：
2S = 2 + 4 + 8 + … + 2n–1 + 2n
用第二個等式減去第一個等式，除了第一個等式的第一項和第二個等式的最後一項外，其餘各項都被消掉了，因此：
S = 2S–S = 2n – 1 □
我們剛剛證明的定理其實是二進製表示方法的關鍵內容。二進製表示方法非常重要，計算機就是利用它來存儲和處理數字的。二進製表示方法的理論依據是，所有數字都可以表示成2的不同次冪相加的唯一形式。例如：
83 = 64 + 16 + 2 + 1
在把十進制轉化成二進制時，每個2的冪次方用數字1表示，缺位的冪次方用數字0表示。在這個例子中，83 = (1×64) + (0×32) + (1×16) + (0×8) + (0×4) + (1×2) + (1×1)。因此，83的二進製表示就是：
83 = (1010011)2
我們怎麼知道所有正數都可以這樣表示呢？假設從1到99的所有數字都可以表示成2的不同次冪相加的唯一形式，我們怎麼知道100是否可以表示成這種唯一形式呢？首先，我們在100以內找到2的最高次冪，這個數字應該是64。（64是必不可少的嗎？是的，因為即使我們把1、2、4、8、16、32全部選上，它們的和也只有63。）選好64之後，我們還需要用2的不同次冪相加得到36，才能湊成100。根據假設，我們可以用2的不同次冪相加的唯一形式表示36，因此，100也必然有唯一的二進製表示。〔我們怎麼表示36呢？先找到2的最高次冪，然後得到36 = 32 + 4。因此，100 = 64 + 32 + 4的二進製表示就是 (1100100)2。〕我們可以將這個過程推而廣之，從而證明所有的正數都有唯一的二進製表示。
謎一般的質數
上文中我們證明了所有的正整數都可以表示成2的不同次冪相加的唯一形式。從某種意義上講，你可以把2的冪次方看作建築材料，通過加法運算，搭建起正整數這座大廈。接下來，我們將會看到質數通過乘法運算扮演了一個類似的角色：所有正整數都可以表示成質數乘積的唯一形式。2的冪次方很容易確認，不會給數學界帶來多少意外發現。質數則不同，它們複雜得多，還有很多未解之謎。
質數是只有1和它本身這兩個正約數的正整數。排在前幾位的質數是：
2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53…
1只有一個約數，就是它本身，因此1不是質數。（人們認為1不是質數，還有一個更重要的原因，稍後揭曉。）請注意，2是唯一一個既是偶數又是質數的數字。因此，有人可能會認為2是最奇怪的質數。
有3個或3個以上約數的正整數叫作「合數」，因為它們可以被分解成多個因數相乘的形式。排在前幾位的合數是：
4，6，8，9，10，12，14，15，16，18，20，21，22，24，25，26，27，28，30…
例如，4有3個約數：1，2和4。6有4個約數：1，2，3和6。注意，1既不是質數，也不是合數。數學界把1稱為「計數單位」（unit），它是所有整數的約數。
所有合數都可以表示成質數乘積的形式。比如，120 = 6×20，由於6和20是合數，可以表示成質數乘積的形式，即6 = 2×3，20 = 2×2×5。因此：
120 = 2×2×2×3×5 = 23×31×51
有意思的是，無論我們以何種方式開始，質因數分解的最後結果都是一樣的。這就是「唯一分解定理」（unique factorization theorem）得出的結論。唯一分解定理亦稱「算術基本定理」（fundamental theorem of arithmetic），指任何一個大於1的正整數都能分解成有限個質數的乘積的唯一形式。
順便告訴大家，我們認為1不是質數的真正原因就在於這條定理。例如，12可以分解成2×2×3，也可以分解成1×1×2×2×3，如果把1視為質數，那麼質因數分解就無法得出唯一的結果。
一旦知道某個數字如何分解，就可以瞭解到關於這個數字的很多信息。小時候，我最喜歡的數字是9，但在成長的過程中，我最喜歡的數字也在不斷「成長」，而且越來越複雜（例如，π = 3.141 59…，φ= 1.618…，e= 2.718 28…，以及沒有小數表達式的i，等等。我們將在本書第10章討論這些數字。）在接觸無理數之前，我一度非常喜歡2 520這個數字，因為在可以被從1到10的所有數字整除的數中，它是最小的一個。它的質因數分解表達式是：
2 520 = 23×32×51×71
只要知道某個數字的質因數分解結果，就可以立刻說出它有多少個正約數。例如，2 520的約數必然是2a×3b×5c×7d 的形式，其中a是0、1、2、3（4種可能），b是0、1、2（3種可能），c是0、1（2種可能），d是0、1（2種可能）。因此，根據乘法法則，2 520有4×3×2×2 = 48個正約數。
延伸閱讀
算術基本定理的證明需要利用質數的某個屬性（所有數論教科書都會在第1章證明這個屬性）：如果p是質數，而且是兩個或兩個以上數字乘積的一個約數，那麼p至少是其中一個乘數的約數。例如，
999 999 = 333×3 003
999 999是11的倍數，因此11必然是333或者3 003的約數。（的確如此，因為3 003 = 11×273。）然而，有的合數並不具有這個屬性。例如，60 = 6×10是4的倍數，但4既不是6的約數，也不是10的約數。
為了證明質因數分解的唯一性，我們先做一個相反的假設：某個數字的質因數分解結果不止一個。假設N是有兩個質因數分解結果的最小數字，例如：
p1p2…pr = N = q1q2…qs
其中，所有的pi和qj項都是質數。因為N肯定是p1的倍數，所以p1肯定是某個qj項的約數。為了方便起見，我們假定p1是q1的約數。由於q1是質數，因此肯定有q1 = p1。把上面的等式除以p1，就會得到：
p2…pr =
= q2…qs
這說明也有兩個質因數分解結果，但我們假設N才是有兩個質因數分解結果的最小數字，因此兩者是矛盾的。 □
延伸閱讀
在有的數字系統中，並不是所有的數字都有唯一的質因數分解結果。例如，火星人長了兩個腦袋，因此他們只使用偶數：
2，4，6，8，10，12，14，16，18，20，22，24，26，28，30…
在火星人的數字系統中，6和10被視為質數，因為它們不能分解成更小的偶數。在這種數字系統中，質數和合數嚴格地交替出現。4的所有倍數都是合數（因為4k = 2×2k），其他的所有偶數（包括6、10、14、18等）都是質數，因為它們無法分解成兩個更小的偶數。但是，我們來看180這個數字：
6×30 = 180 = 10×18
在火星人的數字系統中，180有兩種不同的質因數分解結果，這證明火星數字系統中的質因數分解不具有唯一性。
1~100中有25個質數，101~200中有21個質數，210~300中有16個質數。隨著數字越來越大，質數出現的頻率越來越低。（但是，這種減少的趨勢無法預測。例如，在301~400和401~500中，分別有16和17個質數，而1 000 001~1 000 100中只有6個質數。）這是有道理的，因為大數有多個約數的可能性更大。
我們可以證明，有時候連續100個數字之中也沒有一個質數。如果願意花時間尋找，你甚至可以發現連續1 000或者100萬個數字中也沒有一個質數。你不相信的話，我可以立刻為你提供連續99個合數（儘管在這之前就已經出現過同類現象了）。觀察下面這99個連續數字。
100! + 2，100! + 3，100! + 4，…，100! + 100
因為100! = 100×99×98×…×3×2×1，所以它肯定可以被2~100的所有數字整除。接下來，我們以100! + 53為例。由於53是100!的約數，因此它肯定也是100! + 53的約數。同理可證，對於所有的2 ≤ k ≤ 100，100! + k都必然是k的倍數，也就是說，它們都是合數。
延伸閱讀
注意，我們在上述證明過程中根本沒有提到100! + 1是不是質數的問題，但我們其實是可以做出判斷的。在這裡，我們要應用一個非常棒的定理——「威爾遜定理」（Wilson』s theorem）。這條定理指出，當且僅當 (n－1)! + 1是n的倍數時，n為質數。用幾個比較小的數字加以檢驗，就會發現確實如此。1! + 1 = 2是2的倍數，2! + 1 = 3是3的倍數，3! + 1 = 7不是4的倍數，4! + 1 = 25是5的倍數，5! + 1 = 121不是6的倍數，6! + 1 = 721是7的倍數，等等。由於101是質數，根據威爾遜定理，100! + 1是101的倍數，因此它是合數。也就是說，從100!至100! + 100的101個連續數字都是合數。
既然隨著數字越來越大，質數的出現頻率越來越低，人們自然會想，當數字大到一定程度時，會不會就沒有質數了呢？兩千多年前，歐幾里得告訴我們並非如此。但不能因為他是歐幾里得我們就相信他的話，我們還是盡情享受證明的樂趣吧。
定理：質數有無窮多個。
證明：我們反過來假設質數的個數是有限的。既然質數的個數有限，就必然存在最大的質數，我們將這個數字記作P。現在，觀察P! + 1這個數字。由於從2到P的所有數字都可以整除P!，因此它們都不可能整除P! + 1。這樣一來，P! + 1就必然有一個大於P的約數為質數，而我們假設P是最大的質數，兩者是矛盾的！ □
儘管我們永遠也無法找到一個最大的質數，但這並不能阻止數學家和計算機科學家尋找更大質數的努力。在我創作本書的時候，已知的最大質數有17 425 170位數。把這個數字寫下來，可以寫成大約100本跟本書大小、厚度差不多的書。不過，我們也可以把它表示為：
257 885 161– 1
我們之所以能把它以如此簡單的形式表達出來，是因為我們可以準確地判斷出2n – 1或2n + 1是不是質數。
延伸閱讀
根據偉大的數學家皮埃爾·德·費馬（Pierre de Fermat）的證明，如果p是奇質數，那麼2p – 1 – 1必然是p的倍數。我們用前幾個奇質數來驗證一下。取質數3、5、7、11，我們發現： 22 – 1 = 3是3的倍數，24 – 1 = 15是5的倍數，26 – 1 = 63是7的倍數，210–1 = 1 023是11的倍數。對於合數，我們知道，如果n是偶數，那麼2n–1–1必然是奇數，不可能是n的倍數。我們再用前幾個奇合數9、15和21驗證一下，結果發現：28 – 1 = 255不是9的倍數，214 – 1 = 16 383不是15的倍數，220–1 = 1 048 575不是21的倍數（就連3的倍數都不是）。根據費馬的這條定理，如果知道2N–1 – 1不是數字N的倍數，那麼我們甚至不需要找出N的約數，就可以根據這個屬性確定N不是質數！但是，這條定理反過來卻不成立。確實有些合數從某些方面來看像質數（這類數字被稱為「偽質數」）。最小的偽質數是341 = 11×31，它就具備2340 – 1是341的倍數這個屬性。偽質數有無窮多個，儘管它們出現的頻率比較低，但好在我們已經找到了甄別辦法。
質數有很多應用，尤其在計算機科學領域。在幾乎所有加密算法（包括為互聯網金融交易保駕護航的公鑰加密系統）中，質數都發揮了核心作用。很多加密算法都利用了這樣一個事實：我們可以很快地判斷出某個數字是否為質數，但我們還沒有找到快速分解大數字的方法。例如，如果我隨機選取兩個1 000位的質數相乘，答案是一個2 000位數，任何人、任何計算機（除非量子計算機被人們成功地製造出來）幾乎都不可能根據這個乘積找出原來的兩個質數。人們認為，基於人類無法分解大數字這個特點編製而成的密碼（例如公鑰加密系統）具有很高的安全性。
幾千年來，質數之美一直讓人類魂牽夢繞。古希臘人說，如果某個數字等於所有真約數（除自身以外的約數）之和，這個數字就是「完全數」（perfect number）。例如，6的真約數是1、2、3，它們的和正好是6，因此6是一個完全數。第二個完全數是28，它的真約數1、2、4、7、14的和正好是28。接下來的兩個完全數是496和8 128。完全數有什麼規律呢？不妨考察它們的質因數分解結果。
6 = 2×3
28 = 4×7
496 = 16×31
8 128 = 64×127
看出其中的規律了嗎？被乘數是2的冪次方，乘數是比被乘數的2倍小1的質數。（因此，在上述算式中我們沒有看到8×15或者32×63，因為15和63都不是質數。）我們可以用下面這條定理對這個規律加以概括。
定理：如果2n–1是質數，那麼2n–1×(2n–1)是完全數。
延伸閱讀
證明：令p = 2n–1，p是質數，我們的目標是證明2n–1p是完全數。2n–1p的真約數有哪些呢？不含p的約數只有1，2，4，8，…，2n–1，它們的和為2n – 1 = p。其他約數（不包括2n–1p）則都包含p，這些約數的和為 p(1 + 2 + 4 + 8 + … + 2n–2) = p (2n–1 – 1)。因此，所有真約數的和為:
p + p(2n–1 – 1) = p〔1 + (2n–1 – 1)〕 = 2n–1p
證明完畢。 □
偉大的數學家萊昂哈德·歐拉（Leonhard Euler，1707—1783）證明了所有完全數都是偶數。在我創作本書的時候，人們已經發現了48個完全數，而且全部是偶數。是否存在完全奇數呢？目前，還沒有人知道這個問題的答案。有人認為，如果完全奇數真的存在，它們的位數將超過300。不過，還沒有人證明完全奇數肯定不存在。
關於質數，有很多表述簡單但卻懸而未決的問題。前面已經說過，關於斐波那契數列中的質數是否有無窮多個的問題，現在還沒有答案。〔已經有人證明斐波那契數列中只有兩個完全平方數（1和144）和兩個完全立方數（1和8）。〕還有一個未解難題被稱為「哥德巴赫猜想」（Goldbach』s conjecture），即所有大於2的偶數都是兩個質數之和。目前沒有人可以證明這個猜想，但是有人證明，如果有反例存在，那麼這個數字至少是19位數。〔不久前，人們在一個比較相似的問題上取得了突破。2013年，法國數學家哈羅德·賀夫高特（Harald Helfgott）證明了所有大於7的奇數都至多是三個奇質數之和。〕最後再介紹一個未解難題。我們把差為2的兩個質數定義為「孿生質數」（twin primes）。排在前面的幾對孿生質數分別是3和5，5和7，11和13，17和19，29和31，等等。你知道為什麼3、5、7是唯一的「質數三胞胎」嗎？儘管已經有人證明末位數是1（或者3、7、9）的質數有無窮多個〔古斯塔夫·狄利克雷（Gustav Dirichlet）提出的一個命題的特例〕，但孿生質數是否有無窮多對的問題仍未找到答案。
在結束本章之前，我們來看一個有點兒可疑的證明，但是我希望大家能相信這個命題。
命題：所有正整數都值得關注！
證明：人們一致認為前幾個正整數值得關注。例如，1是第一個正整數，2是第一個偶數，3是第一個奇數，4是唯一一個名副其實的數字（它的英文單詞「FOUR」正好有4個字母）。我們反過來假設有的正整數不值得關注，那麼必然有第一個不值得關注的正整數，我們把它記作N。但是，作為第一個不值得關注的正整數，N必然因此引起關注！因此，不值得我們關注的正整數是不存在的！