数学归纳法的又一妙用

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

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

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

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

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

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

---

证明:

令

记交替和的和为 。

当 时，结论显然成立。

假设当 时，结论成立。

则有

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

部分的交替和的和即 。

部分的交替和的和即 。

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

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

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

即当 时，结论成立，即