Mathematical Food for Thought

Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.
• Meta

A Bit Familiar. Topic: Algebra/NT. Level: Olympiad. January 8th, 2007

Problem: (2002 Putnam – A5) Define a sequence by , together with the rules and for each integer . Prove that every positive rational appears in the set

.

Solution: Consider the sequence . We know and we want to find a recursion for . We can see that

(1)

(2) .

We will now prove the result by strong induction on the denominator of . We know that for , the term appears, so by applying (1) inductively we know appears for all .

So suppose that all fractions of the form with appear in the set. We wish to show that all fractions with appear. We see that

by (2).

In fact, since we know is in the set for already, we get

by (2).

Hence we have found that are all in the set. But then, by applying (1) inductively on each of the fractions, we know that

is in the set, for and , which easily gives us is in the set for any , but those are all integers, which are covered in the first base case. Hence we have shown that all positive rationals with denominator 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 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?