## Friday, April 7, 2006

### Every Single One Of Them. Topic: Algebra/Sequences & Series. Level: Olympiad.

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.