数列 $\{a_n\}$ 定义如下：$a_1$ 是任意正整数，对整数 $n\geqslant 1$，$a_{n+1}$ 是与 $\displaystyle\sum_{i=1}^na_i$ 互素，且不等于 $a_1,\cdots,a_n$ 的最小整数．
证明：每个正整数均在数列 $\{a_n\}$ 中出现．
证明：每个正整数均在数列 $\{a_n\}$ 中出现．
【难度】
【出处】
2018年全国高中数学联赛（A卷加试试题）
【标注】
【答案】
略
【解析】
显然 $a_1=1$ 或 $a_2=1$．下面考虑整数 $m>1$，设 $m$ 有 $k$ 个不同素因子，我们对 $k$ 归纳证明 $m$ 在 $\{a_n\}$ 中出现．记 $S_n=a_1+\cdots+a_n,n\geqslant 1$．
$k=1$ 时，$m$ 时素数方幂，设 $m=p^a$，其中 $a>0$，$p$ 是素数．假设 $m$ 不在 $\{a_n\}$ 中出现．由于 $\{a_n\}$ 各项互不相同，因此存在正整数 $N$，当 $n\geqslant N$ 时，都有 $a_n>p^a$．若对某个 $n\geqslant N,p\not | S_n$，那么 $p^a$ 与 $S_n$ 互素，又 $a_1,\cdots,a_n$ 中无一项是 $p^a$，故由数列定义知 $a_{n+1}\leqslant p^a$，但是 $a_{n+1}>p^a$，矛盾!
因此对每个 $n\geqslant N$，都有 $p|S_n$，但由 $p|S_{n+1}$ 及 $p|S_n$ 知 $p|a_{n+1}$，从而 $a_{n+1}$ 与 $S_n$ 不互素，这与 $a_{n+1}$ 的定义矛盾．
假设 $k\geqslant 2$，且结论对 $k-1$ 成立．设 $m$ 的标准分解为 $m=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$，假设 $m$ 不在 $\{a_n\}$ 中出现，于是存在正整数 $N^\prime$，当 $n\geqslant N^\prime$ 时，都有 $a_n>m$．取充分大的正整数 $\beta_1,\cdots,\beta_{k-1}$，使得 $M=p_1^{\beta_1}\cdots p_{k-1}^{\beta_{k-1}}>\max\limits_{1\leqslant n\leqslant N^\prime}a_n$．
我们证明，对 $n\geqslant N^\prime$，有 $a_{n+1}\ne M$．对任意 $n\geqslant N^\prime $，若 $S_n$ 与 $p_1p_2\cdots p_k$ 互素，则 $m$ 与 $S_n$ 互素，又 $m$ 在 $a_1,\cdots,a_n$ 中均未出现，而 $a_{n+1}>m$，这与数列的定义矛盾．因此我们推出：对任意 $n\geqslant N^\prime $，$S_n$ 与 $p_1p_2\cdots p_k$ 不互素．（*）
情形一
若存在 $i(1\leqslant i\leqslant k-1)$，使得 $p_i|S_n$，因 $(a_{n+1},S_n)=1$，故 $p_i\not |a_{n+1}$，从而 $a_{n+1}\ne M$（因 $p_i|M$）．
情形二
若对每个 $i(1\leqslant i\leqslant k-1)$，均有 $p_i\not |S_n$，则由（*）知必有 $p_k|S_n$．于是 $p_k\not |a_{n+1}$，进而 $p_k\not |S_n+a_{n+1}$，即 $p_k\not |S_{n+1}$．故由（*）知，存在 $i_0(1\leqslant i_0\leqslant k-1)$，使得 $p_{i_0}|S_{n+1}$，再由 $S_{n+1}=S_n+a_{n+1}$ 及前面的假设 $p_i\not |S_n(1\leqslant i\leqslant k-1)$，可知 $p_{i_0}\not |a_{n+1}$，故 $a_{n+1}\ne M$．
因此对 $n\geqslant N^\prime +1$，均有 $a_n\ne M$，而 $M>\max\limits_{1\leqslant i\leqslant N^\prime}a_n$，故 $M$ 不在 $\{a_n\}$ 中出现，这与归纳假设矛盾．因此，若 $m$ 有 $k$ 个不同素因子，则 $m$ 一定在 $\{a_n\}$ 中出现．由数学归纳法知，所有正整数均在 $\{a_n\}$ 中出现．
$k=1$ 时，$m$ 时素数方幂，设 $m=p^a$，其中 $a>0$，$p$ 是素数．假设 $m$ 不在 $\{a_n\}$ 中出现．由于 $\{a_n\}$ 各项互不相同，因此存在正整数 $N$，当 $n\geqslant N$ 时，都有 $a_n>p^a$．若对某个 $n\geqslant N,p\not | S_n$，那么 $p^a$ 与 $S_n$ 互素，又 $a_1,\cdots,a_n$ 中无一项是 $p^a$，故由数列定义知 $a_{n+1}\leqslant p^a$，但是 $a_{n+1}>p^a$，矛盾!
因此对每个 $n\geqslant N$，都有 $p|S_n$，但由 $p|S_{n+1}$ 及 $p|S_n$ 知 $p|a_{n+1}$，从而 $a_{n+1}$ 与 $S_n$ 不互素，这与 $a_{n+1}$ 的定义矛盾．
假设 $k\geqslant 2$，且结论对 $k-1$ 成立．设 $m$ 的标准分解为 $m=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$，假设 $m$ 不在 $\{a_n\}$ 中出现，于是存在正整数 $N^\prime$，当 $n\geqslant N^\prime$ 时，都有 $a_n>m$．取充分大的正整数 $\beta_1,\cdots,\beta_{k-1}$，使得 $M=p_1^{\beta_1}\cdots p_{k-1}^{\beta_{k-1}}>\max\limits_{1\leqslant n\leqslant N^\prime}a_n$．
我们证明，对 $n\geqslant N^\prime$，有 $a_{n+1}\ne M$．对任意 $n\geqslant N^\prime $，若 $S_n$ 与 $p_1p_2\cdots p_k$ 互素，则 $m$ 与 $S_n$ 互素，又 $m$ 在 $a_1,\cdots,a_n$ 中均未出现，而 $a_{n+1}>m$，这与数列的定义矛盾．因此我们推出：对任意 $n\geqslant N^\prime $，$S_n$ 与 $p_1p_2\cdots p_k$ 不互素．（*）
情形一
若存在 $i(1\leqslant i\leqslant k-1)$，使得 $p_i|S_n$，因 $(a_{n+1},S_n)=1$，故 $p_i\not |a_{n+1}$，从而 $a_{n+1}\ne M$（因 $p_i|M$）．
情形二
若对每个 $i(1\leqslant i\leqslant k-1)$，均有 $p_i\not |S_n$，则由（*）知必有 $p_k|S_n$．于是 $p_k\not |a_{n+1}$，进而 $p_k\not |S_n+a_{n+1}$，即 $p_k\not |S_{n+1}$．故由（*）知，存在 $i_0(1\leqslant i_0\leqslant k-1)$，使得 $p_{i_0}|S_{n+1}$，再由 $S_{n+1}=S_n+a_{n+1}$ 及前面的假设 $p_i\not |S_n(1\leqslant i\leqslant k-1)$，可知 $p_{i_0}\not |a_{n+1}$，故 $a_{n+1}\ne M$．
因此对 $n\geqslant N^\prime +1$，均有 $a_n\ne M$，而 $M>\max\limits_{1\leqslant i\leqslant N^\prime}a_n$，故 $M$ 不在 $\{a_n\}$ 中出现，这与归纳假设矛盾．因此，若 $m$ 有 $k$ 个不同素因子，则 $m$ 一定在 $\{a_n\}$ 中出现．由数学归纳法知，所有正整数均在 $\{a_n\}$ 中出现．
答案
解析
备注
