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
1700996989
在把十进制转化成二进制时，每个2的幂次方用数字1表示，缺位的幂次方用数字0表示。在这个例子中，83 = (1×64) + (0×32) + (1×16) + (0×8) + (0×4) + (1×2) + (1×1)。因此，83的二进制表示就是：
1700996990
1700996991
83 = (1010011)2
1700996992
1700996993
我们怎么知道所有正数都可以这样表示呢？假设从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。］我们可以将这个过程推而广之，从而证明所有的正数都有唯一的二进制表示。
1700996994
1700996995
1700996996
1700996997