Recurrence Relation On Continued Fraction

Continued fraction is the fraction of the next form.

\[ \newcommand{\surplus}{\mathbin{\genfrac{}{}{0pt}{}{}{+}}} Q_n = a_0 + \dfrac{b_1}{a_1 + \dfrac{b_2 }{a_2 + \dfrac{\ddots }{\ddots \dfrac{b_{n-1}}{a_{n-1} + \dfrac{b_n}{a_n} } }}} = a_0 + \mathop{\vcenter{\Large\mathrm{K}}}_{i=1}^{n} \frac{b_i}{a_i} = a_0 + \frac {b_1}{a_1} \surplus \frac {b_2}{a_2}  \surplus \cdots \surplus \frac {b_n}{a_n} \]

Since it is unable to get the recurrence relation with basic operators, we can consider fractional linear transformation(FLT).

\[ \pmatrix {a&b \\c&d } (z) = \frac {az+b}{cz+d} \]

If we take a=0 and c=1,

\[ \pmatrix {0&b \\ 1&d} (z) = \frac {b}{z+d} \]

If we put a continued fraction to z, then right hand side would be a bigger continued fraction. With this operation, we can inductively make every continued fraction. Note that we should put z=0 at the end to get the proper form of continued fraction which is mentioned in introduction.

\[\begin{align*} P_0 (z) &= a_0 + z  \\ P_1 (z) &= a_0 + \dfrac {b_1}{a_1 + z} = P_0 \circ\pmatrix {0& b_1 \\ 1 & a_1} (z) \\ P_2 (z) &= a_0 + \dfrac {b_1}{a_1 + \dfrac {b_2}{a_2 + z}} = P_1 \circ \pmatrix {0&b_2 \\ 1 & a_2} (z) \\ \vdots \\ P_n (z) &= P_{n-1} \circ \pmatrix {0&b_n \\ 1 & a_n } (z) \end{align*} \]

Meanwhile, it is convenient to express P_0 as FLT for unity.

\[ P_0 (z) = a_0 + z = \pmatrix {0& 1 \\ 1 & 0 } \circ \pmatrix{0 & b_0 \\ 1& a_0 } (z), \quad (b_0 = 0 ) \]

Fortunately, FLT has an outstanding property. For two 2 by 2 matrix \(\gamma_1, \gamma_2\),

\[ \gamma_1 \circ \gamma_2 (z) = ( \gamma_1 \gamma_2 ) (z) \]

Which means convolution and multiplication have a same role.

\[P_n (z) = P_{n-1} (z) \circ \pmatrix {0&b_n \\ 1 & a_n } (z) = \Bigg( P_{n-1} (z) \pmatrix{0&b_n \\1&a_n} \Bigg) (z)\]

Now we can consider \(P_n (z)\) as a single FLT. Since we will put z=0 at the end, we can ignore the element (1,1) and (1,2) of the 2 by 2 matrix. Then it is able to can understand why we let like following:

\[ P_n (z) = \pmatrix { p_{n-1} & p_n \\ q_{n-1} & q_n } (z) \]

\[ Q_n = P_n (0) = \frac {p_n}{q_n} \]

\[ P_n(z) = \Bigg( \pmatrix {p_{n-2} & p_{n-1} \\ q_{n-2} & q_{n-1}} (z) \pmatrix{0&b_n \\1&a_n} \Bigg) (z) = \pmatrix {p_{n-1} & p_n \\ q_{n-1} & q_n } (z) \]

\[ p_{n+1} = p_{n-1}b_{n+1} + p_n a_{n+1}, \\ q_{n+1} = q_{n-1} b_{n+1} + q_n a_{n+1} \]

\[ p_{-2} = 0, \quad q_{-2} = 1, \quad p_{-1} = 1, \quad q_{-1} = 0 , \quad b_0 = 0\]