NMC 2013 Problem 3

Define a sequence $\left(n_{k}\right)_{k \geq 0}$ by $n_{0}=n_{1}=1$, and $n_{2 k}=n_{k}+n_{k-1}$ and $n_{2 k+1}=n_{k}$ for $k \geq 1$. Let further $q_{k}=n_{k} / n_{k-1}$ for each $k \geq 1$. Show that every positive rational number is present exactly once in the sequence $\left(q_{k}\right)_{k \geq 1}$.