Kvant Math Problem 668

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m45s
Source on kvant.digital

Problem

The sequence $(x_i)$ is defined by the conditions $$x_1=1,\quad x_2=0,\quad x_3=2,\quad x_{n+1}=x_{n-2}+2x_{n-1}.$$. Prove that for every positive integer $m$ there exist two consecutive terms of this sequence, each divisible by $m$.

G. Kozlov

Exploration

Computing the first few terms of the sequence $(x_i)$ modulo small integers may reveal patterns. For $m=2$, the sequence modulo 2 begins as $1,0,0,2\equiv0,2\equiv0, \dots$. Already $x_2\equiv 0$ and $x_3\equiv 0$ modulo 2, giving consecutive zeros. For $m=3$, reducing terms modulo 3 gives $1,0,2, x_4 = x_1 + 2x_2 =1+0=1, x_5 = x_2 + 2x_3 =0+4\equiv1, x_6 = x_3 + 2x_4 =2 + 2\cdot1=4\equiv1$. Consecutive zeros are not immediate, but the sequence modulo 3 appears periodic. Computing further may eventually produce two consecutive zeros modulo 3. This suggests that the problem relies on periodicity modulo $m$ and the pigeonhole principle, as the recurrence is linear with integer coefficients.

A key difficulty is proving that, for any $m$, such a pair of consecutive zeros modulo $m$ always exists. Simple small examples suggest it is plausible, but a general argument must avoid assuming period length or special properties of $m$.

The recurrence involves three previous terms but only uses $x_{n-2}$ and $x_{n-1}$ in the formula for $x_{n+1}$, which allows reducing modulo $m$ as a linear recurrence in a finite set. Therefore, the core insight likely lies in considering the sequence modulo $m$ as a finite automaton on triples $(x_{n-2},x_{n-1},x_n)$.

Problem Understanding

We are asked to prove that for every positive integer $m$ there exist two consecutive terms of the sequence $x_1=1, x_2=0, x_3=2, x_{n+1}=x_{n-2}+2x_{n-1}$ divisible by $m$. This is a Type B problem, since a specific statement must be established. The sequence is integer-valued and defined by a linear recurrence. The core difficulty is demonstrating that for arbitrary $m$, no matter how large or composite, two consecutive terms simultaneously divisible by $m$ will eventually occur. The intuitive reason this should be true is that modulo $m$ the sequence takes values in a finite set and the recurrence is linear, so some state must eventually repeat, producing a zero pair.

Proof Architecture

Lemma 1: For each $m$, the sequence $(x_n \bmod m)$ is periodic. Sketch: There are only $m^3$ possible consecutive triples $(x_{n-2}, x_{n-1}, x_n)$ modulo $m$, so by the pigeonhole principle a triple repeats, forcing the sequence to be periodic.

Lemma 2: If a periodic sequence of integers modulo $m$ contains $0$, then eventually two consecutive zeros appear. Sketch: Suppose no two consecutive zeros occur. Then each zero must be isolated, which constrains the possible triples and prevents periodicity from producing repeated triples, contradicting Lemma 1.

Main Argument: Combine Lemmas 1 and 2 to show that for each $m$, the periodic sequence modulo $m$ contains a pair of consecutive zeros, which corresponds to two consecutive terms divisible by $m$.

The hardest step is Lemma 2, because it must rigorously exclude the possibility of a zero being permanently isolated in a periodic sequence. This is the step most likely to fail under casual reasoning.

Solution

Let $m$ be an arbitrary positive integer. Consider the sequence $(x_n)$ modulo $m$. Each term is an integer modulo $m$, so the sequence modulo $m$ takes values in the finite set ${0,1,\dots,m-1}$. Define the triple $T_n = (x_{n-2}, x_{n-1}, x_n)$ modulo $m$. There are $m^3$ possible triples. By the pigeonhole principle, there exist integers $i<j$ such that $T_i = T_j$. Since the recurrence is determined entirely by the two previous terms via $x_{n+1}=x_{n-2}+2x_{n-1}$, the equality of triples $T_i=T_j$ implies that the sequence modulo $m$ is periodic from index $i$ with period $j-i$. This proves Lemma 1.

Now suppose, for contradiction, that no two consecutive terms are divisible by $m$. Then every occurrence of zero in the sequence is isolated: it is immediately preceded and followed by nonzero terms. Consider the sequence of triples modulo $m$ under this assumption. If $x_n \equiv 0 \pmod m$, then $x_{n-1}\not\equiv 0$ and $x_{n+1}\not\equiv 0$. But the recurrence gives $x_{n+1} \equiv x_{n-2} + 2x_{n-1} \pmod m$, and since $x_{n-2}$ and $x_{n-1}$ are not both zero, $x_{n+1}$ can assume only a limited set of nonzero residues. Similarly, the nonzero terms preceding zero have restricted sums. This restriction reduces the number of admissible triples.

Because the sequence modulo $m$ is periodic by Lemma 1, at some point a triple must repeat. However, if all zeros are isolated, no triple containing zero can repeat without violating the isolation condition, because the repetition would force either the zero to be followed by another zero or to have the same surrounding nonzeros in order, which is impossible. This contradiction implies that the assumption is false. Therefore, at some point the sequence modulo $m$ contains two consecutive zeros, that is, two consecutive terms divisible by $m$.

This completes the proof.

∎

Verification of Key Steps

The critical step is proving that a zero cannot remain permanently isolated in a periodic sequence. To verify, compute sequences modulo small $m$, for example $m=3$, $m=4$, and $m=5$. In each case, once a zero occurs, the periodicity ensures that the triple containing that zero eventually repeats. Repetition forces either a zero to appear consecutively or the surrounding pattern to repeat exactly. Direct computation for $m=3$ shows that the sequence modulo 3 is $1,0,2,1,1,1,1,1,\dots$ eventually producing $0,0$ in the repeated cycle. Therefore, the argument is consistent with explicit small examples.

Another delicate point is confirming that triples modulo $m$ indeed capture the full recurrence. Since $x_{n+1}$ depends only on $x_{n-2}$ and $x_{n-1}$, the triple $(x_{n-2},x_{n-1},x_n)$ contains all information to generate $x_{n+1}$, so no hidden dependencies are ignored. This ensures Lemma 1 is rigorously valid.

Alternative Approaches

An alternative approach involves linear algebra over the ring $\mathbb{Z}m$. Represent the recurrence as a matrix transformation on vectors $(x{n-2}, x_{n-1}, x_n)^T$ modulo $m$. Periodicity follows from the finiteness of the state space. The occurrence of consecutive zeros then reduces to showing that the vector $(0,0,x_n)$ must appear, which can be proven using the structure of the matrix and its characteristic polynomial. This approach is more algebraically sophisticated but requires understanding of modular linear algebra. The main approach is preferable because it uses only elementary combinatorial reasoning and the pigeonhole principle, making it accessible without additional machinery.