31st IMO shortlist 1990/7 solution

31st IMO 1990 shortlist

Problem 7

Define f(0) = 0, f(1) = 0, and f(n+2) = 4ⁿ⁺²f(n+1) - 16ⁿ⁺¹f(n) + n 2^n². Show that f(1989), f(1990) and f(1991) are all divisible by 13.

Solution

Put g(n) = f(n)/2^n². Then we have g(n+2) - 2g(n+1) + g(n) = n 16^-n-1. lhs = (g(n+2) - g(n+1)) - (g(n+1) - g(n)), so summing the relation from 0 to n-1 we get g(n+1) - g(n) = (1 - (15n+1)/16ⁿ)/15². Summing again, we get g(n) = (15n - 32 + (15n+2)16^-n+1)/15³, so f(n) = (15n+2 + (15n-32)16^n-1)2^(n-2)²/15³.

Now we have 15n+2 + (15n-32)16^n-1 = 2n+2 + (2n-6)3^n-1 mod 13 (*). Now 33 = 1 mod 13 and 1989 = 0 mod 3, so 3^1989-1 = 9, 3^1990-1 = 1, 3^1991-1 = 3 mod 13. Also 1989 = 0 mod 13, so (*) becomes 2 - 6·9 = 0 mod 13 for 1989, 4 - 4 = 0 mod 13 for 1990, and 6 - 2·3 = 0 mod 13 for 1991.

Thanks to Mehul Srivastav for this

31st IMO shortlist 1990