60th Putnam 1999

------
 
 
Problem A6

u1 = 1, u2 = 2, u3 = 24, un = (6 un-12un-3 - 8 un-1un-22)/(un-2un-3). Show that un is always a multiple of n.

 

Solution

Put vn = un/un-1. Then the relation simplifies to: vn = 6vn-1 - 8vn-2. This has general solution: vn = A 2n + B 4n. But v2 = u2/u1 = 2, v3 = u3/u2 = 12, so vn+1 = 4n - 2n. Hence un = (4n-1 - 2n-1)(4n-2 - 2n-2) ... (4 - 2).

For any prime p, we have 4p-1 = 2p-1 = 1 (mod p), so p divides 4p-1 - 2p-1 and also 4s - 2s for s a multiple of p - 1. But if pr divides n, then there are at least r multiples of (p - 1) less than n, so pr divides un. Hence n divides un.

 


 

60th Putnam 1999

© John Scholes
jscholes@kalva.demon.co.uk
14 Dec 1999