連分数は分母に分数が出る形の式のことである。
a_0 + \frac{b_0}{ \displaystyle a_1 + \frac{b_1}{ \displaystyle a_2 + \frac{b_2}{ \displaystyle a_3 + \frac{b_3}{\cdots} } } }
話を単純にするため分子がみな 1 になる連分数を扱う。すなわち
a_0 + \frac{1}{ \displaystyle a_1 + \frac{1}{ \displaystyle a_2 + \frac{1}{ \displaystyle a_3 + \frac{1}{\cdots} } } }
このような連分数はスペースを取るので様々な省略記法があるのだが、ここでは上の連分数を
(a_0, a_1, a_2, a_3, \cdots ) と表すことにする。
さて、この連分数の値を求めることを目標とするのだが、その前に全く関係のなさそうな話を少々することになる。
\begin{cases}
x_0 & = k_0x_1 + x_2 \\
x_2 & = k_1x_2 + x_3 \\
& \cdots \\
x_{n-1} & = k_{n-1}x_n + x_{n+1} \\
& \cdots
\end{cases} \cdots (1)
さてガウスの用いた記号にならって、次の記号を定める。
\begin{align}
\left[ k_0 \right] & = k_0 \\
\left[ k_0, k_1 \right] & = k_0 k_1 + 1 \\
\left[ k_0, k_1, \cdots , k_{n+1} \right] & = k_{n+1} \left[ k_0, k_1, \cdots , k_n \right] + \left[ k_0, k_1, \cdots , k_{n-1} \right]
\end{align}
このとき、上の連立方程式について次が成り立つ。
p_0 = 1, \ p_n = \left[ k_0, k_1, \cdots , k_{n-1} \right] \ (n = 1, 2, \cdots ) とおくと
x_0 = p_nx_n + p_{n-1}x_{n+1} \ \cdots (2) （p_n は \left[ \, \cdots \, \right] の再記である）
証明
x_0 = k_0x_1 + x_2 = p_1x_1 + p_0x_2 より、 n = 1 のときは自明に成り立つ。
次に、n のとき成り立つとすると
x_0 = p_nx_n + p_{n-1}x_{n+1} (1) の式を代入して
\begin{align}
x_0 & = p_n(k_nx_{n+1} + x_{n+2}) + p_{n-1}x_{n+1} \\
& = (p_nk_n + p_{n-1})x_{n+1} + p_nx_{n+2} \\
& = ( k_n \left[ k_0, k_1, \cdots , k_{n-1} \right] + \left[ k_0, k_1, \cdots , k_{n-2} \right] )x_{n+1} + p_nx_{n+2} \\
& = ( \left[ k_0, k_1, \cdots , k_n \right] )x_{n+1} + p_nx_{n+2} \\
& = p_{n+1}x_{n+1} + p_nx_{n+2} \\
\end{align}
すなわち n+1 のときでも成り立つ。
以上より数学的帰納法で証明される。
なお、p_{n+1} = p_nk_n + p_{n-1} という漸化式が上の証明から分かるが、
これは k_n をユークリッドの互除法の逐次商とみたときに一次不定方程式の係数の漸化式と同じである。
さて、(1) の一番目の式を除外したときに定理 4.1 より x_1 = q_nx_n + q_{n-1}x_{n+1}
ただし q_0 = 0, \ q_1 = 1, \ q_n = \left[ k_1, k_2, \cdots , k_{n-1} \right] \ (n = 2, 3, \cdots) である。
そうすると、p_n と同様、q_{n+1} = q_nk_n + q_{n-1} \ \cdots (3) となる。
このとき、次の定理が連分数の理論において重要である。
(-1)^nx_n = q_{n-1}x_0 - p_{n-1}x_1
証明
これを証明する前に、まずは次の等式を証明する。
\left|
    \begin{array}{ccc}
      p_n & p_{n-1} \\
      q_n & q_{n-1}
    \end{array}
\right|
 = (-1)^n
すなわち、p_n q_{n-1} - p_{n-1}q_n = (-1)^n \cdots (4)
n = 1 のとき、
\left|
    \begin{array}{ccc}
      p_1 & p_0 \\
      q_1 & q_0
    \end{array}
\right|
\left|
    \begin{array}{ccc}
      k_0 & 1 \\
      1 & 0
    \end{array}
\right|
-1
より、自明に成り立つ。
次に、n のとき成り立つとすると、
\begin{align}
\left|
    \begin{array}{ccc}
      p_{n+1} & p_n \\
      q_{n+1} & q_n
    \end{array}
\right|
& = 
\left|
    \begin{array}{ccc}
      p_nk_n + p_{n-1} & p_n \\
      q_nk_n + q_{n-1} & q_n
    \end{array}
\right| \\
& = (p_nk_n + p_{n-1})q_n - p_n(q_nk_n + q_{n-1}) \\
& = p_nk_nq_n + p_{n-1}q_n - p_nq_nk_n - p_nq_{n-1} \\
& = p_{n-1}q_n - p_nq_{n-1} \\
& = -(p_nq_{n-1} - p_{n-1}q_n) \\
& = -
\left|
    \begin{array}{ccc}
      p_n & p_{n-1} \\
      q_n & q_{n-1} \\
    \end{array}
\right| \\
& = (-1)^{n+1}
\end{align}
ただし、最後の変形には帰納法の仮定を用いた。以上より数学的帰納法によって証明される。
さて、(2)、(3) より
\begin{align}
& \begin{cases}
  x_0 & = p_nx_n + p_{n-1}x_{n+1} \\
  x_1 & = q_nx_n + q_{n-1}x_{n+1}
