IMO 1981 SL 9

Origin: FRG

Problem

A sequence (an) is defined by means of the recursion a1 = 1, an+1 = 1 + 4an + \sqrt1 + 24an . Find an explicit formula for an.

Solution

If we put 1 + 24an = b2 n, the given recurrent relation becomes 3b2 n+1 = 3 2 + b2 n 6 + bn = 2 3 2 + bn 2 , i.e., bn+1 = 3 + bn , (1) where b1 = 5. To solve this recurrent equation, we set cn = 2n−1bn. From (1) we obtain cn+1 = cn + 3 \cdot 2n−1 = \cdot \cdot \cdot = c1 + 3(1 + 2 + 22 + \cdot \cdot \cdot + 2n−1) = 5 + 3(2n −1) = 3 \cdot 2n + 2. Therefore bn = 3 + 2−n+2 and consequently an = b2 n −1 = 1  1 + 3 2n + 22n−1  = 1  1 + 2n−1   1 + 1 2n  .