数学归纳法的又一妙用

题: 对于 \({1,2,3,...,n}\) 的每一个非空子集,定义一个唯一确定的交替和: 对每个子集按照递减的次序重新排列,然后从最大的数开始交替地减或加后继的数(例如,\({1,2,4,6,9}\) 的交替和是 \(9-6+4-2+1=6;\) \({5}\) 的交替和是 \(5\)). 则交替和的总和为______. (用 \(n\) 表示)

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

因此,仅仅考虑 \(n\) 在交替和的和中的部分,是 \(n\times 2^{n-1}\).

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

手动计算了当 \(n=1, n=2, n=3\) 时交替和的和的值,分别为 \(1,4,12.\) 然而,它们刚好与 \(n\times 2^{n-1}\) 相等。

便猜想答案是 \(n\times 2^{n-1}.\) (「其余部分」精妙地抵消成为 \(0\)


证明:

\[A_n=\\{ 1,2,3,...,n \\}, B_n=\\{ X\mid X\subset A_n, X\neq \varnothing \\}\]

记交替和的和为 \(S_n\)

\(n=1\) 时,结论显然成立

假设当 \(n=k\) 时,结论成立

则有

\[S_k=k\times 2^{k-1}\]

\(n=k+1\) 时,考虑 \(B_{k+1},\) 有以下划分:

\[\\{ B_k, \\{\\{k+1\\}\\}, \\{X\cup \\{k+1\\} \mid X\in B_k\\} \\}\]

\(B_k\) 部分的交替和的和即 \(S_k=k\times 2^{k-1}\)

\(\\{\\{k+1\\}\\}\) 部分的交替和的和即 \(k+1\)

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

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

\[(2^k-1)(k+1)-k\times 2^{k-1}\]

综上,所有交替和的和的和,即 \(S_{k+1}=(k+1)\times 2^k\)

即当 \(n=k+1\) 时,结论成立,即

\[\forall n \in N_+, S_n=n \times 2^{n-1} \; \Box\]