题目

查看数据源：5c6f5a8b210b280151d74984

若 $\left\{ {{a}_{1}} {{a}_{2}} \cdots {{a}_{n}} \right\}$ 是一个实数集，且 ${{a}_{1}}<{{a}_{2}}<\cdots <{{a}_{n}}$，它的复合乘幂和被定义为
${{a}_{1}}\text{i}+{{a}_{2}}{{\text{i}}^{2}}+{{a}_{3}}{{\text{i}}^{3}}+\cdots +{{a}_{n}}{{\text{i}}^{n}}$，其中 ${{\text{i}}^{2}}=-1$．设 ${{S}_{n}}$ 表示数列 $\left\{ 1 ,2 ,\cdots, n \right\}$ 的所有非空子集的复合乘幂的总和．已知 ${{S}_{8}}=-176-64\text{i}$，${{S}_{9}}=p+q\text{i}$，其中 $p$，$q$ 均为整数，求 $\left| p \right|+\left| q \right|$．

【难度】

【出处】

1998年第16届美国数学邀请赛（AIME）

【标注】

知识点
>
计数与概率
>
排列数与组合数
知识点
>
数列
>
数列极限
知识点
>
计数与概率
>
计数中的常用知识
>
二项式定理

【答案】

368

【解析】

记 $A=\left\{ 1 2 \cdots 9 \right\}$，由题意，$A$ 的所有不包含元素9的非空子集的复合乘幂的总和为 ${{S}_{8}}$；而对于包含元素9的 $A$ 的子集 $B$，设 $\left| B\right|=k+1$，其中 $0\leqslant k\leqslant 8$，此时所有 $A$ 的包含元素9的 $k+1$ 元子集的复合乘幂和为 ${{T}_{k}}+9\cdot{{\text{i}}^{k+1}}\cdot \text{C}_{8}^{k}$，其中 ${{T}_{k}}$ 为 $\left\{ 1,2,\cdots 8 \right\}$ 的所有 $k$ 元子集的复合乘幂和，于是 $A$ 的所有包含元素9的子集的复合乘幂和为
$\displaystyle \sum\limits_{k=0}^{8}{\left({{T}_{k}}+9\cdot {{\text{i}}^{k+1}}\cdot \text{C}_{8}^{k}\right)}={{S}_{8}}+9\text{i}\sum\limits_{k=0}^{8}{{{\text{i}}^{k}}\text{C}_{8}^{k}}={{S}_{8}}+9\text{i}{{\left(1+\text{i} \right)}^{8}}$
$={{S}_{8}}+144\text{i}$．
从而 ${{S}_{9}}=2{{S}_{8}}+144\text{i}=2\left(-176-64\text{i} \right)+144\text{i}=-352+16\text{i}$，故 $\left| p\right|+\left| q \right|=352+16=368$．

答案解析备注

