IMO 1984 SL 6

Origin: CAN

Problem

Let c be a positive integer. The sequence {fn} is defined as follows: f1 = 1, f2 = c, fn+1 = 2fn −fn−1 + 2 (n \geq2). Show that for each k \inN there exists r \inN such that fkfk+1 = fr.

Solution

From the given recurrence we infer fn+1−fn = fn−fn−1+2. Consequently, fn+1 −fn = (f2 −f1) + 2(n −1) = c −1 + 2(n −1). Summing up for n = 1, 2, . . ., k −1 yields the explicit formula fk = f1 + (k −1)(c −1) + (k −1)(k −2) = k2 + bk −b, where b = c−4. Now we easily obtain fkfk+1 = k4 +2(b+1)k3 +(b2 +b+ 1)k2 −(b2 + b)k −b. We are looking for an r for which the last expression equals fr. Setting r = k2 + pk + q we get by a straightforward calculation that p = b + 1, q = −b, and r = k2 + (b + 1)k −b = fk + k. Hence fkfk+1 = ffk+k for all k.