IMO 1990 SL 7

Origin: GRE

Problem

Let f(0) = f(1) = 0 and f(n + 2) = 4n+2f(n + 1) −16n+1f(n) + n \cdot 2n2, n = 0, 1, 2, 3, . . .. Show that the numbers f(1989), f(1990), f(1991) are divisible by 13.

Solution

Let f(n) = g(n)2n2 for all n. The recursion then transforms into g(n + 2) −2g(n + 1) + g(n) = n \cdot 16−n−1 for n \inN0. By summing this equation from 0 to n −1, we get g(n + 1) −g(n) = 152 \cdot (1 −(15n + 1)16−n). By summing up again from 0 to n −1 we get g(n) = 153 \cdot (15n −32 + (15n + 2)16−n+1). Hence f(n) = 153 \cdot (15n + 2 + (15n −32)16n−1) \cdot 2(n−2)2.

Now let us look at the values of f(n) modulo 13: f(n) \equiv15n + 2 + (15n −32)16n−1 \equiv2n + 2 + (2n −6)3n−1. We have 33 \equiv1 (mod 13). Plugging in n \equiv1 (mod 13) and n \equiv1 (mod 3) for n = 1990 gives us f(1990) \equiv0 (mod 13). We similarly calculate f(1989) \equiv0 and f(1991) \equiv0 (mod 13).