Putnam 1999 A6

The sequence $(a_n)_{n \ge 1}$ is defined by $a_1 = 1$, $a_2 = 2$, $a_3 = 24$, and, for $n \ge 4$, \[ a_n = \frac{6a_{n-1}^2 a_{n-3} - 8 a_{n-1} a_{n-2}^2}{a_{n-2}a_{n-3}} . \] Show that, for all $n$, $a_n$ is an integer multiple of $n$.

Two parts to this problem: find a closed-form formula for $a_n$, and then show that $n$ divides $a_n$. It's not immediately clear that we'll be able to find a closed-form formula, and there might be a way to do the problem without it, but trying to find one will give us some insight even if we fail.

If we simplify the equality above, we get $a_n = \frac{6a_{n-1}^2}{a_{n-2}} - \frac{8a_{n-1} a_{n-2}}{a_{n-3}}$. Hm, what if we divide everything by $a_{n-1}$? That gives \[ \frac{a_n}{a_{n-1}} = 6 \frac{a_{n-1}}{a_{n-2}} - 8 \frac{a_{n-2}}{a_{n-3}}. \] Ah, that looks less complicated. In fact this is a recurrence relation on a related sequence, $b_n = \frac{a_n}{a_{n-1}}$. We've got $b_2 = 2$, $b_3 = 12$, and $b_n = 6 b_{n-1} - 8 b_{n-2}$ for $n \ge 4$.

Now here's where you have to know a little bit of elementary stuff about recurrence relations. I think this is useful enough that it should get its own post. I'll write one after this problem using this particular recurrence as an example. Let's skip to the solution for now: $b_n = 4^{n-1} - 2^{n-1} = 2^{n-1}(2^{n-1}-1)$. And since $a_n$ is the product of all the $b_k$ from $2$ up to $n$, we get \[ a_n = 2^{n(n-1)/2} (2^{n-1}-1)(2^{n-2}-1)(\cdots)(2^2-1). \] On to part two: we just need to show that $n$ divides this gigantic integer. Not so hard here, although we need a nice fact from number theory. First let's write $n = 2^k m$, where $m$ is odd (that is, separate out the $2$'s from the prime factorization of $n$). We can also assume that $n \ge 3$ because it's clear that $1$ divides $a_1$ and $2$ divides $a_2$. Now clearly $k < n(n-1)/2$ for $n \ge 3$ (since for instance $k < n$), so $2^k$ divides the giant product. So we just need to show that $m$ divides it as well. This boils down to showing that $m$ divides $2^k-1$ for some $k < n$; and now a nice elementary number theory fact comes to the rescue, namely Euler's theorem (or Fermat's generalized little theorem, or whatever you like to call it): \[ m| (a^{\varphi(m)} -1) \, \text{for all $a$ relatively prime to $m$,} \] where $\varphi(m)$ is Euler's $\varphi$ function, equal to the number of positive integers less than $m$ relatively prime to $m$. (When $m$ is prime, $\varphi(m) = m-1$, and we get what is generally called Fermat's little theorem.)

Anyway, $\varphi(m)$ is certainly less than $m$, which is $\le n$, and we can take $a=2$ which is relatively prime to $m$, so $m$ divides one of the factors in the giant product and we're done.

Usually A6 is the hardest problem on the first side, but this one was a paper tiger (A5 turned out to be the killer in 1999). We won't be doing many A6's or B6's, so we can savor the moment.

Top 205 scores:
(31,11,9),(1,5,148)