12th Balkan 1995 Problem 1 Define a n by a 3 = (2 + 3)/(1 + 6), a n = (a n-1 + n)/(1 + n a n-1 ). Find a 1995 . Solution
: 1991009/1991011. We calculate that the first few terms are 5/7, 11/9, 7/8, 11/10, 27/29, 37/35, 22/23, 28/27. The even terms are all just over 1 and the odd terms are all just under 1, so this suggests we look separately at the even and odd terms. The terms all seem to have numerator and denominator differing by 1 or 2. This suggests multiplying both by 2 where necessary so that the difference is always 2. Looking then at the even term denominators we get 9, 20, 35, 54. The differences are 11, 15, 19 which go up by 4 each time. The same is true for the odd term denominators, which are 7, 16, 29, 46, differences 9, 13, 17. Assuming this is indeed the pattern we get the formulae a 2n = (2n 2 + n + 1)/(2n 2 + n - 1), a 2n+1 = (2n 2 + 3n)/(2n 2 + 3n + 2). We prove this by induction. It is true for n = 1. Suppose it is true for n. Then we have f(2n+2) = ( (2n 2 + 3n) + (2n+2)(2n 2 + 3n + 2) )/( (2n 2 + 3n + 2) + (2n+2)(2n 2 + 3n) ) = (4n 3 + 12n 2 + 13n + 4)/(4n 3 + 12n 2 + 9n + 2) = (2n 2 + 5n + 4)(2n + 1)/( 2n 2 + 5n + 2)(2n + 1) ) = (2(n+1) 2 + (n+1) + 1)/(2(n+1) 2 + (n+1) - 1). Similarly f(2n+3) = (2n 2 + 5n + 4 + (2n + 3)(2n 2 + 5n + 2) )/(2n 2 + 5n + 2 + (2n+3)(2n 2 + 5n + 4) ) = (2n 2 + 7n + 5)/(2n 2 + 7n + 7) = (2(n+1) 2 + 3(n+1) )/(2(n+1) 2 + 3(n+1) + 2). Hence the result is true for n+1. Applying it to 1995 = 2.997+1 we get the answer. 12th Balkan 1995 © John Scholes jscholes@kalva.demon.co.uk 11 Apr 2002