An infinite sequence $a_1, a_2,\ldots$ of positive integers is such that $a_n \geq 2$ and $a_{n+2}$ divides $a_{n+1} + a_n$ for all $n \geq 1$. Prove that there exists a prime which divides infinitely many terms of the sequence.
Problem
Source: Baltic Way 2024, Problem 18
Tags: number theory, number theory proposed, Sequence, Divisors, prime numbers
bin_sherlo
16.11.2024 22:20
Suppose otherwise. There must exist some $T$ where $a_n$ are odd for $n\geq T$ because $2$ doesn't divide infinitely many terms. However for $k\geq T+2$, we have $a_k|a_{k-1}+a_{k-2}$ and $a_k\neq a_{k-1}+a_{k-2}$ since right hand side is even. Thus, for $k\geq T+2$ we get $a_k\leq \frac{a_{k-1}+a_{k-2}}{2}\leq \max\{a_{k-1},a_{k-2}\}$. This yields the sequence is bounded but this contradicts with our initial assumption since there must be a number occuring infinitely many times.$\blacksquare$
megarnie
16.11.2024 22:31
Suppose not. Claim: The sequence is bounded Proof: Suppose otherwise. Since $2$ divides only finitely many terms, we can start the sequence from whenever it is all odds, so assume that $a_i$ is odd for all $i$ (and still unbounded). We have $a_{n+2} \mid a_{n+1} + a_n $, but $a_{n+1} + a_n$ is even and $a_{n+2}$ is odd, so $a_{n+2} \le \frac{a_{n+1} + a_n}{2} \le \max(a_n, a_{n+1})$. But since the sequence is unbounded, there are infinitely many $n$ with $a_{n+2} > \max(a_n, a_{n+1})$, a contradiction. $\square$ Now, there exists some $x$ that occurs infinitely many times in the sequence. Since $x > 1$, taking a prime $p\mid x $ gives a contradiction.