連分数

$n=0$ では定義より $[a_0;t]=a_0+1/[t]=a_0+1/t=[a_0+1/t]$ である。$n\ge1$ とし、長さの短い場合に正しいとすると
$$ [a_0;a_1,\dots,a_n,t]=a_0+\frac{1}{[a_1;\dots,a_n,t]}=a_0+\frac{1}{[a_1;\dots,a_{n-1},a_n+1/t]}=\Bigl[a_0;a_1,\dots,a_{n-1},a_n+\frac1t\Bigr] $$
である（2 つ目の等号が帰納法の仮定、$a_n+1/t>0$ に注意）。$\square$

$n=0$ では右辺は $(t\cdot1+0)/(t\cdot0+1)=t$ で正しい。$n$ で（すべての $t>0$ について）正しいとする。lem-cf-last-term と帰納法の仮定（$t$ を $a_n+1/t>0$ として使う）により
$$ [a_0;\dots,a_n,t]=\Bigl[a_0;\dots,a_{n-1},a_n+\frac1t\Bigr]=\frac{(a_n+\frac1t)p_{n-1}+p_{n-2}}{(a_n+\frac1t)q_{n-1}+q_{n-2}}=\frac{p_n+\frac1tp_{n-1}}{q_n+\frac1tq_{n-1}}=\frac{tp_n+p_{n-1}}{tq_n+q_{n-1}} $$
であり、$n+1$ でも正しい。分母はどれも正である。$\square$

$n=-1$ では $p_{-1}q_{-2}-p_{-2}q_{-1}=1=(-1)^{-2}$ である。$n\ge0$ で $n-1$ について正しいとすると
$$ p_nq_{n-1}-p_{n-1}q_n=(a_np_{n-1}+p_{n-2})q_{n-1}-p_{n-1}(a_nq_{n-1}+q_{n-2})=-(p_{n-1}q_{n-2}-p_{n-2}q_{n-1})=-(-1)^{n-2}=(-1)^{n-1} $$
である。また $p_nq_{n-2}-p_{n-2}q_n=a_n(p_{n-1}q_{n-2}-p_{n-2}q_{n-1})=a_n(-1)^{n-2}=(-1)^na_n$ である。後半は両辺を $q_nq_{n-1}$（または $q_nq_{n-2}$）で割ればよい（$n\ge1$ で $q_{n-1}>0$、$n\ge2$ で $q_{n-2}>0$）。$\square$

1：$r_{-1}:=a$、$r_0:=b$ とし、$r_k>0$ である限り $r_{k-1}=c_kr_k+r_{k+1}$、$0\le r_{k+1}< r_k$ と整数 $c_k,r_{k+1}$ を定める（除法の原理）。これが互除法である。$x_k=r_{k-1}/r_k$ を $k$ に関する帰納法で示す。$k=0$ では $x_0=a/b$ である。$x_k=r_{k-1}/r_k$ ならば $x_k=c_k+r_{k+1}/r_k$、$0\le r_{k+1}/r_k<1$ なので $a_k=\lfloor x_k\rfloor=c_k$ である。$r_{k+1}=0$ なら $x_k$ は整数で手続きは止まり、そうでなければ $x_{k+1}=1/(x_k-a_k)=r_k/r_{k+1}$ である。$r_0>r_1>r_2>\cdots\ge0$ は整数の狭義減少列なので、ある $n$ で $r_{n+1}=0$ となって止まる。上の式 $x=[a_0;\dots,a_{n-1},x_n]$ で $x_n=a_n$ なので $x=[a_0;\dots,a_n]$ である。$n\ge1$ なら $x_n=r_{n-1}/r_n$ は $r_n< r_{n-1}$ から $1$ より大きい整数なので $a_n\ge2$ である。
2：prop-cf-recurrence により値は整数の比 $p_n/q_n$（$q_n>0$）である。
3：まず、2 つの表し方が実際に同じ値をもつことは lem-cf-last-term（$a_n=(a_n-1)+\frac11$）から分かる。逆に $x=[b_0;b_1,\dots,b_m]$ を任意の単純連分数表示とする。$m\ge1$ かつ $b_m=1$ なら、lem-cf-last-term より $x=[b_0;\dots,b_{m-2},b_{m-1}+1]$ と 1 つ短くでき、その最後の部分商は $2$ 以上である（$m=1$ なら整数 $[b_0+1]$ になる）。したがって、「$m=0$ または $b_m\ge2$」を満たす表示が手続きの出力と一致することを示せばよい。$m$ に関する帰納法による。$m=0$ なら $x=b_0$ は整数で、手続きは $a_0=x$ で止まる。$m\ge1$ なら $y:=[b_1;\dots,b_m]$ は、$m=1$ のとき $b_1\ge2$、$m\ge2$ のとき $b_1+1/[b_2;\dots,b_m]>b_1\ge1$ なので、いずれも $y>1$ である。よって $x=b_0+1/y$、$0<1/y<1$ から $a_0=\lfloor x\rfloor=b_0$、$x_1=1/(x-a_0)=y$ である。$y$ の表示 $[b_1;\dots,b_m]$ は長さが 1 短く同じ条件を満たすので、帰納法の仮定により $y$ の手続きの出力は $b_1,\dots,b_m$ であり、それは $x$ の手続きの $a_1,a_2,\dots$ に等しい。$\square$

