数学归纳法的又一妙用

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

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

因此，仅仅考虑在交替和的和中的部分，是。

其余部分呢？有正有负，不好判断。

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

于是猜想答案是。（「其余部分」精妙地抵消成为了）

证明:

令

记交替和的和为。

当时，结论显然成立。

假设当时，结论成立。

则有

当时，考虑，有以下划分：

部分的交替和的和即。

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

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

综上，所有交替和的和的和，即。

即当时，结论成立，即

数学