# A sequence containing all positive rational numbers.

Question: Consider the following sequence $\{a_n\}_{n=1}^{\infty}$ defined as $a_1=1$ and for $n\ge1$ $a_{2n}=a_{n}+1$ and $a_{2n+1}=\dfrac{1}{a_{2n}}$. Show that the sequence has all positive rational numbers exactly once.

So far: In $a_n$ if $n$ is even $a_n>1$, and if $n>2$ is odd then $a_n<1$. If we can show that all positive rational numbers greater than $1$ are terms of the subsequence $a_{2n}$ we will be done. If $p/q$ is a positive rational in lowest form and $p>q$ then we have to show its a term of the subsequence. How can I do that?

Well I did prove the uniqueness of them, say $a_m=a_n$ and $m\neq n$ for the minimum $m+n$, its easy to see equality will hold if either both $m,n$ are even or both odd, from this we will get a contradiction to minimality assumption of $m,n$.

Please give some hints to proceed from here. If you have alternate solutions do share. What are some other sequences like this which cover the rationals/irrationals?

Thanks a lot!

• Hint: Look up "continued fractions" – Thomas Andrews Oct 15 '16 at 15:29
• Can we do it by induction on the the numerator and denominator? – gambler101 Oct 15 '16 at 17:54

You can do it by induction on the denominator.

I am going to write $f(m)=a_m$, because putting complicated formulae in subscripts is ugly.

First, show that $f(m)>1$ if and only if $m$ is even.

If your rational number is $\frac{p}{1}$ for some integer $p$, then $f(2^p)=p$.

Now, assume it is true for all rationals $\frac{p}{q}$ with $q<Q$. Let $P$ be another positive integer relatively prime to $Q$.

Applying the division algorithm, write $P=Qx+r$ where $x\geq 0$ and $0\leq r<Q$. If $r=0,$ then $Q$ divides $P$, which means they are not relatively prime of unless $Q=1$, which is already covered. So we can assume $0<r<Q$.

Now, by the induction hypothesis, we know that $\frac{Q}{r}=f(m)$ for some $m$, since $0<r<Q$. Since $\frac{Q}{r}>1$, we have that $m=2n$ for some $m$.

The last step, which I'll let you fill in, is to show that:

$$f(2^x(m+1))=\frac{P}{Q}$$

• Thanks I did induction on both numerator and denominator simultaneously. Anyways can you refer me some resources to learn continued fractions, sorry for off-topic question. – gambler101 Oct 17 '16 at 2:45

Hint: Indeed, use continued fractions and also the binary expansion of the index.

Take a positive rational number. Consider its continued fraction. Use pebbles (zeroes) for the partial quotients and reverse the fraction bars into ones. Reverse the sequence of zeroes and ones thus obtained and prepend a one. You got the binary expansion of the index of the term that equals that number

• I dont know continued fractions,can you give a reference for learning it. thanks for the reply. – gambler101 Oct 15 '16 at 17:53