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
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
In fact, since we know is in the set for already, we get
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?
Leave a Reply
You must be logged in to post a comment.