Example 33 (2001 China National Team Training Selection Contest for IMO) For given positive integers does not divide and a given sequence of positive integers , satisfying for all positive integers that . Does there always exist a sequence of positive integers such that for all positive integers , , and for all positive integers (which can be the same), ?
Problem 1031
Official solution
The answer is affirmative. We prove it by inductive construction.
Take as a positive integer such that (for example, if , take ). Assume that have been chosen such that
. Consider
Assume (I) contains a term from , and (II) contains a term from . Since
2 a_{k}+2 b0$. By the inductive hypothesis, $a_{i}-a_{j}=c a+d b, c, d$ are non-negative integers.
Thus, $c a+d b=b-a$.
Therefore, $d=0, b=(c+1) a$, which contradicts the fact that $a$ does not divide $b$.
Case $2 \quad b_{u}=2 a_{k}+2 a$.
In this case, $a_{k}-a_{j}=b-2 a$. By $1 \leqslant j \leqslant k$ and the inductive hypothesis, $a_{k}-a_{j}=c^{\prime} a+d^{\prime} b, c^{\prime}, d^{\prime}$ are non-negative integers.
Thus, $c^{\prime} a+d^{\prime} b=b-2 a$.
Therefore, $d^{\prime}=0, b=\left(c^{\prime}+1\right) a$, which is a contradiction.
Hence, (I) or (II) does not contain any term from $\left\{b_{n}\right\}_{n=1}^{\infty}$.
Therefore, we can take $a_{k+1}=a_{k}+a$ or $a_{k}+b$ such that
a_{k+1}+a_{i} \notin \left\{b^{\prime \prime}\right\}_{n=1}^{\prime \prime}, 1 \leqslant i \leqslant k+1 \text {. }
The proposition is proved.