Russian 1999 Problem 10 The sequence a 1 , a 2 , a 3 , ... of positive integers is determined by its first two members and the rule a n+2 = (a n+1 + a n )/gcd(a n , a n+1 ). For which values of a 1 and a 2 is it bounded?
a 1 = a 2 = 2 Solution Put d n = gcd(a n , a n+1 ). Note that d n+1 divides a n+1 and a n+1 and hence also d n a n+2 - a n+1 = a n . So it also divides d n . Hence, in particular, d n ≥ d n+1 . Since all d n are positive integers, we must have d n = d for all n ≥ some N. If d = 1, then a n+2 = a n+1 + a n > a n+1 for any n > N. So a n cannot be bounded. If d ≥ 3, then a n+2  N. Hence a n+2  N. Hence a n+2 - a n+1 = (a n - a n+1 )/2. So if a N ≠ a N+1 , then for sufficiently large n we get an non-integral. Contradiction. So a N = a N+1 . But gcd(a N ,a N+1 ) = 2, so a N = a N+1 = 2. So 2 = (2 + aN-1)/gcd(2,a N-1 ). If gcd(2,a N-1 ) = 1, then a N-1 = 0. Contradiction. So gcd(2,a N-1 ) = 2. Hence a N-1 = 2 gcd(2,a N-1 ) - 2 = 2. Now by a trivial induction all terms are 2. In particular a 1 and a 2 are 2. Russian 1999 © John Scholes jscholes@kalva.demon.co.uk 4 March 2004 Last corrected/updated 4 Mar 04