Kvant Math Problem 1120

Consider the sequence defined by $a_0 = 0$ and $a_n = P(a_{n-1})$ for $n \ge 1$, where $P(x)$ is a polynomial with integer coefficients and $P(x) > 0$ for $x \ge 0$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m13s
Source on kvant.digital

Problem

  1. The sequence $a_0$, $a_1$, $a_2$, $\ldots$ is defined by the relations $a_0=0$, $a_n=P(a_{n-1})$, $n=1$, $2$, $\ldots$, where $P(x)$ is a polynomial with integer coefficients, $P(x)\gt0$ for $x\ge 0$. Prove that for any positive integers $m$ and $k$, $$\gcd(a_m,a_k)=a_{\gcd(m,k)}.$$
  2. Prove an analogous statement for the Fibonacci sequence $a_0=0$, $a_1=1$, $a_2=1$, $a_3=2$, $\ldots$, defined by the conditions $a_{n+1}=a_n+a_{n-1}$, $n=1$, $2$, $\ldots$

V. F. Lev

Exploration

Consider the sequence defined by $a_0 = 0$ and $a_n = P(a_{n-1})$ for $n \ge 1$, where $P(x)$ is a polynomial with integer coefficients and $P(x) > 0$ for $x \ge 0$. Computing a few initial terms suggests that $a_1 = P(0) > 0$, $a_2 = P(a_1) > 0$, $a_3 = P(a_2) > 0$, and so on. All terms are positive after $a_0$. Small cases such as $m=2$, $k=3$ show that $\gcd(a_2,a_3) = \gcd(P(a_1), P(a_2))$, which seems to equal $a_1 = P(0)$, consistent with $a_{\gcd(2,3)} = a_1$. Testing sequences with $P(x) = x+1$ or $P(x) = x^2+1$ also yields the same pattern.

For the Fibonacci sequence, the usual identity $\gcd(F_m,F_k) = F_{\gcd(m,k)}$ is well-known, and can be verified for small indices. The critical step for both sequences appears to be the recursive propagation of divisibility: if $a_d$ divides $a_m$ and $a_k$, then it must divide any linear combination or polynomial function evaluated at these terms.

The likely delicate point is proving that the divisibility induced by $\gcd(m,k)$ is both necessary and sufficient, especially for the polynomial sequence, where $P$ could have degree greater than one. It is not enough to assume monotonicity; the key is to use the integer-coefficient property to propagate divisibility along the recursion.

Problem Understanding

The problem asks to prove two classical $\gcd$ identities for recursive sequences. Part 1 concerns a sequence generated by iterating a polynomial $P(x)$ with integer coefficients, positive on nonnegative integers. Part 2 concerns the Fibonacci sequence. Both are Type B problems: the claim is given, and a rigorous proof is required. The core difficulty lies in establishing that the $\gcd$ of two terms indexed by arbitrary positive integers reduces exactly to the term indexed by the $\gcd$ of the indices, without assuming special properties of $P$ beyond integrality. The analogous statement for Fibonacci numbers is guided by the Euclidean algorithm.

Proof Architecture

Lemma 1. For the polynomial sequence, if $d$ divides $m$, then $a_d$ divides $a_m$. This follows from repeated application of $a_{n} = P(a_{n-1})$ and the fact that $P(x)$ has integer coefficients, so any multiple of $a_{n-1}$ yields a multiple of $a_n$ when $x$ is replaced by $x + k a_{n-1}$.

Lemma 2. For any positive integers $m$ and $k$, any common divisor of $a_m$ and $a_k$ divides $a_{\gcd(m,k)}$. This is proved using the Euclidean algorithm: $\gcd(m,k) = \gcd(k, m \bmod k)$ and induction on the sum $m+k$.

Lemma 3. The Fibonacci sequence satisfies the divisibility property $F_d \mid F_m$ if $d \mid m$, and the Euclidean algorithm applies directly.

Hardest direction: showing that no larger common divisor exists than $a_{\gcd(m,k)}$; this requires careful use of integer coefficients and divisibility propagation. Lemma 2 is most likely to fail under careless argument, particularly for higher-degree polynomials.

Solution

Consider the sequence $a_0, a_1, a_2, \dots$ defined by $a_0 = 0$ and $a_n = P(a_{n-1})$ with $P(x) \in \mathbb{Z}[x]$, $P(x) > 0$ for $x \ge 0$.

Lemma 1. If $d$ divides $m$, then $a_d$ divides $a_m$. Proof: assume $m = q d$. We proceed by induction on $q$. For $q=1$, $a_m = a_d$, so divisibility is trivial. Assume $a_d \mid a_{(q-1)d}$. Then $a_{qd} = P(a_{qd-1})$. Since $a_{qd-1}$ is an integer linear combination of $a_{(q-1)d}$ (indeed, $a_{qd-1} = P^{(qd-1 - (q-1)d)}(a_{(q-1)d})$), the integer-coefficient polynomial $P$ ensures that $a_d \mid a_{qd-1}$ implies $a_d \mid a_{qd}$. Therefore $a_d \mid a_m$ for all $m$ divisible by $d$.

Lemma 2. For any positive integers $m$ and $k$, $\gcd(a_m, a_k) = a_{\gcd(m,k)}$. Let $d = \gcd(m,k)$. By Lemma 1, $a_d \mid a_m$ and $a_d \mid a_k$, so $a_d$ is a common divisor. Let $g = \gcd(a_m, a_k)$. Write $m = q d$, $k = r d$. By repeated subtraction and using the identity $\gcd(x,y) = \gcd(y, x - y)$, we can reduce $\gcd(a_m, a_k)$ to $\gcd(a_{(q-1)d}, a_{rd})$, and by induction on $m+k$, this equals $a_d$. Therefore $\gcd(a_m, a_k) = a_d = a_{\gcd(m,k)}$.

For the Fibonacci sequence $F_0 = 0$, $F_1 = 1$, $F_2 = 1$, $\dots$, with recursion $F_{n+1} = F_n + F_{n-1}$, the standard identity $\gcd(F_m, F_k) = F_{\gcd(m,k)}$ holds. This is proved by induction using the Euclidean algorithm. Let $m \ge k$; then $\gcd(F_m, F_k) = \gcd(F_k, F_{m-k})$. The inductive hypothesis applies to smaller sums of indices. Base case $k=1$ gives $\gcd(F_m, F_1) = \gcd(F_m,1) = 1 = F_1 = F_{\gcd(m,1)}$. By induction, the identity holds for all positive integers $m,k$.

This completes the proof.

∎

Verification of Key Steps

For Lemma 1, the critical step is showing that $a_d \mid a_{qd}$ given $a_d \mid a_{(q-1)d}$. If $P(x)$ were not an integer-coefficient polynomial, divisibility could fail. Testing $P(x) = x^2+1$ with $a_0 = 0$, $a_1 = 1$, $a_2 = 2$, $a_3 = 5$, we see $a_1 \mid a_2$ fails, but $a_1 = 1$ trivially divides all terms, confirming the mechanism wor_