数学归纳法的又一妙用

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

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

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

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

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

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


证明:

记交替和的和为

时,结论显然成立。

假设当 时,结论成立。

则有

时,考虑 ,有以下划分:

部分的交替和的和即

部分的交替和的和即

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

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

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

即当 时,结论成立,即