IMO 1971 SL 9

Origin: POL

Problem

Let Tk = k −1 for k = 1, 2, 3, 4 and T2k−1 = T2k−2 + 2k−2, T2k = T2k−5 + 2k (k \geq3). Show that for all k, 1 + T2n−1 = 7 2n−1 and 1 + T2n = 7 2n−1 , where [x] denotes the greatest integer not exceeding x.

Solution

We use induction. Since T1 = 0, T2 = 1, T3 = 2, T4 = 3, T5 = 5, T6 = 8, the statement is true for n = 1, 2, 3. Suppose that both formulas from the problem hold for some n \geq3. Then T2n+1 = 1 + T2n + 2n−1 = 7 2n−1 + 2n−1

= 7 2n

, T2n+2 = 1 + T2n−3 + 2n+1 = 7 2n−2 + 2n+1

= 7 2n

. Therefore the formulas hold for n + 1, which completes the proof.