How to prove there exist two elements in a positive integer sequence with bounded differences such that one is a multiple of the other?

Solution 1:

The following is taken from $0 < a_{n+1} - a_n \leq 2001$ on AoPS. The actual value ($2001$ or $2013$) for the upper bound of the difference does not matter, I'll use $M$ instead.

Let $(a_n)$ be a sequence of positive integers such that $0 < a_{n+1} - a_n \le M$ for all $n$. Then there are indices $p \ne q$ such that $a_p$ divides $a_q$.

Let $A = \{ a_n \mid n \in \Bbb N \}$ denote the set of all integers in the sequence. The essential observation is that $A$ cannot contain a “hole” of $M$ consecutive numbers:

For every $n \ge \min A$ there is an integer $k(n)$ such that $0 \le k(n) < M$ and $n + k(n) \in A$.

Therefore one can define recursively a sequence $(b_n)$: $$ \begin{align} b_1 &= a_1 \\ b_2 &= a_2 \\ b_3 &= b_1 + b_1b_2 + r_3\\ & \text{where }r_3 = k(b_1+b_1b_2) \\ b_4 &= b_1 + b_1b_2 + b_1b_2b_3+ r_4\\ & \text{where } r_4 = k(b_1+b_1b_2+b_1b_2b_3) \\ b_5 &= b_1 + b_1b_2 + b_1b_2b_3 +b_1b_2b_3b_4+ r_5\\ & \text{where } r_5 = k(b_1+b_1b_2+ b_1b_2b_3+b_1b_2b_3b_4) \\ \ldots \end{align} $$ It follows from the construction that each $b_n \in A$.

From the pigeonhole principle it follows that among the $M+1$ numbers $r_3, r_4, \ldots, r_{3+M}$ there must two equal numbers: $i < j$ with $r_i = r_j$. For these indices we have $$ b_j - b_i = b_1b_2\cdots b_i + b_1b_2\cdots b_{i+1} + \ldots + b_1b_2\cdots b_{j-1} $$ Then $b_i < b_j$ and $b_j$ is divisible by $b_i$. Since both $b_i$ and $b_j$ are in $A$ we have the desired conclusion.