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 ﬁnd 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 ﬁnd 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.

2016 UMO (Problems • Answer Key • Resources)
Preceded by Problem 4	Followed by Problem 6
1 • 2 • 3 • 4 • 5 • 6
All UMO Problems and Solutions

Page

Toolbox

Search

2016 UMO Problems/Problem 5

Problem

Solution 1

See Also