2009 OIM Problems/Problem 5

Problem

The sequence $a_n$ is defined by $a_1 = 1, a_{2k} = 1 + a_k$ , and $a_{2k+1} = \frac{1}{a_{2k}}$ , for all integer $k \ge 1$ . Prove that every positive rational number appears exactly once in this sequence.

~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Solution

We can prove the statement by strong induction. Define an $n$ -fraction to be a fraction with a denominator of $n$ . Clearly all $n$ -fractions are positive as both functions map positives to positives. Furthermore, let $A$ denote the function $x\rightarrow x+1$ and $B$ the function $x\rightarrow \frac{1}{x}$ . This represents the two recursions given, and the only limitation given is that we cannot apply $B$ twice in a row.

For our base case, clearly all $1$ -fractions (the set of naturals) are able to be generated by repeatedly applying $A$ . Then assume that all $i$ -fractions can be generated for all $i\le k$ such that $k$ is a given positive integer. We prove that all $k+1$ -fractions can also be generated.

Notice that both given functions $A$ and $B$ are one-to-one (bijections over the positive rationals) and thus denote $A’$ and $B’$ as the inverse functions of $A$ and $B$ . If we apply $A’$ or $B’$ to a given fraction, then we can simply apply $A$ or $B$ to the resultant fraction to generate the given fraction again. As a result, we consider some fraction $\frac{m}{k+1}$ for $m$ a positive integer. Repeatedly apply $A’$ a finite number of times $z$ until the fraction is no greater than one and still positive. This new fraction is $\frac{m-z(k+1)}{k+1}$ ; let $p=m-z(k+1)$ , so the fraction is $\frac{p}{k+1}$ ; clearly $p$ is a positive integer. In the case $p=k+1$ , the fraction is simply equal to $1$ , which is already generated; thus we consider $0<p<k$ .

Now we apply $B’$ to this fraction, resulting in $\frac{k+1}{p}$ . However, notice that $p<k+1$ indicates that this new fraction is a $p$ -fraction, which can be generated. As a result, all $k+1$ -fractions can be generated, completing the inductive step and proving the claim.

Finally, we prove that each positive rational appears exactly once in the sequence. Notice that after every application of some number of $A$ results in a greater numerator than denominator due to the addition of $1$ . Then an application of $B$ results in a new greater denominator. Notice that $B$ cannot be applied again due to the restriction of even indices; thus applying the functions $A$ and $B$ will never decrease the denominator of a fraction. Therefore, if we consider $A’$ and $B’$ , these functions will never increase the denominator of a fraction. Thus, given a fraction with a greater denominator than numerator, we cannot apply $B’$ ; thus we must apply $A’$ . Similarly, if we are given a fraction with a greater numerator than denominator, we cannot apply $A’$ as we cannot generate negatives; thus we must apply $B’$ . Clearly the case of equal numerator and denominator is already generated due to $a_1=1$ ; thus we have shown that there is a forced sequence of moves $A’$ and $B’$ that changes a given fraction to $a_1=1$ , so the opposite is true as well, proving uniqueness.

~ eevee9406

Page

Toolbox

Search

2009 OIM Problems/Problem 5

Problem

Solution

See also