COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

特殊な漸化式

特殊な漸化式

問題≪シルベスター数列の漸化式≫

 $a_1 = 2,$ $a_{n+1} = a_n{}^2-a_n+1$ で定まる数列 $\{ a_n\}$ について, 次のことを示せ.
(1)
$a_{n+1} = 1+a_1\cdots a_n$ が成り立つ.
(2)
\begin{align*} \frac{1}{a_1}+\cdots +\frac{1}{a_n} &= 1-\frac{1}{a_1\cdots a_n} = 1-\frac{1}{a_{n+1}-1} \\ &= 1-\frac{1}{a_n(a_n-1)} \end{align*} が成り立つ.

解答例

(1)
$a_{n+1} = 1+a_1\cdots a_n\ \cdots [1]$ を数学的帰納法で示す.
(i)
$a_1 = 2$ から $a_2 = a_1{}^2-a_1+1 = 2^2-2+1 = 3$ であるので, $1+a_1 = 1+2 = 3 = a_2$ が成り立つ.
よって, $n = 1$ のとき $[1]$ が成り立つ.
(ii)
$n = k$ ($k$: 正の整数)のとき $[1]$ が成り立つとすると, \begin{align*} a_{k+2} &= a_{k+1}{}^2-a_{k+1}+1 \\ &= (1+a_1\cdots a_k)^2-(1+a_1\cdots a_k)+1 \\ &= 1+2a_1\cdots a_k+(a_1\cdots a_k)^2 \\ &\qquad -1-a_1\cdots a_k+1 \\ &= 1+a_1\cdots a_k+(a_1\cdots a_k)^2 \\ &= 1+a_1\cdots a_k(1+a_1\cdots a_k) \\ &= 1+a_1\cdots a_ka_{k+1} \end{align*} となり, $n = k+1$ のとき $[1]$ が成り立つ.
(i), (ii) から, すべての正の整数 $n$ に対して $[1]$ が成り立つ.
(2)
$\dfrac{1}{a_1}+\cdots +\dfrac{1}{a_n} = 1-\dfrac{1}{a_1\cdots a_n}\ \cdots [2]$ を数学的帰納法で示す.
(i)
$1-\dfrac{1}{a_1} = 1-\dfrac{1}{2} = \dfrac{1}{2} = \dfrac{1}{a_1}$ であるから, $n = 1$ のとき $[2]$ が成り立つ.
(ii)
$n = k$ ($k$: 正の整数)のとき $[2]$ が成り立つとすると, その両辺に $\dfrac{1}{a_{k+1}}$ を加えることで, $[1]$ から \begin{align*} \frac{1}{a_1}+\cdots +\frac{1}{a_k}+\frac{1}{a_{k+1}} &= 1-\frac{1}{a_1\cdots a_k}+\frac{1}{a_{k+1}} \\ &= 1-\frac{a_{k+1}-a_1\cdots a_k}{a_1\cdots a_ka_{k+1}} \\ &= 1-\frac{1}{a_1\cdots a_ka_{k+1}} \end{align*} となり, $n = k+1$ のとき $[2]$ が成り立つ.
(i), (ii) から, すべての正の整数 $n$ に対して $[2]$ が成り立つ.
また, $[1]$ と定義の漸化式から \begin{align*} &1-\frac{1}{a_1\cdots a_n} = 1-\frac{1}{a_{n+1}-1} \\ &= 1-\frac{1}{a_n{}^2-a_n+1-1} = 1-\frac{1}{a_n(a_n-1)} \end{align*} が成り立つ.

