> [!quote] > > Continued fraction will not be on the test. This was just something for fun (lecture time: 23 minutes). > [!definition] > > The **Gauss map** $f: (0, 1) \to (1, \infty)$ is defined by $x \mapsto \bracs{1/x}$, where $\bracs{1/x}$ is the *fractional part* of $x$ ($\fl{1/x} + \bracs{1/x} = 1/x$). > [!definition] > > $ > a_0 + \frac{b_1}{a_1 + \frac{b_2}{a_2 + \frac{b_3}{a_3 + \ddots}}} > $ > > Let $x \in (0, 1)$, and take $a_1 = \fl{\frac{1}{x}}$, then $x = \frac{1}{a_1 + \bracs{1/x}} = \frac{1}{1/x}$. We then apply the Gauss map on $\bracs{1/x}$ to obtain $a_2$, $a_3$, and so on, iteratively, to obtain a continued fraction representation of $x$. > > Stopping at the $n$-th iteration yields the $n$-th continued fraction. > [!definition] > > Denote a continued fraction > $ > x = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \ddots}}} > $ > as a [[Sequence|sequence]] $x = (a_1, a_2, \cdots)$. > [!theorem] > > If $x \in (0, 1)$ is [[Rational Numbers|rational]], then this process ends in a finite number of steps. If $x$ is [[Irrational Numbers|irrational]], then this process is infinite. > [!theorem] > > $ > \phi = \frac{1 + \sqrt{5}}{2} = (1, 1, 1, \cdots) > $ > > *Proof*. $\phi$ satisfies $\phi = \frac{1}{1 + \phi}$, which is equivalent to the equation $x^2 + x - 1 = 0$. > [!theorem] > > The sequence of $n$-th continued fractions converges to the original number. > > *Proof Sketch.*[^1] The remainder at each step $\bracs{1/x} \in (0, 1)$, but is placed further down the fraction each time. This means that each continued fraction satisfies $x \in (\frac{p_n}{q_n},\frac{p_n+1}{q_n})$. However, with an extra layer added each time, $p_n$ and $q_n$ becomes large, showing that this converges to $x$. > [!theorem] > > Continued fractions is the most effective way of approximating rational numbers. Namely, you cannot do better than continued fractions without using a larger denominator [^1]: Did you seriously thing that he would do a full proof in class?