数学归纳法的又一妙用

题: 对于 的每一个非空子集,定义一个唯一确定的交替和: 对每个子集按照递减的次序重新排列,然后从最大的数开始交替地减或加后继的数(例如, 的交替和是 的交替和是 ). 则交替和的总和为? (用 表示)

初看时,知对任意一个元素,所有包含该元素的集合的个数为 而 n 是最大的,始终以「加」的形式在交替和中出现。

因此,仅仅考虑 在交替和的和中的部分,是 .

其余部分呢?有正有负,不好判断。

手动计算了当 时交替和的和的值,分别为 然而,它们刚好与 相等。

便猜想答案是 (「其余部分」精妙地抵消成为


证明:

记交替和的和为

时,结论显然成立

假设当 时,结论成立

则有

时,考虑 有以下划分:

部分的交替和的和即

部分的交替和的和即

下面讨论最后一部分的交替和的和

由于 是所有这些集合中的最大数,因此在交替和中必为正,加入到 中的原有集合中后,原有元素在交替和中正负皆改变,故第三部分的交替和的和为

综上,所有交替和的和的和,即

即当 时,结论成立,即