IMO 1988 SL 28

Origin: GBR

Problem

The sequence {an} of integers is defined by a1 = 2, a2 = 7, and −1 2 < an+1 − a2 n an−1 \leq1 2, for n \geq2. Prove that an is odd for all n > 1.

Solution

The sequence is uniquely determined by the conditions, and a1 = 2, a2 = 7, a3 = 25, a4 = 89, a5 = 317, . . .; it satisfies an = 3an−1 + 2an−2 for n = 3, 4, 5. We show that the sequence bn given by b1 = 2, b2 = 7, bn = 3bn−1 + 2bn−2 has the same inequality property, i.e., that bn = an: bn+1bn−1−b2 n = (3bn+2bn−1)bn−1−bn(3bn−1+2bn−2) = −2(bnbn−2−b2 n−1)

for n > 2 gives that bn+1bn−1 −b2 n = (−2)n−2 for all n \geq2. But then bn+1 − b2 n bn−1 = 2n−2 bn−1 < 1 2, since it is easily shown that bn−1 > 2n−1 for all n. It is obvious that an = bn are odd for n > 1.