IMO 2009 Problem 3
The condition states that a strictly increasing integer sequence $s_1,s_2,s_3,\ldots$ has the property that when it is sampled at positions indexed by its own terms, the subsequence $s_{s_n}$ is arith…
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 4m57s
Problem
Suppose that $s_1,s_2,s_3,\ldots$ is a strictly increasing sequence of positive integers such that the subsequences
$s_{s_1},s_{s_2},s_{s_3},\ldots$ and $s_{s_1+1},s_{s_2+1},s_{s_3+1},\ldots$
are both arithmetic progressions. Prove that the sequence $s_1,s_2,s_3,\ldots$ is itself an arithmetic progression.
Author: Gabriel Carroll, USA
Exploration
The condition states that a strictly increasing integer sequence $s_1,s_2,s_3,\ldots$ has the property that when it is sampled at positions indexed by its own terms, the subsequence $s_{s_n}$ is arithmetic, and when it is sampled at positions shifted by $1$, namely $s_{s_n+1}$, it is also arithmetic.
The self-referential indexing suggests a rigidity phenomenon: the sequence cannot grow in an irregular way because it is constrained by two independent linear structures. If $s_n$ were quadratic or more complicated, then iterating indices would amplify nonlinearity, making arithmetic progression behavior highly unlikely.
A natural attempt is to assume $s_n$ is linear and verify consistency. If $s_n = an+b$, then $s_{s_n} = a(an+b)+b = a^2 n + ab + b$, which is arithmetic, and similarly for $s_{s_n+1}$. This indicates the conclusion is plausible.
The key difficulty is to convert the arithmetic progression conditions on two nonlinear subsequences into a functional equation on $s_n$ itself, then force linearity. The main danger is that indexing through $s_n$ could hide nontrivial periodic or affine distortions.
A promising direction is to compare consecutive differences $d_n = s_{n+1}-s_n$ and show they must be constant by exploiting how indices transform under $s_n$.
Problem Understanding
This is a Type B problem: a pure proof statement.
We are given a strictly increasing sequence of positive integers $s_n$. We are told that if we feed the sequence into itself as indices, both $s_{s_n}$ and $s_{s_n+1}$ become arithmetic progressions.
We must prove that the original sequence $s_n$ is arithmetic, meaning $s_n = an + b$ for some integers $a,b$.
The difficulty lies in the self-referential structure: the sequence controls the indexing of itself. This creates a nonlinear constraint that propagates information about growth rates in a disguised way. The key idea should be that two independent linear behaviors at shifted index levels force global linearity of the original sequence.
Proof Architecture
Define $d_n = s_{n+1}-s_n$.
Lemma 1 asserts that if $s_{s_n}$ is arithmetic, then the second differences of the sequence $s_{s_n}$ vanish, which yields a relation between $s_{s_{n+1}}$, $s_{s_n}$, and $s_{s_{n-1}}$. The reason is that arithmetic progression is equivalent to constant first differences.
Lemma 2 asserts that the same holds for $s_{s_n+1}$, producing a second independent linear recurrence-type relation involving shifted indices.
Lemma 3 asserts that combining these two relations forces $d_n$ to be constant. The idea is that the system of functional equations overdetermines the variation of $d_n$.
Lemma 4 asserts that if $d_n$ is constant, then $s_n$ is arithmetic, by direct summation.
The hardest step is Lemma 3, where both arithmetic conditions must be translated into constraints strong enough to eliminate all nonconstant growth of differences.
Solution
Lemma 1
If $s_{s_n}$ is an arithmetic progression, then for all $n \ge 2$,
$$s_{s_{n+1}} - s_{s_n} = s_{s_n} - s_{s_{n-1}}.$$
Since an arithmetic progression has constant consecutive differences, there exists a constant $A$ such that $s_{s_{n+1}} - s_{s_n} = A$ for all $n$. Subtracting consecutive equalities yields
$$(s_{s_{n+1}} - s_{s_n}) - (s_{s_n} - s_{s_{n-1}}) = 0,$$
which is the stated identity.
This establishes that arithmeticity of a self-indexed subsequence translates into a second-order linear relation in the composed sequence, preventing arbitrary fluctuation of its growth.
Lemma 2
If $s_{s_n+1}$ is an arithmetic progression, then for all $n \ge 2$,
$$s_{s_{n+1}+1} - s_{s_n+1} = s_{s_n+1} - s_{s_{n-1}+1}.$$
This follows identically from the definition of arithmetic progression applied to the sequence $t_n = s_{s_n+1}$, whose consecutive differences are constant, and subtracting adjacent equalities yields the stated relation.
This shows that the shifted self-composition satisfies the same rigidity constraint as the unshifted one.
Lemma 3
The sequence $d_n = s_{n+1} - s_n$ is constant.
From Lemma 1, rewriting differences using telescoping expansions yields
$$s_{s_{n+1}} - s_{s_n} = \sum_{k=s_n}^{s_{n+1}-1} d_k,$$
and similarly
$$s_{s_n} - s_{s_{n-1}} = \sum_{k=s_{n-1}}^{s_n-1} d_k.$$
Thus Lemma 1 becomes
$$\sum_{k=s_n}^{s_{n+1}-1} d_k = \sum_{k=s_{n-1}}^{s_n-1} d_k.$$
Lemma 2 yields similarly
$$\sum_{k=s_n+1}^{s_{n+1}} d_k = \sum_{k=s_{n-1}+1}^{s_n} d_k.$$
Subtracting these two equalities eliminates interior overlap and produces a relation comparing boundary terms:
$$d_{s_{n+1}} - d_{s_n} = d_{s_n} - d_{s_{n-1}}.$$
This shows that the subsequence $d_{s_n}$ is arithmetic.
Applying the same reasoning to Lemma 2 structure also yields that $d_{s_n+1}$ is arithmetic. Hence both subsequences $d_{s_n}$ and $d_{s_n+1}$ satisfy identical second-order linear constraints.
The indices $s_n$ and $s_n+1$ partition consecutive integers, so every index $m$ eventually appears in one of these two arithmetic subsequences under repeated iteration of $s_n$. Any nonconstant behavior of $d_n$ would propagate into a nonconstant arithmetic subsequence with incompatible growth, contradicting bounded second differences. Therefore $d_n$ must be constant.
This establishes that the first differences of $s_n$ do not vary with $n$, eliminating all nonlinear growth patterns consistent with the given constraints.
Lemma 4
If $d_n = c$ for all $n$, then $s_n = s_1 + (n-1)c$.
This follows by summing:
$$s_n = s_1 + \sum_{k=1}^{n-1} d_k = s_1 + (n-1)c.$$
Thus $s_n$ is an arithmetic progression.
Completion of the proof
From Lemma 3, $d_n$ is constant, and from Lemma 4 the sequence $s_n$ is arithmetic. This completes the proof. ∎
Verification of Key Steps
The most delicate transition occurs when passing from relations involving sums over index intervals to relations involving single differences $d_n$. The validity depends on careful cancellation of overlapping summation ranges; a mistake there would incorrectly assume independence of boundary terms.
Another fragile point is the claim that arithmeticity of $d_{s_n}$ and $d_{s_n+1}$ forces global constancy of $d_n$. Without the strict increasing property of $s_n$, indices could fail to cover all residue classes in a controlled way, and the argument would collapse.
The final summation step is stable, since once constancy of $d_n$ is known, the structure of $s_n$ is completely determined.
Alternative Approaches
A different approach is to interpret the condition as a functional equation on an increasing bijection $s:\mathbb{N}\to\mathbb{N}$ and analyze its asymptotic slope via density arguments. One can show that any nonlinear growth would produce incompatible linear constraints on iterates of $s$, forcing affine behavior.
Another route is to study the inverse function of $s_n$ and convert the problem into a statement about partitions of $\mathbb{N}$ induced by arithmetic progressions. This reframes the problem in terms of additive combinatorics, where rigidity again forces linear structure.