## Monday, January 8, 2007

### A Bit Familiar. Topic: Algebra/NT. Level: Olympiad.

Problem: (2002 Putnam - A5) Define a sequence by $a_0 = 1$, together with the rules $a_{2n+1} = a_n$ and $a_{2n+2} = a_n+a_{n+1}$ for each integer $n \ge 0$. Prove that every positive rational appears in the set

$\left\{\frac{a_{n-1}}{a_n}: n \ge 1 \right} = \left{\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{2}, \cdots \right\}$.

Solution: Consider the sequence $\displaystyle b_n = \frac{a_{n-1}}{a_n}$. We know $b_1 = 1$ and we want to find a recursion for $b$. We can see that

$\displaystyle b_{2n+1} = \frac{a_{2n}}{a_{2n+1}} = \frac{a_{n-1}+a_n}{a_n} = 1+b_n$ (1)

$\displaystyle b_{2n+2} = \frac{a_{2n+1}}{a_{2n+2}} = \frac{a_n}{a_n+a_{n+1}} = \frac{1}{1+\frac{1}{b_{n+1}}} = 1-\frac{1}{1+b_{n+1}}$ (2) .

We will now prove the result by strong induction on the denominator of $\frac{p}{q}$. We know that for $q = 1$, the term $\frac{1}{1}$ appears, so by applying (1) inductively we know $\frac{p}{1}$ appears for all $p$.

So suppose that all fractions of the form $\frac{p}{q}$ with $q < k$ appear in the set. We wish to show that all fractions $\frac{p}{q}$ with $q = k$ appear. We see that

$\displaystyle \frac{1}{k-1} \rightarrow \frac{1}{k}$ by (2).

In fact, since we know $\frac{m}{k-m}$ is in the set for $0 < m < k$ already, we get

$\displaystyle \frac{m}{k-m} \rightarrow \frac{m}{k}$ by (2).

Hence we have found that $\frac{1}{k}, \frac{2}{k}, \cdots, \frac{k-1}{k}$ are all in the set. But then, by applying (1) inductively on each of the fractions, we know that

$\frac{m}{k}+r = \frac{m+kr}{k}$

is in the set, for $m = 1, 2, \ldots, k-1$ and $r = 1, 2, \ldots$, which easily gives us $\frac{s}{k}$ is in the set for any $s \not\equiv 0 \pmod{k}$, but those are all integers, which are covered in the first base case. Hence we have shown that all positive rationals with denominator $k$ are in the set, completing the induction. QED.

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

Comment: Not too hard for an A5 on the Putnam, especially if you've seen types of problems like this before. The crux step was probably getting the recursions for the $b$ sequence, which then allowed you to discover how the rationals are produced. As noted above, it seemed a bit familiar, and a very similar problem showed up on my blog before and a similar proof was given. This one was a little more complicated, but the main ideas are the same.

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

Practice Problem: Can you modify the sequence in the problem to generate all negative rationals as well?