The sequence a1, a2, a3, ... is defined by a1 = 0 and a4n = a2n + 1, a4n+1 = a2n - 1, a4n+2 = a2n+1 - 1, a4n+3 = a2n+1 + 1. Find the maximum and minimum values of an for n = 1, 2, ... , 1996 and the values of n at which they are attained. How many terms an for n = 1, 2, ... , 1996 are 0?
Solution
Answer: max 9, min -10, no. terms 346.
Calculating the first few values, we find:
n an 1 0 10 -1 11 1 100 0 101 -2 110 0 111 2 1000 1 1001 -1 1010 -3 1011 -1 1100 1 1101 -1 1110 1 1111 3If the last two digits are 00 or 11, then an is one more than a[n/2]. If the last two digits are 01 or 10, then an is one less than a[n/2]. Note that [n/2] is formed by deleting the last binary digit of n. So an = (number of adjacent pairs 00 and 11) - (number of adjacent pairs 01 and 10). For example, 1100 has pairs 11, 10 and 00, so an = 2 - 1 = 1.
1996 = 11111001100, so the maximum value of an for n ≤ 1996 is at n = 1111111111 = 1023 with value 9. Similarly, the minimum value is at n = 10101010101 with value -10.
If an = 0, then n must have an odd number of binary digits, with the first digit 1. The only 1 digit number is n = 1. The 3 digit numbers (with an = 0) are 110 and 100. The 5 digit numbers are 11101, 11001, 11011, 10111, 10001 and 10011. Consider the 2m+1 digit numbers. Exactly m of the digits after the initial 1 must be such that they are the same as the previous digit. Specifying those digits completely determines the number, so there are (2m)Cm such numbers (where aCb is the binomial coefficient). Thus there are 6C3 7-digit numbers, 8C4 9-digit numbers and 10C5 11-digit numbers. But the 11-digit numbers 11111100000, 11111010100, 11111010110, 11111010010, 11111011010 are greater than 1996. Hence the required number is 1 + 2 + 6 + 20 + 70 + 252 - 5 = 346.
© John Scholes
jscholes@kalva.demon.co.uk
16 Dec 2002