OIM 2009 Problem 5

Consider the sequence $\{a_n\}_{n\geq1}$ defined as follows: $a_1 = 1$ , $a_{2k} = 1 + a_k$ and $a_{2k + 1} = \frac {1}{a_{2k}}$ for every $k\geq 1$ . Prove that every positive rational number appears on the sequence $\{a_n\}$ exactly once.