打字猴:1.700996939e+09
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
[ 上一页 ]  [ :1.700996939e+09 ]  [ 下一页 ]