Problem 3

Continued fractions give an excellent way to approximate numbers by fractions with small denominators.

For example, suppose that we want to approximate the golden mean \(\phi\) which satisfies \(\phi^2=\phi+1\). We can manipulate this formula to write \[ \phi=1+\frac{1}{\phi} \] and then \[ \phi=1+\dfrac{1}{1+\frac{1}{\phi}} \] and then \[ \phi=1+\dfrac{1}{1+\frac{1}{1+\frac{1}{\phi}}} \] We might imagine we could repeat this process infinitely many times to write the infinite continued fraction \[ \phi=1+\dfrac{1}{1+\frac{1}{1+\frac{1}{1\frac{1}{1+\cdots}}}}. \] One way to give meaning to the above infinite continued fraction is to look at the finite approximations. We could write \[ \frac{p_1}{q_1}=1+\frac{1}{1}=2\] \[ \frac{p_2}{q_2}=1+\frac{1}{1+\frac{1}{1}}=\frac{3}{2}\] \[\frac{p_3}{q_3}=1+\frac{1}{1+\frac{1}{1+\frac{1}{1}}}=\frac{5}{3}\] \[\frac{p_4}{q_4}=1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1}}}}=\frac{8}{5}\]

and see that the fractions \(\frac{p_n}{q_n}\) really do converge to \(\phi\). Suppose now that we want to approximate the number \(\alpha=\frac{1+\sqrt{3}}{2}\). We write down an infinite continued fraction \[ \alpha=1+\dfrac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\frac{1}{\cdots}}}} \] where the \(a_i\) are whole numbers \(\geq 1\). Let \(r_n\), \(s_n\) be whole numbers (with no common factors) satisfying \[ \frac{r_n}{s_n}=1+\dfrac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\frac{1}{a_4+\ddots+\frac{1}{a_n}}}}} \] What is \(r_{20}\)?