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