いろいろな漸化式
いろいろな漸化式
問題《無理数の連分数展開にまつわる数列の一般項》
$\{ a_n\}$ を初期条件 $a_0 = 1$ と漸化式
\[ a_{n+1} = 1+\frac{1}{1+a_n}\]
で定まる数列とする.
- (1)
- $\left\{\dfrac{a_n-\alpha}{a_n-\beta}\right\}$ が等比数列になるような定数 $\alpha,$ $\beta$ $(\alpha > \beta )$ を $1$ 組求め, その公比 $r$ を求めよ.
- (2)
- 数列 $\{ a_n\}$ の一般項を求めよ.
解答例
- (1)
- 定義から, \[ a_{n+1} = \frac{a_n+2}{a_n+1}\] である. $\left\{\dfrac{a_n-\alpha}{a_n-\beta}\right\}$ が公比 $r$ の等比数列になるには, つまり \[\begin{aligned} &r\cdot\frac{a_n-\alpha}{a_n-\beta} = \frac{a_{n+1}-\alpha}{a_{n+1}-\beta} \\ &= \frac{\dfrac{a_n+2}{a_n+1}-\alpha}{\dfrac{a_n+2}{a_n+1}-\beta} = \frac{(a_n+2)-\alpha (a_n+1)}{(a_n+2)-\beta (a_n+1)} \\ &= \frac{(1-\alpha )a_n+(2-\alpha )}{(1-\beta )a_n+(2-\beta )} = \frac{\dfrac{1-\alpha}{1-\beta}a_n+\dfrac{2-\alpha}{1-\beta}}{a_n+\dfrac{2-\beta}{1-\beta}} \end{aligned}\] となるには ($1-\beta = a_0-\beta \neq 0$ に注意), \[ r = \frac{1-\alpha}{1-\beta}, \quad -r\alpha = \frac{2-\alpha}{1-\beta}, \quad -\beta = \dfrac{2-\beta}{1-\beta}\] となればよい. このとき, (第 $2$ 式)$\div$(第 $1$ 式) と第 $3$ 式から $\alpha,$ $\beta$ はともに \[ -x = \frac{2-x}{1-x}, \quad x(x-1) = 2-x, \quad x^2 = 2\] の解であるから, \[\alpha = \sqrt 2, \quad \beta = -\sqrt 2, \quad r = \frac{1-\sqrt 2}{1+\sqrt 2} = -(\sqrt 2-1)^2\] となればよい.
- (2)
- (1) の結果から $\left\{\dfrac{a_n-\sqrt 2}{a_n+\sqrt 2}\right\}$ は第 $0$ 項と公比が \[\frac{1-\sqrt 2}{1+\sqrt 2} = -(\sqrt 2-1)^2\] の等比数列であるので, \[\begin{aligned} \frac{a_n-\sqrt 2}{a_n+\sqrt 2} &= \{ -(\sqrt 2-1)^2\} ^{n+1} = -(-1)^n(\sqrt 2-1)^{2(n+1)} \\ a_n-\sqrt 2 &= -(-1)^n(\sqrt 2-1)^{2(n+1)}(a_n+\sqrt 2) \\ a_n &= \sqrt 2\cdot\frac{1-(-1)^n(\sqrt 2-1)^{2(n+1)}}{1+(-1)^n(\sqrt 2-1)^{2(n+1)}} \end{aligned}\] である.
参考
$\sqrt 2$ は
\[\sqrt 2 = 1+\frac{1}{2+\dfrac{1}{2+\dfrac{1}{\ddots}}}\]
と「連分数展開」される (こちらを参照).
問題《無理数の近似分数にまつわる数列》
$a$ を正の無理数とする.
実数 $x$ 以下の最大の整数を $[x]$ で表すことにして, 数列 $\{ a_n\}$ を初期条件 $a_0 = a$ と漸化式 $a_n = [a_n]+\dfrac{1}{a_{n+1}}$ で定める.
また, 数列 $\{ p_n\},$ $\{ q_n\}$ を
\[\begin{aligned}
&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{aligned}\]
で定める.
このとき, すべての非負整数 $n$ に対して, 次のことを示せ.
(4) \[\left| a-\frac{p_n}{q_n}\right| < \frac{1}{q_n{}^2} \quad \cdots [3]\]
が成り立つ.
- (1)
- \[ p_{n+1}q_n-p_nq_{n+1} = (-1)^n \quad \cdots [1]\] が成り立つ.
- (2)
- $p_n,$ $q_n$ は互いに素である.
- (3)
- \[ a = \frac{p_n+p_{n+1}a_{n+2}}{q_n+q_{n+1}a_{n+2}} \quad \cdots [2]\] が成り立つ.
(参考: $2000$ 上智大)
解答例
- (1)
- (i)
- $n = 0$ のとき. \[ p_1q_0-p_0q_1 = [a_0][a_1]+1-[a_0][a_1] = 1 = (-1)^0\] であるから, $[1]$ が成り立つ.
- (ii)
- $n = k$ ($k$: 非負整数) のとき $[1]$ が成り立つとする. このとき, \[\begin{aligned} &p_{k+2}q_{k+1}-p_{k+1}q_{k+2} \\ &= (p_k+[a_{k+2}]p_{k+1})q_{k+1}-p_{k+1}(q_k+[a_{k+2}]q_{k+1}) \\ &= -(p_{k+1}q_k-p_kq_{k+1}) \\ &= -(-1)^k \\ &= (-1)^{k+1} \end{aligned}\] となるから, $n = k+1$ のとき $[1]$ が成り立つ.
- (2)
- $p_n,$ $q_n$ の最大公約数は, $p_{n+1}q_n-p_nq_{n+1} = (-1)^n$ の約数であるから, $1$ である. よって, $p_n,$ $q_n$ は互いに素である.
- (3)
- (i)
- $n = 0$ のとき. \[\begin{aligned} \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{aligned}\] であるから, $[2]$ が成り立つ.
- (ii)
- $n = k$ ($k$: 非負整数) のとき $[2]$ が成り立つとする. このとき, \[\begin{aligned} \frac{p_{k+1}+p_{k+2}a_{k+3}}{q_{k+1}+q_{k+2}a_{k+3}} &= \frac{p_{k+1}+(p_k+[a_{k+2}]p_{k+1})a_{k+3}}{q_{k+1}+(q_k+[a_{k+2}]q_{k+1})a_{k+3}} \\ &= \frac{p_ka_{k+3}+p_{k+1}(1+[a_{k+2}]a_{k+3})}{q_ka_{k+3}+q_{k+1}(1+[a_{k+2}]a_{k+3})} \\ &= \frac{p_k+p_{k+1}\left( [a_{k+2}]+\dfrac{1}{a_{k+3}}\right)}{q_k+q_{k+1}\left( [a_{k+2}]+\dfrac{1}{a_{k+3}}\right)} \\ &= \frac{p_k+p_{k+1}a_{k+2}}{q_k+q_{k+1}a_{k+2}} \\ &= a \end{aligned}\] となるから, $n = k+1$ のとき $[2]$ が成り立つ.
- (4)
- $n \geqq 1$ のとき, $[1],$ $[2]$ から \[\begin{aligned} 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} \quad (\because [2]) \\ &= \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}{q_n(q_{n-1}+q_na_{n+1})} \quad (\because [1]) \end{aligned}\] が成り立ち, 定義から \[ a_{n+1} = \frac{1}{a_n-[a_n]} > 1, \quad 1 = q_0 \leqq q_1 < q_2 < \cdots\] であるので, \[ \left| a-\frac{p_n}{q_n}\right| < \frac{1}{q_n{}^2a_{n+1}} < \frac{1}{q_n{}^2}\] が成り立つ. これは, $n = 0$ のときも成り立つ. 以上から, すべての非負整数 $n$ に対して $[3]$ が成り立つ.
参考
- 正の数 $a$ に対して, 数列 $\{ a_n\}$ を \[ a_0 = a, \quad a_n = [a_n]+\dfrac{1}{a_{n+1}}\] で定めると, $a$ は \[\begin{aligned} 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{aligned}\] と表される. これを $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) と呼ぶ.
問題《$n!$ の多項間漸化式》
$a_1 = 1$ と漸化式
\[ a_{n+1} = 1+\sum_{k = 1}^nka_k\]
で定まる数列 $\{ a_n\}$ の一般項を求めよ.
解答例
与式から
$a_{n+1}-a_n = na_n$ つまり $a_{n+1} = (n+1)a_n$
が成り立つので, 両辺を $(n+1)!$ で割ると
\[\frac{a_{n+1}}{(n+1)!} = \frac{a_n}{n!}\]
となる.
よって,
\[\frac{a_n}{n!} = \cdots = \frac{a_1}{1!} = 1\]
から
\[ a_n = n!\]
が成り立つ.
問題《シルヴェスター数列の漸化式》
数列 $\{ s_n\}$ を
\[ s_1 = 2, \quad s_{n+1} = s_n{}^2-s_n+1 \quad \cdots [*]\]
で定める.
次のことを示せ.
- (1)
- \[ s_{n+1} = s_1\cdots s_n+1 \quad \cdots [1]\] が成り立つ.
- (2)
- \[\begin{aligned} \frac{1}{s_1}+\cdots +\frac{1}{s_n} &= 1-\frac{1}{s_1\cdots s_n} \quad \cdots [2] \\ &= 1-\frac{1}{s_{n+1}-1} \\ &= 1-\frac{1}{s_n(s_n-1)} \end{aligned}\] が成り立つ.
解答例
- (1)
- $[1]$ を数学的帰納法で示す.
- (i)
- $n = 1$ のとき. $s_1 = 2$ から $s_2 = s_1{}^2-s_1+1 = 2^2-2+1 = 3$ であるので, $s_1+1 = 2+1 = 3 = s_2$ であり, $[1]$ が成り立つ.
- (ii)
- $n = k$ ($k$: 正の整数) のとき $[1]$ が成り立つとする. このとき, \[\begin{aligned} s_{k+2} &= s_{k+1}{}^2-s_{k+1}+1 \\ &= (s_1\cdots s_k+1)^2-(s_1\cdots s_k+1)+1 \\ &= (s_1\cdots s_k)^2+2s_1\cdots s_k+1 \\ &\qquad -s_1\cdots s_k-1+1 \\ &= (s_1\cdots s_k)^2+s_1\cdots s_k+1 \\ &= s_1\cdots s_k(s_1\cdots s_k+1)+1 \\ &= s_1\cdots s_ks_{k+1}+1 \end{aligned}\] となり, $n = k+1$ のとき $[1]$ が成り立つ.
- (2)
- $[2]$ を数学的帰納法で示す.
- (i)
- $n = 1$ のとき. $1-\dfrac{1}{s_1} = 1-\dfrac{1}{2} = \dfrac{1}{2} = \dfrac{1}{s_1}$ であるから, $[2]$ が成り立つ.
- (ii)
- $n = k$ ($k$: 正の整数) のとき $[2]$ が成り立つとする. このとき, その両辺に $\dfrac{1}{s_{k+1}}$ を加えることで, $[1]$ から \[\begin{aligned} \frac{1}{s_1}+\cdots +\frac{1}{s_k}+\frac{1}{s_{k+1}} &= 1-\frac{1}{s_1\cdots s_k}+\frac{1}{s_{k+1}} \\ &= 1-\frac{s_{k+1}-s_1\cdots s_k}{s_1\cdots s_ks_{k+1}} \\ &= 1-\frac{1}{s_1\cdots s_ks_{k+1}} \end{aligned}\] となり, $n = k+1$ のとき $[2]$ が成り立つ.
また, $[1]$ と定義の漸化式から \[\begin{aligned} &1-\frac{1}{s_1\cdots s_n} = 1-\frac{1}{s_{n+1}-1} \\ &= 1-\frac{1}{s_n{}^2-s_n+1-1} = 1-\frac{1}{s_n(s_n-1)} \end{aligned}\] が成り立つ.
参考
- 古代エジプトでは, 整数でない有理数を表すとき, $\dfrac{2}{3}$ を唯一の例外として, 相異なる「単位分数」(分子が $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}$ は $s_1 = 2,$ $s_{n+1} = s_1\cdots s_n+1$ で定まる数列 $\{ s_n\}$ について $(x_1,\cdots,x_n) = (s_1,\cdots,s_n)$ であるとき最大値 \[ 1-\frac{1}{s_1\cdots s_n} = 1-\frac{1}{s_{n+1}-1} = 1-\frac{1}{s_n(s_n-1)}\] をとる ($n = 2,$ $3$ の場合はこちらを参照). 数列 $\{ s_n\}$ は「シルヴェスター数列」(Sylvester sequence) と呼ばれる (注意: $s_0 = 2$ とする流儀もある).
- 数列 $\{ s_n\}$ を特徴付ける等式 $s_1 = 2,$ $s_{n+1} = s_1\cdots s_n+1$ を使うと, 素数が無限にあることが証明できる (こちらを参照).
問題《フェルマー数の数列の漸化式》
$F_n = 2^{2^{n-1}}+1$ を一般項とする数列 $\{ F_n\}$ について,
\[ F_{n+1} = F_1\cdots F_n+2\]
が成り立つことを示せ.
解答例
$F_{n+1} = F_1\cdots F_n+2\ \cdots [1]$ を数学的帰納法で示す.
- (i)
- $F_1 = 2^{2^0}+1 = 3,$ $F_2 = 2^{2^1}+1 = 5$ から,
$F_1+2 = 3+2 = 5 = F_2$ が成り立つ.
よって, $n = 1$ のとき $[1]$ が成り立つ. - (ii)
- $n = k$ ($k$: 正の整数) のとき $[1]$ が成り立つとする. このとき, \[\begin{aligned} F_{k+2} &= 2^{2^{k+1}}+1 = (2^{2^k})^2-1+2 \\ &= (2^{2^k}-1)(2^{2^k}+1)+2 = (F_{k+1}-2)F_{k+1}+2 \\ &= F_1\cdots F_kF_{k+1}+2 \end{aligned}\] となり, $n = k+1$ のとき $[1]$ が成り立つ.
参考
問題《ロジスティック写像》
実数 $a,$ $c$ に対して, 数列 $\{ x_n\}$ を
\[ x_1 = c, \quad x_{n+1} = ax_n(1-x_n)\]
で定める.
- (1)
- $c \neq 0$ であるとする. 常に $x_n = c$ となるとき, $a$ を用いて $c$ を表せ.
- (2)
- $0 \leqq c \leqq 1$ なるすべての実数 $c$ に対して常に $0 \leqq x_n \leqq 1$ となるような $a$ の値の範囲を求めよ.
- (3)
- $0 \leqq c \leqq 1,$ $a = 4$ であるとして, $c = \sin ^2\theta$ とおく. このとき, $\theta$ を用いて数列 $\{ x_n\}$ の一般項を表せ.
(参考: $2004$ 大阪大)
解答例
- (1)
- 常に $x_n = c$ となるためには, $x_2 = c$ であることが必要である.
このとき, $x_2 = ac(1-c) = c,$ $c \neq 0$ から,
となる. このとき, 漸化式から, 常に $x_n = c$ が成り立つ. よって, $c = \dfrac{a-1}{a}$ $(a \neq 0,\ 1)$ である.
$a(1-c) = 1,$ $ac = a-1$ つまり $c = \dfrac{a-1}{a}\ (a \neq 0,\ 1)$ - (2)
- $0 \leqq c \leqq 1\ \cdots [1]$ を仮定する. 常に $0 \leqq x_n \leqq 1$ となるためには, $0 \leqq x_2 \leqq 1$ つまり \[ 0 \leqq ac(1-c) \leqq 1 \quad \cdots [2]\] であることが必要である. $[1]$ における $c$ の $2$ 次関数 $c(1-c)$ の値域は \[ 0 \leqq c(1-c) \leqq \dfrac{1}{4}\] であるから, $[1]$ を満たすすべての実数 $c$ に対して $[2]$ が成り立つためには $0 \leqq a \leqq 4$ であることが必要である. このとき, 漸化式から, 常に $0 \leqq x_n \leqq 1$ が成り立つ. ゆえに, 求める $a$ の値の範囲は, $0 \leqq a \leqq 4$ である.
- (3)
- 仮定と (2) の結果から常に $0 \leqq x_n \leqq 1$ となるので, 各番号 $n$ に対して $x_n = \sin ^2\theta _n$ とおける. このとき, 漸化式から \[\begin{aligned} x_{n+1} &= 4\sin ^2\theta _n(1-\sin ^2\theta _n) = 4\sin ^2\theta _n\cos ^2\theta _n \\ &= (2\sin\theta _n\cos\theta _n)^2 = \sin ^22\theta _n \end{aligned}\] となる. ゆえに, $c = \sin ^2\theta$ とおくと, 数列 $\{ x_n\}$ の一般項は \[ x_n = \sin ^22^{n-1}\theta\] と表される.
参考
$x_1$ の値と漸化式 $x_{n+1} = ax_n(1-x_n)$ で定まる数列 $\{ x_n\}$ を「ロジスティック写像」(logistic map) と呼ぶ.
「ロジスティック写像」は,「ロジスティック方程式」(logistic equation) の「差分化」から得られ, $a$ の値のとり方によって「カオス」(chaos) と呼ばれる複雑な挙動を示すことが知られている.