Putnam 2004, Problem A-3

Define a sequence $\{u_n\}_{n=0}^\infty$ by $u_0 = u_1 = u_2 = 1$, and thereafter by the condition that
\[
\det\begin{pmatrix} u_n & u_{n+1} \\ u_{n+2} & u_{n+3} \end{pmatrix} = n!
\]
for all $n \geq 0$. Show that $u_n$ is an integer for all $n$. (By convention, $0! = 1$.)

Solution:
Define a sequence $v_n$ by $v_n = (n-1)(n-3)\cdots(4)(2)$ if $n$ is odd and $v_n = (n-1)(n-3)\cdots(3)(1)$ if $n$ is even; it suffices to prove that $u_n = v_n$ for all $n \geq 2$. Now $v_{n+3}v_n = (n+2)(n)(n-1)!$ and $v_{n+2}v_{n+1} = (n+1)!$, and so $v_{n+3}v_n - v_{n+2}v_{n+1} = n!$. Since we can check that $u_n = v_n$ for $n = 2,3,4$, and $u_n$ and $v_n$ satisfy the same recurrence, it follows by induction that $u_n = v_n$ for all $n \geq 2$, as desired.