prop-cf-determinant より $n\ge2$ で $c_n-c_{n-2}=(-1)^na_n/(q_nq_{n-2})$ であり、$a_n,q_n,q_{n-2}>0$ なので、$n$ が偶数なら正、奇数なら負である。また $c_{2k+1}-c_{2k}=1/(q_{2k+1}q_{2k})>0$ である。任意の $m,k$ について $N:=\max(m,k)$ とおくと $c_{2m}\le c_{2N}< c_{2N+1}\le c_{2k+1}$ である。$\square$

prop-cf-alternating より $(c_{2m})$ は増加して $c_1$ で上に有界、$(c_{2k+1})$ は減少して $c_0$ で下に有界なので、それぞれ極限 $\alpha,\beta$ をもち（単調収束定理）、$\alpha\le\beta$ である。$q_n\ge n$（$n\ge1$）より
$$ 0\le\beta-\alpha\le c_{2k+1}-c_{2k}=\frac{1}{q_{2k+1}q_{2k}}\le\frac{1}{(2k+1)\cdot2k}\qquad(k\ge1) $$
で右辺は $0$ に収束するので $\alpha=\beta$ であり、$(c_n)$ はこの値 $x$ に収束する。狭義の単調性から $c_{2m}< c_{2m+2}\le x\le c_{2k+3}< c_{2k+1}$ である。したがって $x$ は $c_n$ と $c_{n+1}$ の真に間にあり、$|x-c_n|<|c_{n+1}-c_n|=1/(q_nq_{n+1})$ である。$\square$

1：手続きが第 $n$ 段で止まれば $x=[a_0;\dots,a_n]$ は有理数になる（thm-cf-rational の 2）ので、止まらない。上の節「有理数の連分数展開」の冒頭で示した式 $x=[a_0;\dots,a_{k-1},x_k]$ と prop-cf-recurrence（$t=x_{n+1}$）より
$$ x=[a_0;\dots,a_n,x_{n+1}]=\frac{x_{n+1}p_n+p_{n-1}}{x_{n+1}q_n+q_{n-1}} $$
であり、prop-cf-determinant を使うと
$$ x-\frac{p_n}{q_n}=\frac{(x_{n+1}p_n+p_{n-1})q_n-p_n(x_{n+1}q_n+q_{n-1})}{q_n(x_{n+1}q_n+q_{n-1})}=\frac{p_{n-1}q_n-p_nq_{n-1}}{q_n(x_{n+1}q_n+q_{n-1})}=\frac{(-1)^n}{q_n(x_{n+1}q_n+q_{n-1})} $$
である。$x_{n+1}$ は整数でないので $a_{n+1}< x_{n+1}< a_{n+1}+1$ であり、分母は $q_n(a_{n+1}q_n+q_{n-1})=q_nq_{n+1}$ より大きく、$q_n(q_{n+1}+q_n)$ より小さい。$q_{n+1}\ge q_n$ から最後の不等式を得る。右辺は $0$ に収束するので $p_n/q_n\to x$ であり、$p_n/q_n$ は無限単純連分数 $[a_0;a_1,\dots]$ の収束子なので $x=[a_0;a_1,a_2,\dots]$ である。
2：$y:=[a_1;a_2,a_3,\dots]$ とおく（thm-cf-infinite により定まる）。thm-cf-infinite を列 $a_1,a_2,\dots$ に使うと、$y$ はその第 $0$ 収束子 $a_1$ より真に大きいので $y>1$ である。定義から $[a_0;a_1,\dots,a_n]=a_0+1/[a_1;\dots,a_n]$ であり、$n\to\infty$ とすると右辺の $[a_1;\dots,a_n]$ は $y>0$ に収束するので $x=a_0+1/y$ である。$0<1/y<1$ なので手続きの最初の段は $a_0=\lfloor x\rfloor$、$x_1=1/(x-a_0)=y$ を与える。$y$ は整数でない（$y=a_1+1/[a_2;a_3,\dots]$ で、同じ理由で $[a_2;a_3,\dots]>1$）ので手続きは続き、同じ議論を $y$ に繰り返すと、$k$ に関する帰納法により第 $k$ 段の部分商は $a_k$、完全商は $x_k=[a_k;a_{k+1},\dots]$ である。手続きが止まらないので、thm-cf-rational の 1 により $x$ は有理数でない。$\square$

