22nd IMO 1981 shortlist Problem 3 A sequence a n is defined as follows, a 0 = 1, a n+1 = (1 + 4a n + √(1 + 24a n ))/16 for n ≥ 0. Find an explicit formula for a n .
(1/3)(1 + 1/2 n )(1 + 1/2 n+1 ) Solution Put b n = 2 2n+1 a n . Then the relation becomes b n+1 = 2 2n-1 + b n + 2 n √(2 2n-2 + 3b n ). Put c n = √(2 2n-2 + 3b n ) and this becomes c n+1 2 = c n 2 + 3·2 n c n + 9·2 2n-2 = (c n + 3·2 n-1 ) 2 . Hence c n+1 = c n + 3·2 n-1 . Iterating, c n+1 = 3·2 n-1 + 3·2 n-2 + ... + 3·2 0 + c 1 = 3(2 n -1) + c 1 = 3·2 n + 1 (we have a 1 = 5/8, so b 1 = 5, c 1 = 4). Hence b n = (2 2n+1 + 3·2 n + 1)/3, a n = 1/3 + 1/2 n+1 + 1/(3·2 2n+1 ) = (1/3)(1 + 1/2 n )(1 + 1/2 n+1 ). Thanks to Suat Namli 24th IMO shortlist 1983 © John Scholes jscholes@kalva.demon.co.uk 12 February 2004 Last corrected/updated 12 Feb 04