1700996732
12堂魔力数学课 [:1700993738]
1700996733
12堂魔力数学课 棋盘覆盖问题与归纳性证明
1700996734
1700996735
我们再回过头去，证明与正整数相关的一些定理。在本书第1章，通过观察：
1700996736
1700996737
1700996738
1700996739
1700996740
我们先提出前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取所有值时命题都成立。归纳性证明就像爬梯子：先证明你可以踏上梯子，然后证明如果你已经爬上了一级，就可以再向上爬一级。稍稍思考其中的道理，你就会相信自己可以爬上梯子的任意一级。
1700996741
1700996742
例如，对于前n个奇数的和这个命题，我们的目标是证明对于所有的n≥1，都有：
1700996743
1700996744
1 + 3 + 5 + … + (2n– 1) =n2
1700996745
1700996746
我们发现，第一个奇数1的和的确是12，因此当n= 1时，这个命题肯定是正确的。接下来，我们注意到，如果前k个奇数的和是k2，即：
1700996747
1700996748
1 + 3 + 5 + … + (2k– 1) =k2
1700996749
1700996750
再加上下一个奇数（2k+ 1），就有：
1700996751
1700996752
1 + 3 + 5 + … + (2k– 1) + (2k+ 1) =k2+ (2k+ 1)
1700996753
1700996754
= (k+ 1)2
1700996755
1700996756
也就是说，如果前k个奇数的和是k2，那么前k+ 1个奇数的和一定是(k+ 1)2。既然n= 1时命题成立，由上述证明过程可知，n取所有值时该命题也成立。
1700996757
1700996758
归纳性证明法是一个功能强大的证明方法。本书讨论的第一个问题是前n个数字的和：
1700996759
1700996760
1700996761
1 + 2 + 3 + … +n=
1700996762
1700996763
当n= 1时，该命题肯定是正确的，因为1 = （1×2） / 2。如果我们假设对于某个数字k，命题
1700996764
1700996765
1700996766
1 + 2 + 3 + … +k=
1700996767
1700996768
是正确的，在上式基础上再加上 (k+ 1)，就会得到：
1700996769
1700996770
1700996771
1 + 2 + 3 + … +k+ (k+ 1) =+ (k+ 1)
1700996772
1700996773
1700996774
= (k+ 1) (+ 1)
1700996775
1700996776
1700996777
=
1700996778
1700996779
这是用k+ 1代替n时的求和公式。因此，如果n=k（k是任意正数）时公式成立，那么当n=k+ 1时，该公式同样成立。由此可证，当n取所有正值时，公式都成立。
1700996780
1700996781
在本章以及后续章节中，我们将见到更多的归纳性证明实例。为了帮助大家加深印象，我在这里为大家送上“数学音乐家”戴恩·坎普（Dane Camp）和拉里·莱塞（Larry Lesser）创作的一首歌，这首歌采用了美国民谣歌手鲍勃·迪伦（Bob Dylan）的作品《答案在风中飘荡》（Blowing in the Wind）的旋律。