Putnam 2002, Problem A-5

Define a sequence by $a_0 = 1$, together with the rules $a_{2n+1} = a_n$ and $a_{2n+2} = a_n + a_{n+1}$ for each integer $n \geq 0$. Prove that every positive rational number appears in the set $\left\{\frac{a_{n-1}}{a_n} : n \geq 1\right\} = \left\{\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \frac{3}{2}, \ldots\right\}$.

Solution:
It suffices to prove that for any relatively prime positive integers \( r, s \), there exists an integer \( n \) with \( a_n = r \) and \( a_{n+1} = s \). We prove this by induction on \( r + s \), the case \( r + s = 2 \) following from the fact that \( a_0 = a_1 = 1 \). Given \( r \) and \( s \) not both 1 with \( \gcd(r, s) = 1 \), we must have \( r \neq s \). If \( r > s \), then by the induction hypothesis we have \( a_n = r - s \) and \( a_{n+1} = s \) for some \( n \); then \( a_{2n+2} = r \) and \( a_{2n+3} = s \). If \( r < s \), then we have \( a_n = r \) and \( a_{n+1} = s - r \) for some \( n \); then \( a_{2n+1} = r \) and \( a_{2n+2} = s \).  

Note: a related problem is as follows. Starting with the sequence  
\[ \frac{0}{1}, \frac{1}{0}, \]  
repeat the following operation: insert between each pair \( \frac{a}{b} \) and \( \frac{c}{d} \) the pair \( \frac{a+c}{b+d} \). Prove that each positive rational number eventually appears.  

Observe that by induction, if \( \frac{a}{b} \) and \( \frac{c}{d} \) are consecutive terms in the sequence, then \( bc - ad = 1 \). The same holds for consecutive terms of the \( n \)-th Farey sequence, the sequence of rational numbers in \( [0, 1] \) with denominator (in lowest terms) at most \( n \).