背景

  • 古代エジプトにおいて, 分数は相異なる「単位分数」(分子が $1$ の分数, unit fraction)の和として表されていた. このように表された有理数を「エジプト分数」(Egyptian fraction)と呼ぶ.
  • 項数が $n$ の場合の $1$ 未満の「エジプト分数」の最大値を求めるという問題は, 次のように解決されている: 連立不等式 \[\frac{1}{x_1}+\cdots +\frac{1}{x_n} < 1, \quad 0 < x_1 < \cdots < x_n\] の整数解に対し, $\dfrac{1}{x_1}+\cdots +\dfrac{1}{x_n}$ は \[ a_1 = 2,\ a_{n+1} = a_n{}^2-a_n+1 \quad \cdots [*]\] で定まる数列 $\{ a_n\}$ について $(x_1,\cdots,x_n) = (a_1,\cdots,a_n)$ であるとき最大値 $1-\dfrac{1}{a_n(a_n-1)}$ をとる(シルベスターの定理; $n = 2,$ $3$ の場合はこちらを参照). $[*]$ で定まる数列 $\{ a_n\}$ は「シルベスター数列」(Sylvester sequence)と呼ばれる. 本問では,「シルベスター数列」$\{ a_n\}$ を特徴づけるもう $1$ つの漸化式 \[ a_{n+1} = 1+a_1\cdots a_n\] を導いて, \[\frac{1}{a_1}+\cdots +\frac{1}{a_n} = 1-\frac{1}{a_n(a_n-1)}\] であることを示した.

問題≪無理数の近似分数にまつわる数列≫

 $a$ を正の無理数とする. $a_0 = a$ とおき, 実数 $x$ を超えない最大の整数を $[x]$ で表すことにして, $a_1$ を $a_0 = [a_0]+\dfrac{1}{a_1}$ により定める. このようにして, 数列 $\{ a_n\}$ を漸化式 $a_n = [a_n]+\dfrac{1}{a_{n+1}}$ により定める. また, 数列 $\{ p_n\},$ $\{ q_n\}$ を \begin{align*} &p_0 = [a_0], &&\!\!\!\!\!\!\!\!\!\! p_1 = [a_0][a_1]+1, &&\!\!\!\!\!\!\!\!\!\! p_{n+2} = p_n+[a_{n+2}]p_{n+1}, \\ &q_0 = 1, &&\!\!\!\!\!\!\!\!\!\! q_1 = [a_1], &&\!\!\!\!\!\!\!\!\!\! q_{n+2} = q_n+[a_{n+2}]q_{n+1} \end{align*} により定める. このとき, すべての正の整数 $n$ に対して, 次のことを示せ.
(1)
\[ p_nq_{n-1}-p_{n-1}q_n = (-1)^{n-1} \quad \cdots [1]\] が成り立つ.
(2)
$p_n,$ $q_n$ は互いに素である.
(3)
\[ a = \frac{p_{n-1}+p_na_{n+1}}{q_{n-1}+q_na_{n+1}} \quad \cdots [2]\] が成り立つ.
(4)
\[\left| a-\frac{p_n}{q_n}\right| < \frac{1}{q_n{}^2} \quad \cdots [3]\] が成り立つ.
[上智大]

解答例

