IMO 1988 SL 1

Origin: BUL

Problem

An integer sequence is deﬁned by an = 2an−1 + an−2 (n > 1), a0 = 0, a1 = 1. Prove that 2k divides an if and only if 2k divides n.

Solution

Assume that p and q are real and b0, b1, b2, . . . is a sequence such that bn = pbn−1 + qbn−2 for all n > 1. From the equalities bn = pbn−1 + qbn−2, bn+1 = pbn + qbn−1, bn+2 = pbn+1 + qbn, eliminating bn+1 and bn−1 we obtain that bn+2 = (p2 +2q)bn −q2bn−2. So the sequence b0, b2, b4, . . . has the property b2n = Pb2n−2 + Qb2n−4, P = p2 + 2q, Q = −q2. (1) We shall solve the problem by induction. The sequence an has p = 2, q = 1, and hence P = 6, Q = −1. Let k = 1. Then a0 = 0, a1 = 1, and an is of the same parity as an−2; i.e., it is even if and only if n is even. Let k \geq1. We assume that for n = 2km, the numbers an are divisible by 2k, but divisible by 2k+1 if and only if m is even. We assume also that the sequence c0, c1, . . . , with cm = am\cdot2k, satisﬁes the condition cn = pcn−1−cn−2, where p \equiv2 (mod 4) (for k = 1 it is true). We shall prove the same statement for k + 1. According to (1), c2n = Pc2n−2 −c2n−4, where P = p2 −2. Obviously P \equiv2 (mod 4). Since P = 4s + 2 for some integer s, and c2n = 2k+1d2n, c0 = 0, c1 \equiv2k (mod 2k+1), and c2 = pc1 \equiv2k+1 (mod 2k+2), we have c2n = (4s + 2)2k+1d2n−2 −c2n−4 \equivc2n−4 (mod 2k+2), i.e., 0 \equivc0 \equivc4 \equivc8 \equiv\cdot \cdot \cdot and 2k+1 \equivc2 \equivc6 \equiv\cdot \cdot \cdot (mod 2k+2), which proves the statement. Second solution. The recursion is solved by an = \sqrt (1 + \sqrt 2)n −(1 − \sqrt 2)n

n

2 n
22 n
\cdot \cdot \cdot . Let n = 2km with m odd; then for p > 0 the summand 2p n 2p + 1 = 2k+pm(n −1) . . . (n −2p) (2p + 1)! = 2k+p m 2p + 1 n −1 2p is divisible by 2k+p, because the denominator 2p + 1 is odd. Hence an = n + p>0 2p n 2p + 1 = 2km + 2k+1N for some integer N, so that an is exactly divisible by 2k. Third solution. It can be proven by induction that a2n = 2an(an +an+1). The required result follows easily, again by induction on k.