Proving that if a sequence of integers satisfies $0<a_{k+1}-a_k<r$, then it contains arbitrarily long arithmetic progressions

Question

If $a_0, a_1, a_2,...$ is an infinite sequence of integers satisfying $0 < a_{k+1} - a_k < r$ for some fixed $r$, then prove that the sequence contains arbitrarily long arithmetic progressions.

This resembles Van der Waerden, but I don't know how to apply the condition.

Answer 1

We will prove the following:

Suppose $A = \{a_i\}_{i = 0}^{\infty}$ is a sequence of non negative integers such that for all $i \ge 1$, $$0 < a_i - a_{i - 1} < r$$ for some positive integer $r$. Then for all positive integers $N$, there exists a subsequence of $A$ that is a $N$ term arithmetic progression.

(The main idea behind this proof is to use $a_i$ to induce a coloring on the integers. Then, we use VDW on the integers and translate back to our sequence.)

Proof: From the definition of our sequence it follows that we can find at least one $a_i$ in each of the intervals of the form $$I_n = [(n - 1) \cdot r + 1, nr].$$

(We can just subtract a constant from each of the $a_i$'s to ensure that $a_0$ is in the first interval. This won't change the proof since we are subtracting the same constant.)

Now construct a new sequence $B = \{b_i \}_{i = 1}^{\infty}$ by letting $b_k$ be one of the terms of $A$ that is in $I_k$. If there are multiple, pick one. Define a partition of the positive integers into the sets $C_1, C_2, \cdots, C_r$ as follows:

Put $i$ in $C_j$ if $b_i \equiv j \pmod r$.

By Van der Waerden, there exist a $j$ such that $C_j$ has as arithmetic progression of length $N$ for all positive integers $N$. Let these integers be $$k, k + d, k + 2d , \cdots, k + (N-1) \cdot d$$ for some $d$. Now we need to check that the corresponding $b_i$'s are also in an arithmetic progression. The term in $B$ that corresponds to $k + nd$ is $(k + n - 1)\cdot r + j$ since that term has to be in the interval $I_{k + nd}$ and has to have a remainder of $j$ mod $r$.

This means that we can find $b_i$'s that are of the form $$(k - 1)\cdot r + j, (k + d - 1)\cdot r + j, \cdots, (k + Nd - 1)\cdot r + j.$$

This is clearly a $N$ term arithmetic progression with difference $d \cdot r$. This completes the proof since our $b_i$s are a subsequence of the $a_i$'s.