(1)
(i)
\[ p_1q_0\!\!-\!p_0q_1 \!=\! [a_0][a_1]\!+\!1\!-\![a_0][a_1] \!=\! 1 \!=\! (-1)^0\] であるから, $n = 1$ のとき $[1]$ が成り立つ.
(ii)
$n = k$ ($k$: 正の整数)のとき, $[1]$ が成り立つとすると, \begin{align*} &p_{k+1}q_k-p_kq_{k+1} \\ &= (p_{k-1}\!\!+\![a_{k+1}]p_k)q_k\!\!-\!p_k(q_{k-1}\!\!+\![a_{k+1}]q_k) \\ &= -(p_kq_{k-1}-p_{k-1}q_k) \\ &= -(-1)^{k-1} \\ &= (-1)^k \end{align*} となるから, $n = k+1$ のとき $[1]$ が成り立つ.
(i), (ii) から, すべての正の整数 $n$ に対して $[1]$ が成り立つ.
(2)
$p_n,$ $q_n$ の最大公約数は, $p_nq_{n-1}-p_{n-1}q_n = (-1)^{n-1}$ の約数であるから, $1$ である. よって, $p_n,$ $q_n$ は互いに素である.
(3)
(i)
\begin{align*} \frac{p_0+p_1a_2}{q_0+q_1a_2} &= \frac{[a_0]+([a_0][a_1]+1)a_2}{1+[a_1]a_2} \\ &= [a_0]+\frac{1}{[a_1]+\dfrac{1}{a_2}} \\ &= [a_0]+\frac{1}{a_1} = a_0 = a \end{align*} であるから, $n = 1$ のとき $[2]$ が成り立つ.
(ii)
$n = k$ ($k$: 正の整数)のとき, $[2]$ が成り立つとすると, \begin{align*} \frac{p_k\!\!+\!p_{k+1}a_{k+2}}{q_k\!\!+\!q_{k+1}a_{k+2}} &\!=\! \frac{p_k\!\!+\!(p_{k-1}\!\!+\![a_{k+1}]p_k)a_{k+2}}{q_k\!\!+\!(q_{k-1}\!\!+\![a_{k+1}]q_k)a_{k+2}} \\ &\!=\! \frac{p_{k-1}a_{k+2}\!\!+\!p_k(1\!+\![a_{k+1}]a_{k+2})}{q_{k-1}a_{k+2}\!\!+\!q_k(1\!+\![a_{k+1}]a_{k+2})} \\ &\!=\! \frac{p_{k-1}\!\!+\!p_k\!\!\left(\dfrac{1}{a_{k+2}}\!\!+\![a_{k+1}]\right)}{q_{k-1}\!\!+\!q_k\!\!\left(\dfrac{1}{a_{k+2}}\!+\![a_{k+1}]\right)} \\ &\!=\! \frac{p_{k-1}\!\!+\!p_ka_{k+1}}{q_{k-1}\!\!+\!q_ka_{k+1}} \\ &\!=\! a \end{align*} となるから, $n = k+1$ のとき $[2]$ が成り立つ.
(i), (ii) から, すべての正の整数 $n$ に対して $[2]$ が成り立つ.
(4)
$[2]$ により \begin{align*} a-\frac{p_n}{q_n} &= \frac{p_{n-1}+p_na_{n+1}}{q_{n-1}+q_na_{n+1}}-\frac{p_n}{q_n} \\ &= \frac{q_n(p_{n-1}+p_na_{n+1})-p_n(q_{n-1}+q_na_{n+1})}{q_n(q_{n-1}+q_na_{n+1})} \\ &= \frac{-(p_nq_{n-1}-p_{n-1}q_n)}{q_n(q_{n-1}+q_na_{n+1})} \\ &= \frac{-(-1)^{n-1}}{q_n(q_{n-1}+q_na_{n+1})} \end{align*} が成り立ち, 定義により \begin{align*} &a_{n+1} = \frac{1}{a_n-[a_n]} > 1, \\ &1 = q_0 \leqq q_1 < q_2 < \cdots \end{align*} であるから, \[ \left| a-\frac{p_n}{q_n}\right| < \frac{1}{q_n{}^2a_{n+1}} < \frac{1}{q_n{}^2}\] が成り立つ. 以上から, すべての正の整数 $n$ に対して $[3]$ が成り立つ.

背景

  • 正の数 $a$ に対して, 数列 $\{ a_n\}$ を \[ a_0 = a, \quad a_n = [a_n]+\dfrac{1}{a_{n+1}}\] により定めると, $a$ は \begin{align*} a &= [a_0]+\dfrac{1}{a_1} = [a_0]+\dfrac{1}{[a_1]+\dfrac{1}{a_2}} = \cdots \\ &= [a_0]+\dfrac{1}{[a_1]+\dfrac{1}{\ddots +[a_n]+\dfrac{1}{a_{n+1}}}} \quad \cdots [*] \end{align*} と表される. これを $a$ の「連分数表示」(continued fraction display)と呼び, $[a_n] = c_n$ のとき $[*]$ を $[c_0;c_1,\cdots,c_n,a_{n+1}]$ で表す.
  • 常に $a_n \neq 0$ となり, 無限に数列 $\{ a_n\}$ が定義できるのは, $a$ が無理数の場合に限る.
  • その場合, $[c_0;c_1,\cdots,c_n]$ を $a$ の第 $n$ 次近似分数($n$-th approximating fraction)と呼ぶ. \[ [c_0;c_1,\cdots,c_n] = \frac{p_n}{q_n}\] であることが知られており, $[3]$ から \[\lim\limits_{n \to \infty}[c_0;c_1,\cdots,c_n] = \lim\limits_{n \to \infty}\dfrac{p_n}{q_n} = a\] が成り立つ. そこで, この極限値を $[c_0;c_1,\cdots,c_n,\cdots ]$ で表し, $a$ の「連分数展開」(continued fraction expansion)と呼ぶ.