## Exercises - Continued Fractions

1.
1. $355/113$
2. $87/32$
3. $10/3$
2. Find a simple continued fraction expansion for the following values:

1. $32/17$
2. $22/7$
3. $\sqrt{3}$

To avoid the possibility of round-off error in a calculator, let us keep exact values throughout our calculation.

First, we separate the integer part of $\sqrt{3}$ from the fractional part:

$$\sqrt{3} = 1 + (\sqrt{3} - 1)$$

Reciprocating the fractional part twice (which doesn't change it's value), and then multiplying by a well-chosen value of one that involves the conjugate of $\sqrt{3}-1$ (again, not changing the overall value, we have

$$= 1 + \frac{1}{\displaystyle{\frac{1}{\sqrt{3}-1} \cdot \frac{\sqrt{3}+1}{\sqrt{3}+1}}}$$

Simplifying the bottom-most product, we arrive at

$$= 1 + \frac{1}{\displaystyle{\frac{\sqrt{3}+1}{2}}}$$

Now we start the process over. We separate the integer part of $\frac{\sqrt{3}+1}{2}$ from its fractional part:

$$= 1 + \frac{1}{\displaystyle{1+\frac{\sqrt{3}-1}{2}}}$$

Then, we reciprocate the fractional part twice and multiply by a well-chosen value of one that involves a conjugate

$$= 1 + \frac{1}{\displaystyle{1+\displaystyle{\frac{1}{\displaystyle{\frac{2}{\sqrt{3}-1} \cdot \frac{\sqrt{3}+1}{\sqrt{3}+1}}}}}}$$

and, like before, we simplify this bottom-most product

$$= 1 + \frac{1}{\displaystyle{1+\displaystyle{\frac{1}{\displaystyle{\sqrt{3}+1}}}}}$$

As we start to do it again, we notice something when we separate the integer part of $\sqrt{3}+1$ from its fractional part...

$$= 1 + \frac{1}{\displaystyle{1+\displaystyle{\frac{1}{\displaystyle{2 + (\sqrt{3}-1)}}}}}$$

The fractional part found is something we have seen already -- it is the same fractional part we discovered for $\sqrt{3}$ at the beginning of this argument! As such, this continued fraction will simply repeat from this point forward. Thus, the simple continued fraction representation for $\sqrt{3}$ is given by

$$\sqrt{3} = [1;\overline{1,2}]$$
4. $\sqrt{33}$
5. $\sqrt{19}$
3. While it doesn't repeat, there is a clear pattern to the simple continued fraction for $e$:

$$e = [2;1,2,1,1,4,1,1,6,1,1,8,1,1,10,1,1,12,1,1,\ldots]$$

Interestingly, proving this pattern continues to hold also establishes the irrationality of $e$, as all rational values have a finite simple continued fraction.

4. There is no apparent pattern to the simple continued fraction representation for $\pi$, as can be seen below:

$$\pi = [3; 7,15,1,292,1,1,1,2,1,3,1,14,2,1,1,2,2,2,2,\ldots]$$

That said, there are some beautiful non-simple continued fraction representations for $\pi$, however:

$$\pi=\textstyle \frac{4}{1+\textstyle \frac{1^2}{2+\textstyle \frac{3^2}{2+\textstyle \frac{5^2}{2+\textstyle \frac{7^2}{2+\textstyle \frac{9^2}{2+\ddots}}}}}} =3+\textstyle \frac{1^2}{6+\textstyle \frac{3^2}{6+\textstyle \frac{5^2}{6+\textstyle \frac{7^2}{6+\textstyle \frac{9^2}{6+\ddots}}}}} =\textstyle \frac{4}{1+\textstyle \frac{1^2}{3+\textstyle \frac{2^2}{5+\textstyle \frac{3^2}{7+\textstyle \frac{4^2}{9+\ddots}}}}}$$

5. Suppose $x$ represents the continued fraction in question.

$$x = 3 + \frac{1}{2 + \displaystyle{\frac{1}{\displaystyle{6 + \frac{1}{\displaystyle{2 + \frac{1}{6 + \cdots}}}}}}}$$

Note, if we let $y$ be the fractional part of $x$ (i.e., everything but the $3$), we can express $x$ in two ways:

$$x = 3 + y \quad \quad \textrm{and} \quad \quad x = 3 + \frac{1}{2 + \displaystyle{\frac{1}{\displaystyle{6 + y}}}}$$

Setting these equal to one another and collapsing/simplifying the fractional expression, we discover

$$y = \frac{6+y}{13+2y}$$

Multiplying both sides by $(13+2y)$ yields a quadratic equation,

$$13y+2y^2 = 6 + y$$

which we may readily solve for $y$:

$$2y^2 + 12y - 6 = 0 \quad \quad \longrightarrow \quad \quad y = -3 \pm 2\sqrt{3}$$

Discarding $y = -3-2\sqrt{3}$, since we know $y$ must be positive, we are left with

$$y = -3 + 2\sqrt{3}$$

Finally, remembering that $x=3+y$, we have

$$[3;\overline{2,6}] = 3 + (-3 + 2\sqrt{3}) = 2\sqrt{3}$$

6. The finite simple continued fractions $[1;2]$, $[1;2,2]$, $[1;2,2,2]$, $[1;2,2,2,2]$, $[1;2,2,2,2,2], \ldots$ are called the convergents of $[1;\overline{2}]$. More generally, the $n^{th}$ convergent for a given continued fraction is found by truncating the original continued fraction sequence to $n$ values.

First, we note that $[1;\overline{2}]$ has a fractional part of

$$y = \frac{1}{2 + \displaystyle{\frac{1}{2 + \displaystyle{\frac{1}{2 + \cdots}}}}}$$

This tells us that

$$y = \frac{1}{2+y}$$

Multiplying by $(2+y)$, we produce a quadratic equation

$$2y+y^2 = 1$$

Putting this in standard form and solving for $y$ with the quadratic formula, we find

$$y^2 + 2y - 1 = 0 \quad \quad \longrightarrow \quad \quad y = -1 \pm \sqrt{2}$$

Note, we can throw away one of the solutions found, as we know $y$ must be positive. Hence,

$$y = -1 + \sqrt{2}$$

This in turn, tells us that $[1;\overline{2}] = 1 + y = 1 + (-1 + \sqrt{2}) = \sqrt{2}$.

Now we turn our attention to the convergents...

Through direct calculation, we find

$$\begin{array}{rcccl} [1;2] &=& 3/2 &=& 1.5\\ [1;2,2] &=& 7/5 &=& 1.4\\ [1;2,2,2] &=& 17/12 &=& 1.41\overline{6}\\ [1;2,2,2,2] &=& 41/29 &=& 1.41379310\cdots\\ [1;2,2,2,2,2] &=& 99/70 &=& 1.41428571\cdots\\ \end{array}$$

We compare these with $\sqrt{2} = 1.41421356\cdots$, and see that the sequence of convergents converges fairly quickly.

Interestingly, rather than evaluate each successive convergent from scratch, we can tighten the calculation process by using each convergent value to find the next convergent value.

Specifically, if $a_n$ is the $n^{th}$ convergent of $[1,\overline{2}]$, then

$$a_{n+1} = \frac{1}{a_n + 1} + 1$$

Do you see where this comes from? Write down the first couple of convergents in full continued fraction form, and look carefully at the denominators. How can you modify one convergent's form to produce the next one?

7. Find the rational numbers, in lowest terms, given by each of the following continued fractions. Do you notice anything interesting? What value would have a simple continued fraction representation with an infinite string of $1$'s (i.e., $[1,\overline{1}]$)? Knowing that the continued fractions given below should better and better approximate $[1,\overline{1}]$, what might one conclude?

1. [1;1]
2. [1;1,1]
3. [1;1,1,1]
4. [1;1,1,1,1]

After calculating the first several convergent values, it shouldn't be hard to see the pattern...

$$\begin{array}{rcl} [1;1] &=& 2\\ [1;1,1] &=& 3/2\\ [1;1,1,1] &=& 5/3\\ [1;1,1,1,1] &=& 8/5\\ [1;1,1,1,1,1] &=& 13/8\\ \vdots \end{array}$$

We are looking at ratios of successive Fibonacci numbers!

Of course, we expect the convergents to get closer and closer in value to $[1,\overline{1}]$, which we can compute in the standard way. $$[1,\overline{1}] = \frac{1+\sqrt{5}}{2}$$

The observant among you might recognize this value as the golden ratio, $\varphi$.

As such, we conclude that the limiting quotient of successive Fibonacci numbers must be the golden ratio. That ties some nice things together, doesn't it!

8. The continued fraction we seek is given by $[1;8,3,2,2,1,14,3,9]$.

Comparing this with the work done in computing the greatest common divisor, we discover that the list of quotients found exactly matches the values seen in the continued fraction.

Careful consideration of the divisions happening in both processes should reveal that this was no coincidence -- it must always happen.