Problem: (Math Olympiad Treasures - 1.7.8) The sequence $ (x_n)_{n \ge 1} $ is defined by $ x_1 = 1 $, $ x_{2n} = 1+x_n $, and $ x_{2n+1} = \frac{1}{x_{2n}} $ for all $ n \ge 1 $. Prove that for any positive rational number $ r $ there exists a unique $ n $ such that $ r = x_n $.
Solution: Let $ r = \frac{p}{q} $. We will proceed by strong induction on $ q $. First note that $ x_{2n} > 1 $ and $ x_{2n+1} < 1 $ for $ n \ge 1 $.
Base Case: $ q = 1 $. Clearly all integers appear in the sequence uniquely because $ 1 $ does, so $ x_2 = 2, x_4 = 3, \ldots $ and their reciprocals can only appear as $ x_k $ when $ k $ is odd (by the comment above) so we will never have $ x_{2n+1} = \frac{1}{x_k} $ because $ k \neq 2n $.
Induction Step: So suppose $ r = \frac{p}{q} $. If $ p > q $, then repeatedly subtract $ q $ from $ p $ until $ p < q $. We can see that if $ \frac{p}{q} $ appears in the sequence we have $ \frac{p+kq}{q} $ in the sequence (from adding $ 1 $ repeatedly).
The only way that $ \frac{p}{q} $ can appear is if $ \frac{q}{p} $ appears. But since $ p < q $, our inductive hypothesis says that $ \frac{q}{p} $ is in the sequence already, so $ \frac{p}{q} $ must appear. And we know $ \frac{q}{p} $ only appears once (inductive hypothesis), so $ \frac{p}{q} $ can only appear once as well, completing the induction.
So we know that every positive rational number appears only once in the sequence, as desired. QED.
--------------------
Comment: This is a really cool sequence which generates the rational numbers and also provides a way of counting them. In actuality, a proof would need to be much more rigorous, but the details would be boring and not help in showing the insight required for this problem.
--------------------
Practice Problem: (Math Olympiad Treasures - 1.7.5) Let $ n $ be a positive integer. Prove that the number
$ 2^{2^n}-1 $
has at least $ n $ distinct prime divisors.
No comments:
Post a Comment