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?