1700996922
1700996923
证明：当n= 1时，定理成立，因为任何一个2×2的棋盘都可以用一个三方块和一个1×1方块来覆盖，而且1×1方块可以摆放在棋盘的任何位置上。接下来，假设当n=k时（即棋盘大小为2k×2k时）定理也成立。我们需要完成的任务是证明在棋盘大小为2k+1×2k+1时，该定理仍然成立。如下图所示，将1×1方块摆放在棋盘的任意位置上，然后将棋盘分成四等分。
1700996924
1700996925
1700996926
1700996927
1700996928
用三方块覆盖棋盘
1700996929
1700996930
1700996931
由于放有1×1方块的那一等分的大小为2k×2k，因此，它可以被三方块完全覆盖（根据假设，当n=k时，定理成立）。接下来，我们在棋盘的中心位置放一个三方块，让它与其余三个等分相交。这三个等分的大小分别为2k×2k，且其中有一个1×1方格已经被覆盖了，所以用三方块可以完全覆盖住它们。因此，在棋盘大小为2k+1×2k+1时，定理仍然成立。
1700996932
1700996933
本节最后证明的等式有很多重要应用，我们将用归纳证明法和其他几种不同方法予以证明。这个令人感兴趣的问题是：如果从20= 1开始，将2的前n次方相加，和是多少？下面是排在前几位的2的幂次方：
1700996934
1700996935
1，2，4，8，16，32，64，128，256，512，1 024…
1700996936
1700996937
将它们加到一起，就会得到：
1700996938
1700996939
1700996940
1700996941
1700996942
大家看出其中的规律了吗？所有的和都比2的更高次幂小1。
1700996943
1700996944
定理：对于n≥1，
1700996945
1700996946
1 + 2 + 4 + 8 +… + 2n–1= 2n– 1
1700996947
1700996948
证明：如上所述，当n= 1时（以及n= 2，3，4或5时）定理成立。假设当n=k时定理成立，就有：
1700996949
1700996950
1 + 2 + 4 + 8 +… + 2k–1= 2k–1
1700996951
1700996952
在等式两边同时加上更高一阶的2次幂，即2k，就会得到：
1700996953
1700996954
1 + 2 + 4 + 8 +… + 2k–1+ 2k= (2k– 1) + 2k
1700996955
1700996956
= 2×2k–1
1700996957
1700996958
= 2k+1–1 □
1700996959
1700996960
在第4章和第5章，我们通过运用不同方法回答同一个计数问题，证明了多种相互关系。看了下面的内容，你也许会认为组合性证明法真的非常重要！
1700996961
1700996962
问题：从n名曲棍球球员（球衣号码为1~n）中选择若干名球员加入体育联合会代表团，要求代表团中至少包含1名球员，一共有多少种选择方案？
1700996963
1700996964
第一种解法：每名球员都有参加或者不参加代表团这两个选择，因此选择方案应该是2n种。但所有球员均不参加的情况是不允许的，还需要减去1。所以，一共有2n–1种选择方案。
1700996965
1700996966
第二种解法：考虑参加者的球衣号码最大的情况。如果1是最大号码，选择方案只有1种；如果2是最大号码，选择方案有2种（2号球员可能独自参加，也可能和1号球员一起参加）；3是最大号码时，选择方案有4种（3号球员必须参加，1号和2号球员各有两个选择）。以此类推，n是最大球衣号码时，选择方案有2n–1种，因为n号球员必须参加，1号至n– 1号球员各有两个选择（参加和不参加）。加到一起，一共有1 + 2 + 4 + … + 2n–1种选择方案。
1700996967
1700996968
1700996969
由于这两种解法都是正确的，因此必然会得出相同的答案。也就是说，1 + 2 + 4 + … + 2n–1= 2n– 1。
1700996970
1700996971
不过，最简单的证明方法可能是单纯的代数运算，这让我们不禁回想起把循环小数表示成分数形式的那个方法。