16th ASU 1982 Problem 2 The sequence a n is defined by a 1 = 1, a 2 = 2, a n+2 = a n+1 + a n . The sequence b n is defined by b 1 = 2, b 2 = 1, b n+2 = b n+1 + b n . How many integers belong to both sequences?
1,2,3 only Solution The first few terms are: n 1 2 3 4 5 6 7 a n 1 2 3 5 8 13 21 b n 2 1 3 4 7 11 18 Note that for n = 4, 5 we have a n-1 < b n < a n . So by a trivial induction, the inequality holds for all n ≥ 4. Thanks to Suat Namli 16th ASU 1982 © John Scholes jscholes@kalva.demon.co.uk 16 March 2004 Last corrected/updated 16 Mar 04