Determinated! Topic: NT/S&S. Level: Olympiad.

Problem: (2004 Putnam - A3) Define a sequence $ \displaystyle \{u_n\}^{\infty}_{n=0} $ by $ u_0 = u_1 = u_2 = 1 $, and thereafter by the condition that

$ u_n u_{n+3}-u_{n+1}u_{n+2} = n! $

for all $ n \ge 0 $. Show that $ u_n $ is an integer for all $ n $. (By convention, $ 0! = 1 $.) [Reworded: there originally contained a determinant]

Solution: Rewrite the given condition as

$ u_{n+3} = \frac{n!+u_{n+1}u_{n+2}}{u_n} $.

First, let's calculate some terms; we get

$ 1, 1, 1, 2, 3, 8, 15, 48, 105 $.

Now, this is interesting sequence, but we manage to notice that $ u_n u_{n+1} = n! $, or $ u_{n+1} = \frac{n!}{u_n} $. Aha! So we'll prove this by induction. Assuming it is true for $ 1, 2, \ldots, n+2 $ (base case is trivial), we have

$ u_{n+3} = \frac{n!+u_{n+1} u_{n+2}}{u_n} $

and we make the substitutions $ u_{n+1} = \frac{n!}{u_n} $, $ u_{n+2} = (n+1)u_n $, and $ u_n = \frac{u_{n+2}}{n+1} $ (yes the last two are equivalent) to get

$ u_{n+3} = \frac{n!+\frac{n!}{u_n} (n+1) u_n}{\frac{u_{n+2}}{n+1}} = \frac{(n+2)!}{u_{n+2}} $

after a big mess of algebra. So it's true. Let's induct again (assume true for $ 1, 2, \ldots, n+1 $) to show that $ u_{n+2}|(n+2)! $. Remember we had $ u_{n+2} = (n+1)u_n $, but $ u_n|n! $ so $ (n+1)u_n|(n+2)! \Rightarrow u_{n+2}|(n+2)! $ as desired. Hence each $ u_n $ is an integer. QED.

--------------------

Comment: Whew, another way (the official solution) would be to notice that $ u_n = (n-1)(n-3) \cdots (4)(2) $ for odd $ n $ and $ u_n = (n-1)(n-3) \cdots (3)(1) $ for even $ n $ and induct. That seems rather unnatural for people with non-godly observation skills, though.

--------------------

Practice Problem: (2004 Putnam - B2) Let $ m $ and $ n $ be positive integers. Show that

$ \frac{(m+n)!}{(m+n)^{m+n}} < \frac{m!}{m^m} \cdot \frac{n!}{n^n} $.

[Hint: look for a one-line solution.]