数学归纳法的又一妙用

Author Avatar
Ivan Chen 7月 22, 2018
  • 在其它设备中阅读本文章

题: 对于 ${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$

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

$\because$ $k+1$ 是所有这些集合中的最大数,因此在交替和中必为正,加入到 $B_k$ 中的原有集合中后,原有元素在交替和中正负皆改变

$\therefore$ 第三部分的交替和的和为 $(2^k-1)(k+1)-k\times 2^{k-1}$

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

即当 $n=k+1$ 时,结论成立

$\therefore \forall n \in N_+, S_n=n \times 2^{n-1}$ $\Box$

本文采用知识共享 署名-相同方式共享 4.0 国际许可协议(CC BY-SA 4.0)进行许可。
本文链接: https://idkidknow.com/2018/07/22/数学归纳法的又一妙用/