IMO shortlist 1983/7 solution

24th IMO 1983 shortlist

Problem 7

Let N be a positive integer. Define the sequence a₀, a₁, a₂, ... by a₀ = 0, a_n+1 = N(a_n + 1) + (N + 1)a_n + 2( N(N+1)a_n(a_n+1) )^1/2. Show that all terms are positive integers.

Solution

Solution by Demetres Christofides

Induction on n. Note first that √a_n+1 = (√(N+1) √a_n + √N √(a_n+1) and √(a_n+1+1) = √N √a_n + √(N+1) √(a_n+1). So √N √(N+1) √a_n+1 √(a_n+1+1) = N(N+1)(a_n+a_n+1) + (2N+1) √N √(N+1) √a_n √(a_n+1) (*).

If a_n and a_n+1 are integers it follows from the definition that √N √(N+1) √a_n √(a_n+1) is an integer, and hence (*) implies that √N √(N+1) √a_n+1 √(a_n+1+1) is an integer. Hence a_n+2 is an integer. But it is easy to check that a₀ = 0 and a₁ = N are integers, so a_n is an integer for all n.

24th IMO shortlist 1983