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
不过，最简单的证明方法可能是单纯的代数运算，这让我们不禁回想起把循环小数表示成分数形式的那个方法。
1700996972
1700996973
代数证明：
1700996974
1700996975
令S= 1 + 2 + 4 + 8 + … + 2n–1
1700996976
1700996977
两边同时乘以2，就会得到：
1700996978
1700996979
2S= 2 + 4 + 8 + … + 2n–1+ 2n
1700996980
1700996981
用第二个等式减去第一个等式，除了第一个等式的第一项和第二个等式的最后一项外，其余各项都被消掉了，因此：
1700996982
1700996983
S= 2S–S= 2n– 1 □
1700996984
1700996985
我们刚刚证明的定理其实是二进制表示方法的关键内容。二进制表示方法非常重要，计算机就是利用它来存储和处理数字的。二进制表示方法的理论依据是，所有数字都可以表示成2的不同次幂相加的唯一形式。例如：
1700996986
1700996987
83 = 64 + 16 + 2 + 1
1700996988