The integers r, s are non-zero and k is a positive real. The sequence an is defined by a1 = r, a2 = s, an+2 = (an+12 + k)/an. Show that all terms of the sequence are integers iff (r2 + s2 + k)/(rs) is an integer.
Solution
Many thanks to Nizameddin Ordulu & Ali Adalý for the second half of this (if the terms are integral, then t is integral). They make it look easy, but I wasted a lot of time failing to do it.
Let t = (r2 + s2 + k)/(rs). We show by induction that an+2 = t an+1 - an. We have a3 = (s2 + k)/r = st - r = t a2 - a1, so the result is true for n = 1. Suppose it is true for n - 1. Then an+2 = (an+12 + k)/an = an+1(t an - an-1)/an + k/an = t an+1 - an+1an-1/an + k/an = t an+1 - (an2 + k)/an + k/an = t an+1 - an. So the result is true for n. We are given that r and s are integers. So if t is also an integer, then a trivial induction shows that all an are integers.
Now suppose that all the an are integers but that t is not. So t = u/v with u and v > 1 relatively prime. Since a3 = u/v a2 - a1 and the ai are integral, v must divide a2. A simple induction shows that vn must divide an+1. Now take N sufficiently large that vN > k. Then k = aN+2aN - aN+12. But the rhs is divisible by vN and the lhs is not. Contradiction. So t must be an integer.
© John Scholes
jscholes@kalva.demon.co.uk
11 Apr 2002