21st BMO 1985 Problem 3 Let { x } denote the nearest integer to x, so that x - 1/2 ≤ { x } < x + 1/2. Define the sequence u 1 , u 2 , u 3 , ... by u 1 = 1. u n+1 = u n + { u n √2 }. So, for example, u 2 = 2, u 3 = 5, u 4 = 12. Find the units digit of u 1985 .
9 Solution We find the first few terms are 1, 2, 5, 12, 29, 70, which suggests that u n+2 = 2u n+1 +u n . Induction. True for n = 1. Suppose true for n. Then u n+3 = u n+2 + { u n+2 √2 } = u n+2 + { u n+1 √2 + 2u n+1 } = u n+2 + 2u n+1 + { u n+1 √2 } = u n+2 + u n+1 + u n+1 + { u n+1 √2 } = u n+2 + u n+1 + u n+2 , so it is true for n+1 and hence for all n. Now calculating mod 10 we find the terms are 1, 2, 5, 2, 9, 0, 9, 8, 5, 8, 1, 0, 1, 2, so it is periodic with period 12. Hence u 1985 = u 5 = 9 mod 10. 21st BMO 1985 © John Scholes jscholes@kalva.demon.co.uk 11 February 2004 Last corrected/updated 11 Feb 04