4th Brazil 1982 Problem 2 Any positive integer n can be written in the form n = 2 b (2c+1). We call 2c+1 the odd part of n. Given an odd integer n > 0, define the sequence a 0 , a 1 , a 2 , ... as follows: a 0 = 2 n -1, a k+1 is the odd part of 3a k +1. Find a n .
(3 n - 1)/2 Solution A simple induction shows that a k = 3 k 2 n-k - 1 for k ≤ n-1. It is certainly true for k = 0. Suppose it is true for k  1, the odd part is 3 k+1 2 n-(k+1) - 1, so the result is true for k+1. That gets us as far as a n-1 = 3 n-1 2 - 1. Now we want the odd part of 2(3 n - 1). Certainly 3 n - 1 is even. We have 3 n - 1 = (-1) n - 1 = 2 mod 4 for n odd, so for n odd it is not divisible by 4. Hence for n odd we have a n = (3 n - 1)/2. 4th Brazil 1982 © John Scholes jscholes@kalva.demon.co.uk 24 Oct 2003 Last corrected/updated 24 Oct 03