我们再回过头去，证明与正整数相关的一些定理。在本书第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时定理也成立，那么：
在等式两边同时加上，就会得到：
证明完毕。 □