\end{cases} \ \cdots (5) \\
\iff &
\begin{cases}
  q_{n-1}x_0 & = q_{n-1}p_nx_n + q_{n-1}p_{n-1}x_{n+1} \\
  -p_{n-1}x_1 & = -p_{n-1}q_nx_n - p_{n-1}q_{n-1}x_{n+1}
\end{cases}
\end{align}
\therefore \ x_n(p_nq_{n-1} - p_{n-1}q_n) = q_{n-1}x_0 - p_{n-1}x_1 \iff (-1)^nx_n = q_{n-1}x_0 - p_{n-1}x_1 \ \ \ (\because (4) \, )
----
さて、p_n, q_n を計算するには次の等式を用いるのが簡便である。
\left[ k_0, k_1, \cdots, k_{n+1} \right] = k_0 \left[ k_1, k_2, \cdots, k_{n+1} \right] + \left[ k_2, k_3, \cdots, k_{n+1} \right] \ \ \cdots (6)
n = 1 のとき、定義より
\begin{align}
\left[ k_0, k_1, k_2 \right] & = k_2 \left[ k_0, k_1 \right] + \left[ k_0 \right] \\
& = k_2 (k_0k_1 + 1) + k_0 \\
& = k_0(k_1k_2 + 1) + k_2 \\
& = k_0 \left[ k_1, k_2 \right] + \left[ k_2 \right]
\end{align}
したがって成り立つ。
n = 2 のとき、
\begin{align}
\left[ k_0, k_1, k_2, k_3 \right] & = k_3 \left[ k_0, k_1, k_2 \right] + \left[ k_0, k_1 \right] \\
& = k_3(k_2 \left[ k_0, k_1 \right] + \left[ k_0 \right]) + k_0k_1 + 1 \\
& = k_3(k_2k_0k_1 + k_2 + k_0) + k_0k_1 + 1 \\
& = k_0k_1k_2k_3 + k_2k_3 + k_0k_3 + k_0k_1 + 1 \\
\end{align}
\begin{align}
k_0 \left[ k_1, k_2, k_3 \right] + \left[ k_2, k_3 \right] & = k_0(k_3 \left[ k_1, k_2 \right] + \left[ k_1 \right]) + k_2k_3 + 1 \\
& = k_0(k_3k_2k_1 + k_3) + k_2k_3 + 1 \\
& = k_0k_1k_2k_3 + k_2k_3 + k_0k_1 + 1 \\
\end{align}
\therefore \ \left[ k_0, k_1, k_2, k_3 \right] = k_0 \left[ k_1, k_2, k_3 \right] + \left[ k_2, k_3 \right]
したがって成り立つ。
次に、n < m \ \ (3 \leqq m) なる全ての n について成り立つとすると
\begin{align}
\left[ k_0, k_1, \cdots, k_{m+1} \right] & = k_{m+1} \left[ k_0, k_1, \cdots , k_m \right] + \left[ k_0, k_1, \cdots , k_{m-1} \right] \\
& = k_{m+1} (k_0 \left[ k_1, k_2, \cdots, k_m \right] + \left[ k_2, k_3, \cdots, k_m \right]) + (k_0 \left[ k_1, k_2, \cdots, k_{m-1} \right] + \left[ k_2, k_3, \cdots, k_{m-1} \right]) \\
& = k_0 (k_{m+1} \left[ k_1, k_2, \cdots, k_m \right] + \left[ k_1, k_2, \cdots, k_{m-1} \right]) + (k_{m+1}  \left[ k_2, k_3, \cdots, k_m \right] + \left[ k_2, k_3, \cdots, k_{m-1} \right]) \\
& = k_0 \left[ k_1, k_2, \cdots, k_{m+1} \right] + \left[ k_2, k_3, \cdots, k_{m+1} \right] \\
\end{align}
よって、m も成り立つ。以上より全ての場合に成り立つことが分かり、(6) は累積帰納法で証明される。この式を使えば、後ろから \left[ k_{n+1} \right], \ \left[ k_{n}, k_{n+1} \right], \ \left[ k_{n-1}, k_{n}, k_{n+1} \right], \cdots が次々に求まり、楽に計算ができる。
さて、目標としていたことは連分数を計算することだったが、それは (6) を用いれば簡単にできる。
(a_0, a_1, a_2, \cdots, a_n) は冒頭と同じく
a_0 + \frac{1}{ \displaystyle a_1 + \frac{1}{ \displaystyle a_2 + \frac{1}{ \displaystyle a_3 + \frac{1}{ \displaystyle \cdots + \frac{1}{ \displaystyle a_{n-1} + \frac{1}{ \displaystyle a_n} } } } } }
を表すこととする。
(k_0, k_1, k_2, \cdots , k_n) = \frac{ \left[ k_0, k_1, k_2, \cdots , k_n \right] }{ \left[ k_1, k_2, \cdots , k_n \right] } が成り立つ。
なぜなら、(6) によって左辺は
\begin{align}
\frac{ k_0 \left[ k_1, k_2, \cdots , k_n \right] + \left[ k_2, \cdots, k_n \right] }{ \left[ k_1, k_2, \cdots , k_n \right] } & = k_0 + \frac{1}{ \displaystyle \frac{ \left[ k_1, k_2, \cdots, k_n \right] }{ \left[ k_2, \cdots, k_n \right] } } \\
& =  k_0 + \frac{1}{ \displaystyle k_1 + \frac{1}{ \, \displaystyle \frac{ \left[ k_2, \cdots, k_n \right] }{ \displaystyle \left[ k_3, \cdots, k_n \right] \, } } }
\end{align}
となるからである。