60th Putnam 1999

u₁ = 1, u₂ = 2, u₃ = 24, u_n = (6 u_n-1²u_n-3 - 8 u_n-1u_n-2²)/(u_n-2u_n-3). Show that u_n is always a multiple of n.

Solution

Put v_n = u_n/u_n-1. Then the relation simplifies to: v_n = 6v_n-1 - 8v_n-2. This has general solution: v_n = A 2ⁿ + B 4ⁿ. But v₂ = u₂/u₁ = 2, v₃ = u₃/u₂ = 12, so v_n+1 = 4ⁿ - 2ⁿ. Hence u_n = (4^n-1 - 2^n-1)(4^n-2 - 2^n-2) ... (4 - 2).

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

60th Putnam 1999

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