The sequence an of odd positive integers is defined as follows: a1 = r, a2 = s, and an is the greatest odd divisor of an-1 + an-2. Show that, for sufficiently large n, an is constant and find this constant (in terms of r and s).
Solution
This is awkward to get started. Note that if an-1 = an-2, then an-1 + an-2 = 2an-1, whose greatest odd divisor is just an-1, so an = an-1. So once two consecutive terms are constant the following terms are constant.
Both an-1 and an-2 are odd, so an-1 + an-2 is even and hence an ≤ (an-1 + an-2)/2. So if an-1 and an-2 are unequal, then an < max(an-1, an-2). As already noted, if they are equal, then an = max(an-1, an-2).
Put bn = max(an, an-1). If an < an-1, then an+1 < max(an, an-1) = an-1. Also an+2 ≤ max(an+1, an) < an-1. Hence max(an+2, an+1) < max(an, an-1) or bn+2 < bn. If an > an-1, then an+1 < max(an, an-1) = an, and an+2 < max(an+1, an) = an. Hence bn+2 < bn. Thus if an and an-1 are unequal, then bn+2 < bn. But obviously an > 0 for all n, and so bn > 0 for all n. Also it is integral, and b1 = max(r, s), so we can only have b2n+1 < b2n-1 for at most max(r, s) values of n. Hence for some n we must have an = an-1 and then an is constant from that point on.
We show that the constant is the greatest common divisor of r and s. Use parentheses to denote the greatest common divisor, so the greatest common divisor of r and s is (r, s). We have (an-1, an-2) = (an-1, an-1 + an-2) = (an, an-1). So if an is constant for n ≥ N, we have (r, s) = (a1, a2) = (a2, a3) = ... = (aN, aN+1) = aN. We claim that an = d for n > 3. Clearly d divides r + s and hence d divides a3. But d divides a2 = s, so d also divides a2 + a3 and hence d divides a4. Now suppose some odd k divides r + s, but does not divide s. So k divides a3, but not a2. Hence it does not divide a4.
© John Scholes
jscholes@kalva.demon.co.uk
23 Aug 2002