2016 UMO Problems/Problem 5

Problem

Let $a_0,a_1,a_2,\ldots$ be a sequence of integers (positive, negative, or zero) such that for all nonnegative integers $n$ and $k$, $a_{n+k}^2-(2k + 1)a_{n}a_{n+k} + (k^2 + k)a_n^2 = k^2-k$. Find all possible sequences $(a_n)$.


Solution 1

We can factor the equation as $[a_{n+k}-k\cdot a_n][a_{n+k}-(k + 1)\cdot a_n] = k(k-1)$. Substituting in $k = 1$, we find that either $a_{n+1} = 2a_n$ or $a_{n+1} = a_n$ for all integers $n$. If $p$ is a prime such that $p \vert a_r$, then by repeatedly applying $a_{n+1} = 2a_n$ or $a_{n+1} = a_n$, we find that $p$ divides $a_n$ for all integers $n >= r$. Substituting $k = 2$ and $n = r$ into (1) we notice that the LHS is divisible by $p^2$, and the RHS is equal to $2$; hence $p^2 \vert 2$, which is a contradiction. Thus $a_n$ is never divisible by any prime for any $n$, so $a_n = \pm 1$. In particular, $a_{n+1} = a_n$ for all integers $n$, and $a_n$ is constant either 1 or -1. Substituting either of these sequences into (1) shows that both are valid solutions.

See Also

2016 UMO (ProblemsAnswer KeyResources)
Preceded by
Problem 4
Followed by
Problem 6
1 2 3 4 5 6
All UMO Problems and Solutions