完全商 $x_k$ は thm-cf-irrational の証明の 2 より $x_k=[a_k;a_{k+1},\dots]$ であり、部分商の列の $k$ 番目以降だけで決まる。また $x_k$ に手続きを施したときの完全商は $x_k,x_{k+1},\dots$ である。
循環するならば 2 次無理数：$k\ge m$ で $a_{k+h}=a_k$ とする。$x_{m+h}$ と $x_m$ は同じ列 $a_m,a_{m+1},\dots$ で決まるので $y:=x_m=x_{m+h}$ である。有限列 $a_m,\dots,a_{m+h-1}$ から作った $p,q$ を $P:=p_{h-1}$、$P':=p_{h-2}$、$Q:=q_{h-1}$、$Q':=q_{h-2}$ とおくと、prop-cf-recurrence を $y$ に使って $y=[a_m;\dots,a_{m+h-1},y]=(yP+P')/(yQ+Q')$ となり、
$$ H(u):=Qu^2+(Q'-P)u-P' $$
について $H(y)=0$ である。$Q\ge1$ なので $H$ は $0$ でない。次に、$x$ の $p,q$ で $\alpha:=p_{m-1}$、$\beta:=p_{m-2}$、$\gamma:=q_{m-1}$、$\delta:=q_{m-2}$ とおくと、$x=(\alpha y+\beta)/(\gamma y+\delta)$、$\alpha\delta-\beta\gamma=(-1)^m$ である（$m=0$ なら $x=y$）。$\alpha-\gamma x\neq0$ である（$\gamma\neq0$ なら $x$ が有理数になり、$\gamma=0$ なら $m=0$ で $\alpha=1$）。$x(\gamma y+\delta)=\alpha y+\beta$ を $y$ について解くと $y=(\delta x-\beta)/(\alpha-\gamma x)$ となる。整数係数の多項式
$$ g(t):=Q(\delta t-\beta)^2+(Q'-P)(\delta t-\beta)(\alpha-\gamma t)-P'(\alpha-\gamma t)^2 $$
は、$\alpha-\gamma t\neq0$ のとき $g(t)=(\alpha-\gamma t)^2H\bigl(\frac{\delta t-\beta}{\alpha-\gamma t}\bigr)$ を満たすので $g(x)=0$ である。$g$ が零多項式だとすると、$\alpha-\gamma t\neq0$ を満たす無限個の有理数 $t$ について $u(t):=\frac{\delta t-\beta}{\alpha-\gamma t}$ が $H$ の根になる。ところが $u(t)=u(s)$ から分母を払うと $(\alpha\delta-\beta\gamma)(t-s)=0$、すなわち $t=s$ が出るので $u(t)$ は互いに異なり、$0$ でない高々 2 次の多項式 $H$ が無限個の根をもつことになって矛盾する。よって $g$ は $0$ でない高々 2 次の整数係数多項式で、無理数 $x$ を根にもつ。1 次以下なら根は有理数か存在しないので、$g$ はちょうど 2 次であり、$x$ は 2 次無理数である。
2 次無理数ならば循環する：$f(t):=at^2+bt+c$（$a\neq0$）、$f(x)=0$ とし、判別式を $D:=b^2-4ac$ とおく。$f$ のもう一つの根 $x'$ は $x+x'=-b/a$ を満たすので無理数であり、$f$ は有理数の根をもたない。$n\ge1$ について $x=(x_np_{n-1}+p_{n-2})/(x_nq_{n-1}+q_{n-2})$ を $f(x)=0$ に代入し $(x_nq_{n-1}+q_{n-2})^2$ を掛けると、$A_nx_n^2+B_nx_n+C_n=0$ となる。ここで
$$ A_n=ap_{n-1}^2+bp_{n-1}q_{n-1}+cq_{n-1}^2,\quad B_n=2ap_{n-1}p_{n-2}+b(p_{n-1}q_{n-2}+p_{n-2}q_{n-1})+2cq_{n-1}q_{n-2},\quad C_n=ap_{n-2}^2+bp_{n-2}q_{n-2}+cq_{n-2}^2 $$
は整数であり、両辺を展開して比べると $B_n^2-4A_nC_n=D\,(p_{n-1}q_{n-2}-p_{n-2}q_{n-1})^2=D$ が成り立つ（prop-cf-determinant）。$A_n=q_{n-1}^2f(p_{n-1}/q_{n-1})$ であり、$f$ は有理数の根をもたないので $A_n\neq0$ である。
$r:=p_{n-1}/q_{n-1}$ とおくと、thm-cf-irrational の 1 より $|r-x|<1/q_{n-1}^2\le1$ である。$f(r)=f(r)-f(x)=(r-x)\bigl(a(r+x)+b\bigr)$ なので
$$ |A_n|=q_{n-1}^2|r-x|\,|a(r+x)+b|<|a|(2|x|+1)+|b|=:M $$
である。$n\ge2$ では $C_n=A_{n-1}$ なので $|C_n|< M$ であり、$B_n^2=D+4A_nC_n\le|D|+4M^2$ である。したがって $n\ge2$ で整数の組 $(A_n,B_n,C_n)$ は有限個の値しかとらない。各 $x_n$ は $A_n\neq0$ の 2 次方程式の根で、1 つの方程式の根は高々 2 個なので、$\{x_n\mid n\ge2\}$ は有限集合である。よって $2\le m< m+h$ で $x_m=x_{m+h}$ となるものがある。$x_{k+1}$ は $x_k$ だけで決まる（$a_k=\lfloor x_k\rfloor$、$x_{k+1}=1/(x_k-a_k)$）ので、$k\ge m$ で $x_{k+h}=x_k$、したがって $a_{k+h}=a_k$ である。$\square$