Donald Knuth offers a start to this rich subject in Seminumerial Algorithms. The general form of a continued fraction is
\[ \frac {b_1} {a_1 + \frac {b_2} {a_2 + \frac {b_3} {a_3}}} = b_1 / (a_1 + b_2 / (a_2 + b_3 / a_3)) \ \ . \]We’ll look at continued fractions in which all the \( b \)’s are one. A convenient notation is
\[ \newcommand{\sslash}{\mathbin{/\mkern-6mu/}} \sslash x_1, x_2, x_3, \ldots, x_n \sslash = \frac{1}{x_1 + \frac{1}{x_2 + \frac{1}{ \cdots \frac{\rule{0in}{.1in}}{x_{n-1} + \frac{1}{x_n}}}}} \ \ . \]One reason to study continued fractions is that they are beautiful expressions. This sampler is from Knuth and The Handbook of Mathematical Functions, usually known by its authors, Abramowitz & Stegun.
\[ \phi = \frac{1 + \sqrt{5}}{2} = 1 + \sslash 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \ldots \sslash \] \[ e = 2 + \sslash 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, \ldots \sslash \] \[ \pi = 3 + \sslash 7, 15, 1, 192, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, \ldots \sslash \] \[ tan(1) = \sslash 1, -3, 5, -7, 9, -11, 13, \ldots \sslash \] \[ ln(1 + z) = \frac {z} {1 + \frac {z} {2 + \frac {z} {3 + \frac {4 z} {4 + \frac {4 z} {5 + \frac {9 z} {6 + \cdots}}}}}} \] \[ e^z = \frac {1} {1 - \frac {z} {1 + \frac {z} {2 - \frac {z} {3 + \frac {z} {2 - \frac {z} {5 + \frac {z} {2 - \cdots}}}}}}} \]Euler and others investigated the useful continuant polynomials:
\[ K_{n}(x_1, x_2, \ldots, x_n) = \left\{ \begin{array}{ll} 1 & \mbox{if $n = 0$} \\ x_1 & \mbox{if $n = 1$} \\ {x_1 K_{n-1}(x_2, x_3, \ldots, x_n) + K_{n-2}(x_3, x_4, \ldots, x_n)} & \mbox{if $n > 1$} \end{array} \right. \]Here are the first several:
\[ \begin{array}{ll} K_0 & 1 \\ K_1(x_1) & x_1 \\ K_2(x_1, x_2) & x_1 x_2 + 1 \\ K_3(x_1, x_2, x_3) & x_1 x_2 x_3 + x_1 + x_3 \\ K_4(x_1, x_2, x_3, x_4) & x_1 x_2 x_3 x_4 + x_1 x_2 + x_1 x_4 + x_2 x _3 + 1 \\ K_5(x_1, x_2, x_3, x_4, x_5) & \begin{array}{l} x_1 x_2 x_3 x_4 x_5 + x_1 x_2 x_3 + x_1 x_2 x_5 + x_1 x _4 x_5 + \\ \ \ \ x_3 x_4 x_5 + x_1 + x_3 + x_5 \end{array} \end{array} \]Fun facts about continuants:
Continued fractions are quotients of K-polynomials: \[ \sslash x_1, x_2, \ldots, x_n \sslash = \frac{K_{n-1}(x_2, x_3, \ldots, x_n)} {K_n(x_1, x_2, \ldots, x_n)} = \frac{1} {\frac{K_n(x_1, \ldots, x_n)} {K_{n-1}(x_2, \ldots, x_n)}} \] To see this, expand the denominator: \[ \frac{x_1 K_{n-1}(x_2, \ldots, x_n) + K_{n-2}(x_3, \ldots, x_n)} {K_{n-1}(x_2, \ldots, x_n)} \] The right-hand side of the formula above is thus \[ \frac{1} {x_1 + \frac{K_{n-2}(x_3, \ldots, x_n)} {K_{n-1}(x_2, \ldots, x_n)}} \] which leads by induction to \[ \frac{1}{x_1 + \frac{1}{x_2 + \frac{1}{ \cdots \frac{\rule{0in}{.1in}}{x_{n-1} + \frac{1}{x_n}}}}} = \sslash x_1, x_2, \ldots, x_n \sslash \ \ . \]
This identity \[ K_n(x_1, \ldots, x_n) K_n(x_2, \ldots, x_{n+1}) - K_{n+1}(x_1, \ldots, x_{n+1}) K_{n-1}(x_2, \ldots, x_n) = (-1)^{n} \] for \( n \geq 1 \) is very useful. To verify it by induction, advance to step \( n+1 \). First expand the left-hand term to \[ (x_1 K_n(x_2, \ldots, x_{n+1}) + K_{n-1}(x_3, \ldots, x_{n+1})) K_{n+1}(x_2, \ldots x_{n+2}) \ \ . \] Then expand the right-hand term to \[ (x_1 K_{n+1}(x_2, \ldots, x_{n+2}) + K_{n}(x_3, \ldots, x_{n+2})) K_{n}(x_2, \ldots x_{n+1}) \ \ . \] The terms with factor \( x_1 \) cancel, leaving \[ K_{n-1}(x_3, \ldots, x_{n+1}) K_{n+1}(x_2, \ldots x_{n+2}) - K_{n}(x_3, \ldots, x_{n+2}) K_{n}(x_2, \ldots x_{n+1}) = (-1)^{n+1} \] by the assumption for step \( n \).
We can now make the remarkable connection between the K-polynomials and continued fractions: \[ \sslash x_1, x_2, \ldots, x_n \sslash = \frac{1}{q_0 q_1} -\frac{1}{q_1 q_2} + \frac{1}{q_2 q_3} + \cdots + \frac{(-1)^{n-1}}{q_{n-1}q_{n}} \] where \( q_k = K_k(x_1, \ldots, x_k) \).
It's just a bit more K-polynomial algebra. Start with the continued fraction as a quotient of continuants \[ \sslash x_1, \ldots, x_n \sslash = \frac{K_{n-1}(x_2, \ldots, x_n) K_{n-1}(x_1, \ldots, x_{n-1}) } {K_n(x_1, \ldots, x_n) K_{n-1}(x_1, \ldots, x_{n-1})} \] with the extra terms chosen in order to exploit the identity of the previous section.
Rewriting the numerator leads to \[ \frac{ (-1)^{n-1} + K_{n}(x_1, \ldots, x_{n}) K_{n-2}(x_2, \ldots, x_{n-1}) } {K_n(x_1, \ldots, x_n) K_{n-1}(x_1, \ldots, x_{n-1})} = \frac{K_{n-2}(x_2, \ldots, x_{n-1})} {K_{n-1}(x_1, \ldots, x_{n-1})} + \frac{(-1)^{n-1}}{q_{n-1}q_{n}} \] which is the inductive step.
Every real number \( X \) with \( 0 \leq X < 1 \) has a regular continued fraction defined by this process. Set \( X = X_0 \), and for every \( n \geq 0 \), if \( X_n \neq 0 \) \[ A_{n+1} = \lfloor 1 / X_n \rfloor \ , \ \ \ \ X_{n+1} = 1 / X_n - A_{n+1} \] If \( X_n = 0 \) the process stops and \( X = \sslash A_1, A_2, \ldots, A_n \sslash \) .
If \( X_n \neq 0 \) then \( 0 \leq X_{n+1} < 1 \), so all the \( A \)’s are positive integers. The definition above expands to \[ X = X_0 = \frac{1}{A_1 + X_1} = \frac{1}{A_1 + \frac{1}{A_2 + X_2}} = \cdots \] so \[ X = \sslash A_1, A_2, \ldots, A_n + X_n \sslash \] for all \( n \geq 1 \), whenever \( X_n \) is defined.
Because \( K_n(A_1, \ldots, A_{n-1}, A_{n} + Y) \) is monotoinc in \( Y \), \( X \) lies between \( \sslash A_1, \ldots, A_n \sslash \) and \( \sslash A_1, \ldots, A_n + 1 \sslash \). The alternating signs in the identity of the last section suggest that successive approximations approach \( X \) from above and below, depending on whether \( n \) is odd or even.
The \( A \)’s are called the partial quotients of \( X \).
Regular continued fractions approach their target quickly. To see this, consider \[ \begin{align} | X - \sslash A_1, \ldots, A_n \sslash | & = | \sslash A_1, \ldots, A_n + X_n \sslash - \sslash A_1, \ldots, A_n \sslash | \\ & = | \sslash A_1, \ldots, A_n, 1 / X_n \sslash - \sslash A_1, \ldots, A_n \sslash | \\ & = 1 / (K_n(A_1, \ldots, A_n) K_{n+1}(A_1, \ldots, A_n, 1 / X_n)) \\ & \leq 1 / (K_n(A_1, \ldots, A_n) K_{n+1}(A_1, \ldots, A_n, A_{n+1})) \end{align} \] with the usual algebra applied in order to achieve a numerator of \( \pm 1 \) and the common denominator shown. The inequality arises because \( A_{n+1} = \lfloor 1 / X_n \rfloor \) and \( K \) is monotonic in each of its parameters.