设法用 ${{S}_{n}}$ 与 $n$ 来表示，${{S}_{n+1}}$．$\left\{ 1,2,3,\cdots n+1 \right\}$ 的子集中不含 $n+1$ 的集合恰为 $\left\{ 1,2,3,\cdots n \right\}$ 的子集．这样，它们的复合乘幂的和的总和恰为 ${{S}_{n}}$，包含 $n+1$ 在内的 $\left\{1,2,3,\cdots n+1 \right\}$ 的子集即为 $\left\{ 1,2,3,\cdots n \right\}$ 的所有子集再在每个中添一个最大元素 $n+1$．注意到在这些子集中，仅含有 $n+1$ 这一个元的子集只有一个，$n+1$ 是第二个元在 $n$ 个子集中，一般地，$n+1$ 是第 $k$ 个元在这些子集中的 $\text{C}_{n}^{k-1}$ 个子集中（将子集中元素从小到大排列）．故包含 $n+1$ 在内的 $\left\{ 1,2,3,\cdots n+1 \right\}$ 的子集的复合乘幂和的总和为 ${{S}_{n}}+\text{C}_{n}^{0}\left(n+1 \right)\text{i+C}_{n}^{1}\left( n+1\right){{\text{i}}^{2}}+\text{C}_{n}^{2}\left( n+1 \right){{\text{i}}^{3}}+\cdots+\text{C}_{n}^{n}\left( n+1 \right){{\text{i}}^{n+1}}$ $\displaystyle ={{S}_{n}}+\text{i}\left(n+1\right)\sum\limits_{k=0}^{n}{\text{C}_{n}^{k}{{\text{i}}^{k}}}={{S}_{n}}+\text{i}\left(n+1 \right){{\left( 1+\text{i} \right)}^{n}}$， 故所求递推式为 ${{S}_{n+1}}=2{{S}_{n}}+\text{i}\left(n+1 \right){{\left( 1+\text{i} \right)}^{n}}$．（3） 所以 ${{S}_{9}}=2{{S}_{8}}+9i{{\left(1+\text{i} \right)}^{8}}=-352-128\text{i}+9\text{i}\times 16=-352+16\text{i}$． 故 $\left| p\right|+\left| q \right|=368$． 为了求解递推式（3），可以用累加法． ${{S}_{n}}=2{{S}_{n-1}}+\text{i}n{{\left(1+\text{i} \right)}^{n-1}}$， $2{{S}_{n-1}}=4{{S}_{n-2}}+2\text{i}\left(n-1 \right){{\left( 1+\text{i} \right)}^{n-2}}$， $4{{S}_{n-2}}=8{{S}_{n-3}}+4\text{i}\left(n-2 \right){{\left( 1+\text{i} \right)}^{n-3}}$， …… ${{2}^{n-2}}{{S}_{2}}={{2}^{n-1}}{{S}_{1}}+{{2}^{n-2}}\text{i}2\left(\text{i}+1 \right)$， ${{2}^{n-1}}{{S}_{1}}={{2}^{n-1}}\text{i}$． 将以上各式两边分别相加得 ${{S}_{n}}=\text{i}\left({{2}^{n-1}}+{{2}^{n-2}}2\left( \text{i}+1 \right)+\cdots +n{{\left( 1+\text{i}\right)}^{n-1}} \right)$ $=\text{i}{{2}^{n-1}}\left( 1+2z+3{{z}^{2}}+\cdots+n{{z}^{n-1}} \right)$， 其中 $z=\frac{1}{2}\left(1+\text{i} \right)$，两边同乘以 $1-z$ 得 $\left( 1-z\right){{S}_{n}}=\text{i}{{2}^{n-1}}\left( 1+z+{{z}^{2}}+\cdots+{{z}^{n-1}}-n{{z}^{n}} \right)$ $=\text{i}{{2}^{n-1}}\left( \frac{1-{{z}^{n}}}{1-z}-n{{z}^{n}} \right)$． 两边同乘以 ${{\left( 1-z\right)}^{-1}}=1+\text{i}$ 得 ${{S}_{n}}=\text{i}{{2}^{n-1}}\left[2\text{i}\left[ 1-{{\left( \frac{1+\text{i}}{2} \right)}^{n}} \right]-n\left(1+\text{i} \right){{\left( \frac{1+\text{i}}{2} \right)}^{n}} \right]$ $=\left( n+1+\text{i} \right){{\left(1+\text{i} \right)}^{n-1}}-{{2}^{n}}$． 这里再给出一种组合方法来计算 ${{S}_{n}}$． 观察发现，对于 $1\leqslant k\leqslant n$ 及 $1\leqslant r\leqslant k$，在每一次关于 $1\leqslant {{a}_{1}}<{{a}_{2}}<\cdots \leqslant n\left( {{a}_{r}}=k\right)$ 的选择中，项 $k{{i}^{r}}$ 出现在复合乘幂和总和中．因此 $\displaystyle {{S}_{n}}=\sum\limits_{k=1}^{n}{\sum\limits_{r=1}^{k}{W\left( k , r \right)k{{i}^{r}}}}$，其中 $W\left( k,r \right)$ 是 $\left\{ 1,2 ,\cdots n \right\}$ 的子集 $\left\{ {{a}_{1}} {{a}_{2}} \cdots \right\}$ 的数目，其中第 $r$ 个最小元素是 $k$，注意到 $W\left(k,r \right)=\text{C}_{k-1}^{r-1}{{2}^{n-k}}$，因为有 $\text{C}_{k-1}^{r-1}$ 种方法去选择 $1\leqslant{{a}_{1}}<{{a}_{2}}<\cdots <{{a}_{r}}-1\leqslant k-1$ 且然后有 ${{2}^{n-k}}$ 种方法选择 $\left\{{{a}_{r+1}} {{a}_{r+2}} \cdots \right\}\leqslant \left\{ k+1 \cdots n \right\}$．所以，由二项式定理得 $\displaystyle {{S}_{n}}=\sum\limits_{k=1}^{n}{\sum\limits_{r=1}^{k}{\text{C}_{k-1}^{r-1}{{2}^{n-k}}k{{\text{i}}^{r}}}}$ $\displaystyle =\text{i}{{2}^{n-1}}\sum\limits_{k=1}^{n}{k{{2}^{-\left(k-1 \right)}}\sum\limits_{r=1}^{k}{\text{C}_{r-1}^{r-1}{{\text{i}}^{r-1}}}}$ $\displaystyle =\text{i}{{2}^{n-1}}\sum\limits_{k=1}^{n}{k{{z}^{k-1}}}$， 其中 $z=\frac{1}{2}\left(1+\text{i} \right)$．以下步骤如点评1所述．