Putnam 1999, Problem A-6

The sequence \((a_n)_{n \geq 1}\) is defined by \(a_1 = 1, a_2 = 2, a_3 = 24\), and, for \(n \geq 4\),
\[
a_n = \frac{6a_{n-1}^2 a_{n-3} - 8a_{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\).

Solution:
Rearranging the given equation yields the much more tractable equation
$$\frac{a_n}{a_{n-1}} = 6\frac{a_{n-1}}{a_{n-2}} - 8\frac{a_{n-2}}{a_{n-3}}.$$

Let $b_n = a_n/a_{n-1}$; with the initial conditions $b_2 = 2, b_3 = 12$, one easily obtains $b_n = 2^{n-1}(2^{n-2} - 1)$, and so
$$a_n = 2^{n(n-1)/2} \prod_{i=1}^{n-1} (2^i - 1).$$

To see that $n$ divides $a_n$, factor $n$ as $2^k m$, with $m$ odd. Then note that $k \leq n \leq n(n-1)/2$, and that there exists $i \leq m-1$ such that $m$ divides $2^i - 1$, namely $i = \phi(m)$ (Euler's totient function: the number of integers in $\{1,\ldots,m\}$ relatively prime to $m$).