## Wednesday, September 6, 2006

### 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.]