COMPASS

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

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

漸化式

理論

線形漸化式

$2$ 項間線形漸化式

解法≪定数係数の $2$ 項間線形漸化式≫

 $a,$ $p \neq 0,$ $q$ を定数とする. $$\left\{\begin{array}{l} a_1 = a, \\ a_{n+1} = pa_n+q \cdots (\spadesuit ) \end{array}\right.$$ で定まる数列 $\{ a_n\}$ の一般項を求める.
(i)
$p = 1$ のとき. $$a_{n+1} = a_n+q$$ より, $\{ a_n\}$ は初項 $a,$ 公差 $q$ の等差数列だから, $$a_n = a+(n-1)q.$$
(ii)
$p \neq 1$ のとき. $2$ つの解法を紹介する.
(1)
$(\spadesuit )$ の特性方程式 $$x = px+q$$ の解を $\alpha$ とおく: $\alpha = -\dfrac{q}{p-1}.$
$(\spadesuit ),$ $\alpha = p\alpha +q$ の辺々を引くと, $$a_{n+1}-\alpha = p(a_n-\alpha ).$$ よって, $\{ a_n-\alpha\}$ は初項 $a_1-\alpha = a-\alpha,$ 公比 $p$ の等比数列だから, \begin{align*} a_n-\alpha &= (a-\alpha )p^{n-1}. \\ \therefore a_n &= (a-\alpha )p^{n-1}+\alpha \\ &= \left( a+\frac{q}{p-1}\right) p^{n-1}-\frac{q}{p-1}. \end{align*}
(2)
$(\spadesuit )$ において $n$ を $n+1$ に置き換えると, $$a_{n+2} = pa_{n+1}+q \cdots (\spadesuit )'.$$ $(\spadesuit )'-(\spadesuit )$ より, $$a_{n+2}-a_{n+1} = p(a_{n+1}-a_n).$$ よって, $\{ a_n\}$ の階差数列 $\{ a_{n+1}-a_n\}$ は初項 $a_2-a_1 = (pa+q)-a = (p-1)a+q,$ 公比 $p$ の等比数列で, その一般項は $((p-1)a+q)p^{n-1}$ だから, \begin{align*} a_n &= a+\sum\limits_{i = 1}^{n-1}((p-1)a+q)p^{i-1} \\ &= a+\frac{(p-1)a+q}{p-1}(p^{n-1}-1) \\ &= a+a(p^{n-1}-1)+\frac{q}{p-1}(p^{n-1}-1) \\ &= \left( a+\frac{q}{p-1}\right) p^{n-1}-\frac{q}{p-1}. \end{align*}

注意≪定数係数の $2$ 項間線形漸化式の一般化≫

 上記の解法は, $l \neq 0,$ $l \neq p$ のとき, 上記の $p,$ $q$ を $\dfrac{p}{l},$ $\dfrac{q}{l}$ に置き換えることにより, $a_1 = a,$ $la_{n+1} = pa_n+q$ で定まる数列 $\{ a_n\}$ に一般化できる.
 $2$ 項間線形漸化式について, 係数がすべて定数の場合に帰着して解ける, 斉次部分のみ定数の場合として, 次の漸化式 $(\heartsuit ),$ $(\diamondsuit )$ を考える.

解法≪非斉次部分が等差数列の $2$ 項間線形漸化式≫

 $a,$ $p \neq 0,$ $q,$ $r$ を定数とする. $$\left\{\begin{array}{l} a_1 = a, \\ a_{n+1} = pa_n+qn+r \cdots (\heartsuit ) \end{array}\right.$$ で定まる数列 $\{ a_n\}$ の一般項を求める.
$(\heartsuit )$ において $n$ を $n+1$ に置き換えると, $$a_{n+2} = pa_{n+1}+q(n+1)+r \cdots (\heartsuit )'.$$ $(\heartsuit )'-(\heartsuit )$ より, $$(a_{n+2}-a_{n+1}) = p(a_{n+1}-a_n)+q.$$ すなわち, $\{ a_n\}$ の階差数列 $\{ b_n\}$ は $$b_{n+1} = pb_n+q$$ を満たすから, $(\spadesuit )$ 型の漸化式の解法より $\{ b_n\}$ の一般項が求められる.
その結果と自然数 $n \geqq 2$ に対する公式 $$a_n = a+\sum\limits_{i = 1}^{n-1}b_i$$ より, $\{ a_n\}$ の一般項が求まる.

解法≪非斉次部分が等比数列の $2$ 項間線形漸化式≫

 $a,$ $p,$ $q,$ $r$ を $p \neq 0,$ $r \neq 0$ を満たす定数とする. $$\left\{\begin{array}{l} a_1 = a, \\ a_{n+1} = pra_n+qr^{n+1} \cdots (\diamondsuit ) \end{array}\right.$$ で定まる数列 $\{ a_n\}$ の一般項を求める.
$(\diamondsuit )$ の両辺を $r^{n+1} \neq 0$ で割ると, $$\frac{a_{n+1}}{r^{n+1}} = p\frac{a_n}{r^n}+q.$$ よって, $b_n = \dfrac{a_n}{r^n}$ で定まる数列 $\{ b_n\}$ は $$b_{n+1} = pb_n+q$$ を満たすから, $(\spadesuit )$ 型の漸化式の解法より $\{ b_n\}$ の一般項が求まる.
その結果と $$a_n = b_nr^n$$ より, $\{ a_n\}$ の一般項が求まる.

$2$ 項間 $1$ 次分数型漸化式

解法≪定数係数の $2$ 項間 $1$ 次分数型漸化式≫

 $a,$ $p,$ $q,$ $r,$ $s$ を (I) $r \neq 0,$ $ps-qr \neq 0$ を満たす定数とする. $$\left\{\begin{array}{l} a_1 = a, \\ a_{n+1} = \frac{pa_n+q}{ra_n+s} \cdots (\clubsuit ) \end{array}\right.$$ で定まる数列 $\{ a_n\}$ の一般項を求める. ただし, 任意の自然数 $n$ に対して $ra_n+s \neq 0$ とする.
$(\clubsuit )$ の特性方程式 $$x = \frac{px+q}{rx+s}$$ の $2$ 解を $\alpha,$ $\beta$ とおく. このとき, $$\left\{\begin{array}{l} \alpha = \frac{p\alpha +q}{r\alpha +s} \cdots [1], \\ \beta = \frac{p\beta +q}{r\beta +s} \cdots [2]. \end{array}\right.$$ $(\clubsuit )-[1],$ $(\clubsuit )-[2]$ より, $$\left\{\begin{array}{l} a_{n+1}-\alpha = \frac{(ps-qr)(a_n-\alpha )}{(r\alpha +s)(ra_n+s)} \cdots [3], \\ a_{n+1}-\beta = \frac{(ps-qr)(a_n-\beta )}{(r\beta +s)(ra_n+s)} \cdots [4]. \end{array}\right.$$
(i)
$a \neq \alpha \neq \beta \neq a$ のとき. $[3]\div [4]$ より, $$\frac{a_{n+1}-\alpha}{a_{n+1}-\beta} = \frac{r\beta +s}{r\alpha +s}\cdot\frac{a_n-\alpha}{a_n-\beta}.$$ よって, $\left\{\dfrac{a_n-\alpha}{a_n-\beta}\right\}$ は初項 $\dfrac{a_1-\alpha}{a_1-\beta} = \dfrac{a-\alpha}{a-\beta},$ 公比 $\dfrac{r\beta +s}{r\alpha +s}$ の等比数列だから, $$\frac{a_n-\alpha}{a_n-\beta} = \frac{a-\alpha}{b-\beta}\left(\frac{r\beta +s}{r\alpha +s}\right) ^{n-1}.$$ これを $a_n$ について整理すると, $\{ a_n\}$ の一般項が求まる.
(ii)
$a \neq \alpha = \beta$ のとき. 仮にある自然数 $n > 1$ に対して $a_n = \alpha$ とすると, $a_{n-1}$ は $\alpha = \dfrac{px+q}{rx+s}$ のただ $1$ つの解だから $a_{n-1} = \alpha$ となり, 帰納法より $a = a_1 = \alpha$ となってしまうから, 任意の自然数 $n$ に対して, $a_n \neq \alpha.$
$[3]$ の右辺の分子が $0$ でないことに注意して両辺の逆数をとると, \begin{align*} &\frac{1}{a_{n+1}-\alpha} \\ &= \frac{r\alpha +s}{ps-qr}\cdot\frac{ra_n+s}{a_n-\alpha} \\ &= \frac{r\alpha +s}{ps-qr}\left(\frac{r\alpha +s}{a_n-\alpha} +r\right) \\ &= \frac{(r\alpha +s)^2}{ps-qr}\cdot\frac{1}{a_n-\alpha}+\frac{r(r\alpha +s)}{ps-qr} \cdots [5]. \end{align*} 一方, $\alpha$ は $rx^2-(p-s)x-q = 0$ の重解だから, 解と係数の関係より, \begin{align*} 2\alpha &= \frac{p-s}{r}, & \alpha ^2 &= -\frac{q}{r}. \\ \therefore 2r\alpha &= p-s, & r^2\alpha ^2 &= -qr. \end{align*} \begin{align*} \therefore (r\alpha +s)^2 &= r^2\alpha ^2+2r\alpha\cdot s+s^2 \\ &= -qr+(p-s)s+s^2 \\ &= ps-qr \end{align*} よって, \[\frac{(r\alpha +s)^2}{ps-qr} = 1,\ \frac{r(r\alpha +s)}{ps-qr} = \frac{r(r\alpha +s)}{(r\alpha +s)^2} = \frac{r}{r\alpha +s}.\] これと $[5]$ より, $$\frac{1}{a_{n+1}-\alpha} = \frac{1}{a_n-\alpha}+\frac{r}{r\alpha +s}.$$ よって, $\left\{\dfrac{1}{a_n-\alpha}\right\}$ は初項 $\dfrac{1}{a_1-\alpha} = \dfrac{1}{a-\alpha},$ 公差 $\dfrac{r}{r\alpha +s}$ の等差数列だから, $$\frac{1}{a_n-\alpha} = \frac{1}{a-\alpha}+(n-1)\frac{r}{r\alpha +s}.$$ これを $a_n$ について整理すると, $\{ a_n\}$ の一般項が求まる.
(iii)
$a = \alpha$ のとき. 任意に与えられた自然数 $n$ に対して $a_n = \alpha$ とすると, $$a_{n+1} = \frac{p\alpha +q}{r\alpha +s} = \alpha.$$ よって, $\{ a_n\}$ の一般項は, $$a_n = \alpha.$$ $a = \beta$ のとき. 同様の理由で, $a_n = \beta.$

注意≪定数係数の $2$ 項間 $1$ 次分数型漸化式の特別な場合≫

(II)
$r = 0$ のとき, $$a_{n+1} = \frac{p}{s}a_n+\frac{q}{s}$$ と $(\spadesuit )$ 型の漸化式になる.
(III)
$r \neq 0,$ $s \neq 0,$ $ps-qr = 0$ のとき, $\lambda = \dfrac{p}{r} = \dfrac{q}{s}$ とおくと, $p = \lambda r,$ $q = \lambda s$ より $$a_{n+1} = \frac{\lambda ra_n+\lambda s}{ra_n+s} = \lambda$$ となる.
(IV)
$r \neq 0,$ $s = 0,$ $ps-qr = 0$ のとき, $qr = ps = 0$ と $r \neq 0$ より $q = 0$ だから, $$a_{n+1} = \frac{pa_n}{ra_n} = \frac{p}{r}$$ となる.

$3$ 項間斉次線形漸化式

解法≪定数係数の $3$ 項間斉次線形漸化式≫

 $a,$ $b,$ $p,$ $q \neq 0$ を定数とする. $$\left\{\begin{array}{l} a_1 = a,\ a_2 = b, \\ a_{n+2}+pa_{n+1}+qa_n = 0 \cdots (\natural ) \end{array}\right.$$ で定まる数列 $\{ a_n\}$ の一般項を求める.
$(\natural )$ の特性方程式 $$x^2+px+q = 0$$ の $2$ 解を $\alpha,$ $\beta$ とおく.
解と係数の関係より $$\alpha +\beta = -p,\ \alpha\beta = q$$ だから, \begin{align*} (\natural ) &\iff a_{n+2}-(\alpha +\beta )a_{n+1}+\alpha\beta a_n = 0 \\ &\iff \left\{\begin{array}{l} a_{n+2}-\alpha a_{n+1} = \beta (a_{n+1}-\alpha a_n) \cdots [1], \\ a_{n+2}-\beta a_{n+1} = \alpha (a_{n+1}-\beta a_n) \cdots [2]. \end{array}\right. \end{align*}
(i)
$\alpha \neq \beta$ のとき. $[1]$ より, $\{ a_{n+1}-\alpha a_n\}$ は初項が $a_2-\alpha a_1 = b-\alpha a,$ 公比 $\beta$ の等比数列だから, $$a_{n+1}-\alpha a_n = (b-\alpha a)\beta ^{n-1} \cdots [3].$$ 同様に, $[2]$ より, $$a_{n+1}-\beta a_n = (b-\beta a)\alpha ^{n-1} \cdots [4].$$ $[4]-[3]$ より \[ (\alpha -\beta )a_n = (b-\beta a)\alpha ^{n-1}-(b-\alpha a)\beta ^{n-1}\] だから, $\alpha \neq \beta$ に注意すると, \[ a_n = \frac{b-\beta a}{\alpha -\beta}\alpha ^{n-1}-\frac{b-\alpha a}{\alpha -\beta}\beta ^{n-1}\]
(ii)
$\alpha = \beta$ のとき. $[1]$ より, $$a_{n+2}-\alpha a_{n+1} = \alpha (a_{n+1}-\alpha a_n).$$ $\{ a_{n+1}-\alpha a_n\}$ は初項 $a_2-\alpha a_1 = b-\alpha a,$ 公比 $\alpha$ の等比数列だから, $$a_{n+1}-\alpha a_n = (b-\alpha a)\alpha ^{n-1}.$$ $r \neq 0$ より $\alpha \neq 0$ に注意して, 両辺を $\alpha ^{n+1}$ で割ると, $$\frac{a_{n+1}}{\alpha ^{n+1}}-\frac{a_n}{\alpha ^n} = \frac{b-\alpha a}{\alpha ^2}.$$ よって, $\left\{\dfrac{a_n}{\alpha ^n}\right\}$ は初項 $\dfrac{a_1}{\alpha ^1} = \dfrac{a}{\alpha},$ 公差 $\dfrac{b-\alpha a}{\alpha ^2}$ の等差数列だから, \begin{align*} \frac{a_n}{\alpha ^n} &= \frac{a}{\alpha}+(n-1)\frac{b-\alpha a}{\alpha ^2}. \\ \therefore a_n &= a\alpha ^{n-1}+(b-\alpha a)(n-1)\alpha ^{n-2}. \end{align*}

連立漸化式

解法≪連立 $2$ 項間斉次線型漸化式≫

 $a,$ $b,$ $p,$ $q,$ $r,$ $s$ を定数とする. $$\left\{\begin{array}{l} a_1 = a,\ b_1 = b, \\ a_{n+1} = pa_n+qb_n \cdots (\sharp ), \\ b_{n+1} = ra_n+sb_n \cdots (\flat ) \end{array}\right.$$ で定まる数列 $\{ a_n\},$ $\{ b_n\}$ の一般項を求める $2$ つの方法を紹介する.
(1)
$(\sharp )$ より, $$qb_n = a_{n+1}-pa_n \cdots [1].$$ ここで $n$ を $n+1$ に置き換えると, $$qb_{n+1} = a_{n+2}-pa_{n+1} \cdots [2]$$ $[1],$ $[2]$ を $q\times (\flat )$ に代入すると, \begin{align*} & a_{n+2}-pa_{n+1} = qra_n+s(a_{n+1}-pa_n). \\ &\therefore a_{n+2}-(p+s)a_{n+1}+(ps-qr)a_n = 0. \end{align*} よって, $(\spadesuit )$ 型の漸化式の解法より, $\{ a_n\}$ の一般項が求まる.
$a_n,$ $a_{n+1}$ を $(\sharp )$ に代入して $b_n$ について整理すると, $\{ b_n\}$ の一般項が求まる.
(2)
$\{ a_n+\lambda b_n\}$ が等比数列となるような定数 $\lambda$ を求める:
$\lambda$ を定数として $a_{n+1}+\lambda b_{n+1}$ に $(\sharp ),$ $(\flat )$ を代入すると, \begin{align*} a_{n+1}+\lambda b_{n+1} &= (p+\lambda r)a_n+(q+\lambda s)b_n \\ &= (p+\lambda r)\left( a_n+\frac{q+\lambda s}{p+\lambda r}b_n\right). \end{align*} よって, $\lambda$ を $x$ の方程式 $$x = \frac{q+sx}{p+rx} \cdots (\ast )$$ の解とすると, $\{ a_n+\lambda b_n\}$ は初項 $a_1+\lambda b_1 = a+\lambda b,$ 公比 $p+\lambda r$ の等比数列である.
$(\ast )$ の $2$ 解を $\alpha,$ $\beta$ とおく. このとき, $$\left\{\begin{array}{l} a_n+\alpha b_n = (a+\alpha b)(p+\alpha r)^{n-1} \cdots [1], \\ a_n+\beta b_n = (a+\beta b)(p+\beta r)^{n-1} \cdots [2]. \end{array}\right.$$
(i)
$\alpha \neq \beta$ のとき, $[1],$ $[2]$ を $a_n,$ $b_n$ について解くと, $\{ a_n\},$ $\{ b_n\}$ の一般項が求まる.
(ii)
$\alpha = \beta \neq 0$ のとき, $[1],$ $(\sharp )$ を $a_{n+1}$ について解くと, $$a_{n+1} = \frac{\alpha p-q}{\alpha}a_n+\frac{q(a+\alpha b)}{\alpha}(p+\alpha r)^{n-1}.$$ $(\diamondsuit )$ 型の漸化式の解法より, $\{ a_n\}$ の一般項が求まる.
$a_n,$ $a_{n+1}$ を $(\sharp )$ に代入して $b_n$ について整理すると, $\{ b_n\}$ の一般項が求まる.
(iii)
$\alpha = \beta = 0$ のとき, $[1],$ $[2]$ より, $$a_n = ap^{n-1}.$$ $a_n,$ $a_{n+1}$ を $(\sharp )$ に代入して $b_n$ について整理すると, $\{ b_n\}$ の一般項が求まる.

問題

線形漸化式

$2$ 項間線形漸化式

問題≪ハノイの塔≫

 地面に $3$ 本の棒 A, B, C が立てられており, 棒 A に穴の開いた半径の異なる $n$ 枚の円盤が半径の大きい順に通されている. $1$ 本の棒の最も上にある円盤を別の棒の最も上に移す操作を $1$ 手と数え, $1$ 本の棒の最も上にある $n$ 枚の円盤を別の棒の最も上に移すための手数の最小値を $a_n$ とおく. ただし, いずれの段階においても小さい円盤の上に大きい円盤は置かないとする.
(1)
任意の自然数 $n$ に対して $a_{n+1} = 2a_n+1$ が成り立つことを説明せよ.
(2)
$a_n$ を $n$ で表せ.

解答例

(1)
棒 A に通された $n+1$ 枚の円盤を棒 B に移すためには, まず上の $n$ 枚の円盤を棒 C に移し, 次に棒 A に残された円盤を棒 B に移し, 最後に棒 C に移された $n$ 枚の円盤を棒 B に移す必要がある. \begin{align*} \therefore a_{n+1} &= a_n+1+a_n \\ &= 2a_n+1 \cdots [1]. \end{align*}
(2)
$\alpha = 2\alpha +1 \cdots [2]$ を解くと, $\alpha = -1.$
$[1]-[2]$ より, $$a_{n+1}-\alpha = 2(a_n-\alpha ).$$ ここに $\alpha = -1$ を代入すると, $$a_{n+1}+1 = 2(a_n+1).$$ よって, $\{ a_n+1\}$ は公比 $2$ の等比数列である.
$a_1 = 1$ より, この初項は $a_1+1 = 2$ だから, \begin{align*} a_n+1 &= 2\cdot 2^{n-1} = 2^n \\ \therefore a_n &= 2^n-1. \end{align*}

解説・方針

  • 漸化式を立てて「ハノイの塔」と呼ばれるパズルの手数の最小値を求める場合の数と数列の融合問題.
  • $n+1$ 枚の場合に, 円盤を $n$ 枚のかたまりと $1$ 枚に分けて考えると $n$ 枚の場合が現れ, $a_n,$ $a_{n+1}$ の関係式が得られる. この方法は, 漸化式を立てて場合の数を問題の定石の $1$ つと言える.

問題≪確率の $2$ 項間線形漸化式≫

 $1$ 個のさいころを $n$ 回投げるとき, $1$ の目が偶数回出る確率 $p_n$ を求めよ.

解答例

 明らかに, $p_1 = \dfrac{5}{6}.$
さいころを $n+1$ 回投げるときに $1$ の目が偶数回出るのは
(i)
初めの $n$ 回で $1$ の目が偶数回出て $n+1$ 回目に $1$ の目が出ない場合
(ii)
初めの $n$ 回で $1$ の目が奇数回出て $n+1$ 回目に $1$ の目が出る場合
のいずれかであるから, \[ p_{n+1} = p_n\cdot\frac{5}{6}+(1-p_n)\frac{1}{6}\] すなわち \[ p_{n+1} = \frac{2}{3}p_n+\frac{1}{6}\] が成り立つ. これを変形すると, \[ p_{n+1}-\frac{1}{2} = \frac{2}{3}\left( p_n-\frac{1}{2}\right)\] となるから, $\left\{ p_n-\dfrac{1}{2}\right\}$ は初項 $p_1-\dfrac{1}{2} = \dfrac{1}{3},$ 公比 $\dfrac{2}{3}$ の等比数列である. よって, \[ p_n-\frac{1}{2} = \frac{1}{3}\left(\frac{2}{3}\right) ^{n-1}\] であるから, \[ p_n = \frac{1}{2}+\frac{1}{3}\left(\frac{2}{3}\right) ^{n-1}.\]

問題≪円で分割された領域の個数≫

 どの $2$ つも $2$ 点で交わり, どの $3$ つも共有点を持たない $n$ 個の円によって分けられた平面上の領域の個数 $a_n$ を求めよ.

解答例

 $a_1 = 2.$
条件を満たす $n$ 個の円 $C_1,$ $\cdots,$ $C_n$ に条件を満たす円 $C_{n+1}$ を $1$ 個加えると, $C_{n+1}$ は $C_1,$ $\cdots,$ $C_n$ のそれぞれと $2$ 点で交わり, その隣接する交点を結ぶ $C_{n+1}$ 上の弧それぞれによって領域が $1$ つ増えるから, \begin{align*} a_{n+1} &= a_n+2n. \\ \therefore a_{n+1}-a_n &= 2n. \end{align*} よって, $n \geqq 2$ のとき, \begin{align*} a_n &= a_1+\sum\limits_{i = 1}^{n-1}2i \\ &= 2+2\sum\limits_{i = 1}^{n-1}i \\ &= 2+2\cdot\frac{1}{2}(n-1)n \\ &= n^2-n+2. \end{align*} $1^2-1+2 = 2$ より, これは $n = 1$ のときも成り立つ. ゆえに, 任意の自然数 $n$ に対して, $$a_n = n^2-n+2.$$

問題≪$a_{n+1} = pa_n+qr^n$ 型の漸化式≫

 $a_1 = 2,$ $a_{n+1} = 4a_n+2^{n+1} \cdots (\ast )$ で定まる数列 $\{ a_n\}$ の一般項を求めよ.

解答例

 $(\ast )$ の両辺を $2^{n+1} \neq 0$ で割ると, $$\frac{a_{n+1}}{2^{n+1}} = 2\cdot\frac{a_n}{2^n}+1.$$ この辺々から $x = 2x+1$ の解 $x = -1$ を引くと, $$\frac{a_{n+1}}{2^{n+1}}+1 = 2\left(\frac{a_n}{2^n}+1\right).$$ よって, $\left\{\dfrac{a_n}{2^n}+1\right\}$ は初項 $\dfrac{a_1}{2^1}+1 = \dfrac{2}{2}+1 = 2,$ 公比 $2$ の等比数列だから, \begin{align*} \frac{a_n}{2^n}+1 &= 2^n. \\ \therefore\frac{a_n}{2^n} &= 2^n-1. \end{align*} 両辺に $2^n$ を掛けると, $$a_n = 4^n-2^n.$$

問題≪$a_{n+1} = \dfrac{pa_n}{ra_n+s}$ 型の漸化式≫

 $a_1 = 1,$ $a_{n+1} = \dfrac{a_n}{a_n+2} \cdots (\ast )$ で定まる数列 $\{ a_n\}$ の一般項を求めよ.

解答例

(i)
仮定より, $a_1 = 1 > 0.$
(ii)
任意に与えられたある自然数 $n$ に対して, $a_n > 0$ を仮定すると, $a_n+2 > 0$ より, $$a_{n+1} = \dfrac{a_n}{a_n+2} > 0.$$
(i), (ii) より, 任意の自然数 $n$ に対して, $a_n > 0.$
このことに注意して, $(\ast )$ の両辺の逆数をとると, $$\frac{1}{a_{n+1}} = \frac{2}{a_n}+1.$$ この辺々から $x = 2x+1$ の解 $x = -1$ を引くと, $$\frac{1}{a_{n+1}}+1 = 2\left(\frac{1}{a_n}+1\right).$$ よって, $\left\{\dfrac{1}{a_n}+1\right\}$ は初項 $\dfrac{1}{a_1}+1 = \dfrac{1}{1}+1 = 2,$ 公比 $2$ の等比数列だから, \begin{align*} \frac{1}{a_n}+1 &= 2^n. \\ \therefore\frac{1}{a_n} &= 2^n-1. \end{align*} この両辺の逆数をとると, $$a_n = \frac{1}{2^n-1}.$$

$3$ 項間線形漸化式

問題≪並び替えに関するフィボナッチ数列≫

 $1$ 列に並んだ $n$ 人をそれぞれが動かないか隣に移るように並び替える方法の総数を $a_n$ とおく.
(1)
任意の自然数 $n$ に対して $a_{n+2} = a_{n+1}+a_n$ が成り立つことを説明せよ.
(2)
数列 $\{ a_{n+1}-\alpha a_n\},$ $\{ a_{n+1}-\beta a_n\}$ がそれぞれ公比 $\beta,$ $\alpha$ の等比数列となるような定数 $\alpha,$ $\beta$ ($\alpha < \beta$)の値を求めよ.
(3)
$2-\alpha = \beta ^2,$ $2-\beta = \alpha ^2$ に注意して, $a_n$ を求めよ.

解答例

(1)
$n+2$ 人の並び替えを考える. 横から見て右端の人が動くかどうかによって, 次の場合に分ける.
(i)
右端の人が動かないとき. 並び替えの方法は, その左側の $n+1$ 人を並び替える $a_{n+1}$ 通りある.
(ii)
右端の人が動くとき. 条件より, 右端の人はその隣の人と入れ替わるしかない.
よって, 並び替えの方法は, 残りの $n$ 人を並び替える $a_n$ 通りある.
(i), (ii) は排反だから, $n+2$ 人を並び替える方法の総数は \[ a_{n+2} = a_{n+1}+a_n \quad \cdots [1].\]
(2)
数列 $\{ a_{n+1}-\alpha a_n\},$ $\{ a_{n+1}-\beta a_n\}$ がそれぞれ公比 $\beta,$ $\alpha$ の等比数列であるとき, \begin{align*} a_{n+2}-\alpha a_{n+1} &= \beta (a_{n+1}-\alpha a_n), \\ a_{n+2}-\beta a_{n+1} &= \alpha (a_{n+1}-\beta a_n). \end{align*} となるから, \[ a_{n+2} = (\alpha +\beta )a_{n+1}-\alpha\beta a_n \quad \cdots [2].\] $[1],$ $[2]$ より, \[\alpha +\beta = 1,\quad \alpha\beta = -1\] が成り立てば良い. このとき, $\alpha,$ $\beta$ は $2$ 次方程式 $x^2-x-1 = 0$ の解だから, \[\alpha = \frac{1-\sqrt 5}{2}, \quad \beta = \frac{1+\sqrt 5}{2}.\]
(3)
明らかに, \[ a_1 = 1,\quad a_2 = 2.\] 数列 $\{ a_{n+1}-\alpha a_n\},$ $\{ a_{n+1}-\beta a_n\}$ の初項はそれぞれ, \begin{align*} a_2-\alpha a_1 = 2-\alpha &= \frac{3+\sqrt 5}{2} = \beta ^2, \\ a_2-\beta a_1 = 2-\beta &= \frac{3-\sqrt 5}{2} = \alpha ^2. \end{align*} よって, $\alpha,$ $\beta$ の取り方から, \begin{align*} a_{n+1}-\alpha a_n = \beta ^{n+1} \quad \cdots [3], \\ a_{n+1}-\beta a_n = \alpha ^{n+1} \quad \cdots [4]. \end{align*} $[3]-[4]$ より, \[ (\beta -\alpha )a_n = \beta ^{n+1}-\alpha ^{n+1}.\] $\beta -\alpha = \sqrt 5$ より, \[ a_n = \frac{1}{\sqrt 5}\left(\left(\frac{1+\sqrt 5}{2}\right) ^{n+1}-\left(\frac{1-\sqrt 5}{2}\right) ^{n+1}\right).\]

問題≪漸化式で定まる数列の余りの周期性≫

 漸化式 $a_1 = a_2 = 1,$ $a_{n+2} = a_{n+1}+a_n$ で定まる数列 $\{ a_n\}$ について, $a_n$ が $10$ の倍数であるための必要十分条件を求めよ.

解答例

 $0$ でない整数 $b$ による割り算について $a_k$ の余りが $r_k$ のとき $a_{k+2} = a_{k+1}+a_k$ の余りは $r_{k+1}+r_k$ の余りに等しいことを使う.
(i)
$a_n$ を $2$ で割った余りを $x_n$ とおくと \begin{align*} x_1 &= 1, & x_2 &= 1, & x_3 &= 0, \\ x_4 &= 1, & x_5 &= 1, & &\dots \end{align*} となるから, 各正の整数 $m$ に対して \[ x_{3m-2} = x_{3m-1} = 1,\ x_{3m} = 0\] となる. よって, $a_n$ は $2$ の倍数 $\iff$ $n$ は $3$ の倍数.
(ii)
$a_n$ を $5$ で割った余りを $y_n$ とおくと \begin{align*} &y_1 = 1,\ y_2 = 1,\ y_3 = 2,\ y_4 = 3,\ y_5 = 0 \\ &y_6 = 1,\ y_7 = 1,\ \dots \end{align*} となるから, 各正の整数 $m$ に対して \[ y_{5m-4} = y_{5m-3} = 1,\ y_{5m-2} = 2,\ y_{5m-1} = 3,\ y_{5m} = 0\] となる. よって, $a_n$ は $5$ の倍数 $\iff$ $n$ は $5$ の倍数.
(i), (ii) より,
$a_n$ は $10$ の倍数$\iff$ $a_n$ は $2$ の倍数かつ $5$ の倍数
$\iff$ $n$ は $3$ の倍数かつ $5$ の倍数
$\iff$ $n$ は $15$ の倍数.
ゆえに, 求める条件は, $n$ が $15$ の倍数であること.

解説・方針

  • 漸化式で定まる数列の余りの周期性に関する典型問題.
  • $10 = 2\cdot 5$ より, $a_n$ が $2,$ $5$ の倍数であるための条件をそれぞれ調べる. 小さい番号 $n$ について $a_n$ を $2,$ $5$ で割った余りを具体的に計算してみると, その周期性が見えてくる.
  • 本問の数列はフィボナッチ数列だから,「和の余りは余りの和の余り」であることを使う. ちなみに,「積の余りは余りの積の余り」であることも使えば, $a_{n+2} = a_{n+1}+2a_n$ のような漸化式についても同様の問題が解ける.

問題≪フィボナッチ数列の加法定理≫

 数列 $\{ F_n\}$ を \[ F_0 = 0, \quad F_1 = 1, \quad F_{n+2} = F_n+F_{n+1}\] により定める. 任意の非負整数 $m,$ $n$ に対して, 次が成り立つことを示せ.
(1)
$F_{m+n+1} = F_mF_n+F_{m+1}F_{n+1} \quad \cdots [\ast ].$ 
(2)
$0 \leqq m \leqq n$ のとき, $m$ が $n$ を割り切るならば, $F_m$ は $F_n$ を割り切る.
(3)
$n \neq 4$ のとき, $F_n$ が素数ならば $n$ は素数である.
(4)
$F_n,$ $F_{n+1}$ は互いに素である.
(5)
(2) の逆.

解答例

(1)
$m$ を固定し, $n$ に関する帰納法で \[ F_{m+n+1} = F_mF_n+F_{m+1}F_{n+1} \quad \cdots [\ast ]_n\] を示す.
(i)
$F_0 = 0,$ $F_1 = 1,$ $F_2 = 0+1 = 1$ より \begin{align*} &F_mF_0+F_{m+1}F_1 = F_{m+1}, \\ &F_mF_1+F_{m+1}F_2 = F_m+F_{m+1} = F_{m+2} \end{align*} となるから, $[\ast ]_0,$ $[\ast ]_1$ が成り立つ.
(ii)
与えられた非負整数 $n$ に対して, $[\ast ]_n,$ $[\ast ]_{n+1}$ の成立を仮定する. このとき, \begin{align*} &F_{m+n+3} \\ &= F_{m+n+1}+F_{m+n+2} \\ &= F_mF_n+F_{m+1}F_{n+1}+F_mF_{n+1}+F_{m+1}F_{n+2} \\ &= F_m(F_n+F_{n+1})+F_{m+1}(F_{n+1}+F_{n+2}) \\ &= F_mF_{n+2}F_{m+1}F_{n+3} \end{align*} となり, $[\ast ]_{n+2}$ が成り立つ.
以上より, 任意の非負整数 $m,$ $n$ に対して $[\ast ]$ が成り立つ.
(2)
任意の非負整数 $m,$ $q$ に対して $F_{mq}$ が $F_m$ で割り切れることを示せば良い.
(I)
$F_{0\cdot q} = F_0 = 0$ は $F_0 = 0$ で割り切れるから, $m = 0$ のとき成り立つ.
(II)
正整数 $m$ を固定し, $q$ に関する帰納法で示す.
(i)
$F_{m\cdot 0} = F_0 = 0$ は $F_m$ で割り切れるから, $q = 0$ のとき成り立つ.
(ii)
与えられた非負整数 $q$ に対して $F_{mq}$ が $F_m$ で割り切れるとする. このとき, $d = F_{mq}/F_m$ は整数だから, \begin{align*} F_{m(q+1)} &= F_{mq+m-1+1} \\ &= F_{mq}F_{m-1}+F_{mq+1}F_m \quad (\because (1)) \\ &= dF_mF_{m-1}+F_{mq+1}F_m \\ &= F_m(dF_{m-1}+F_{mq+1}) \end{align*} は $F_m$ で割り切れる.
以上より, 任意の非負整数 $m,$ $q$ に対して $F_{mq}$ は $F_m$ で割り切れる. 題意が示された.
(3)
$4$ でない非負整数 $n$ に対して, $n$ が素数でないならば $F_n$ は素数でないことを示す. $F_0 = 0,$ $F_1 = 1$ は素数でないから, $n$ を $0,$ $1,$ $4$ でも素数でない非負整数とする. このとき, $2$ より大きい整数 $\ell,$ $m$ を用いて $n = \ell m$ と書ける. (2) で示したことから $F_n = F_{\ell m}$ は $F_\ell$ で割り切れる. また, フィボナッチ数列の単調増加性より $1 = F_2 < F_\ell < F_n.$ よって, $F_n$ は $1$ でも $F_n$ でもない正の約数 $F_\ell$ を持つから, 素数でない. ゆえに, 対偶は真だから, 示すべき命題も真である.
(4)
$d$ を $F_n,$ $F_{n+1}$ の任意の正の公約数とする. $n > 1$ のとき, $d$ は $F_{n+1}-F_n = F_{n-1}$ を割り切る. これを繰り返すと, $d$ は $F_1 = 1$ を割り切るから, $d = 1.$ ゆえに, $F_n,$ $F_{n+1}$ は互いに素である.
(5)
(I)
$m = 0$ のとき. $F_0 = 0$ が $F_n$ を割り切るならば, $F_n = 0$ より, $n = 0$ となるから, $0$ は $n$ を割り切る.
(II)
$m > 0$ のとき. $n$ を $m$ で割った商を $q,$ 余りを $r$ とおくと, \[ n = mq+r, \quad 0 \leqq r < m.\] $m \leqq n$ より $mq \geqq m > 0$ であることに注意すると, \begin{align*} F_n &= F_{mq-1+r+1} \\ &= F_{mq-1}F_r+F_{mq}F_{r+1} \quad (\because (1)). \end{align*} $F_{mq-1}$ は, (4) より $F_{mq}$ と互いに素だから, $F_m$ と互いに素でなければならない. また, (2) より, $F_m$ は $F_{mq}$ を割り切る. よって, $F_m$ が $F_n$ を割り切るとすると, $F_m$ は $F_r$ を割り切る. このとき, $r < m$ より $F_r \leqq F_m$ であることに注意すると, $F_r = 0$ より $r = 0$ となるから, $m$ は $n$ を割り切る.
題意が示された.

解説

  • フィボナッチ数列 $\{ F_n\}$ の項は, フィボナッチ数(Fibonacci number)と呼ばれ, 植物の葉や花びらの数など自然界でよく現れる.
  • 少しボリュームがあるので, 入試問題で出題されるとすれば, (1) のみか, (1)→(2) か, (1)→(2)→(3) か, (1)→(2)→(4)→(5) の形で出されるであろう.
  • 示した結果を用いてフィボナッチ数の素因数分解や最大公約数を求める問題も考えられる.
  • (1) は, しばしばフィボナッチ数列の加法定理(addition theorem)と呼ばれる.
  • (5) の証明には, (2) の結果を使っていることに注意する.
  • ユークリッドの互除法により, (5) より強い次の定理が示される: 整数 $a,$ $b$ の最大公約数を $(a,\ b)$ で表すとき, $n \neq 0$ ならば, $(F_m,\ F_n) = F_{(m,\ n)}$ が成り立つ. 証明は, こちらを参照.

連立漸化式

問題≪順列に関する場合の数の連立漸化式≫

 $3$ 種類の文字 A, B, C を使って $n$ 文字から成る文字列を作るとき, 任意の隣り合う $2$ 文字の少なくとも一方が A である場合の数を $x_n$ とおく. そのうち, 末尾が A, B, C である場合の数をそれぞれ $a_n,$ $b_n,$ $c_n$ とおく. ただし, $x_1 = 3,$ $a_1 = b_1 = c_1 = 1$ とする.
(1)
$a_{n+1},$ $b_{n+1},$ $c_{n+1}$ を $a_n,$ $b_n,$ $c_n$ で表せ.
(2)
$a_n$ を求めよ.
(3)
$x_n$ を求めよ.

解答例

(1)
$n$ 番目の文字が A でも B でも C でも $n+1$ 番目の文字を A とすることができるから, $$a_{n+1} = a_n+b_n+c_n \cdots [1].$$ $n$ 番目の文字が A の場合にのみ $n+1$ 番目の文字を A 以外とすることができるから, $$b_{n+1} = c_{n+1} = a_n \cdots [2].$$
(2)
$(\ast )$ において $n$ を $n+1$ に置き換えると, $$a_{n+2} = a_{n+1}+b_{n+1}+c_{n+1} \cdots [1]'.$$ $[1]'$ に $[2]$ を代入すると, \begin{align*} &a_{n+2} = a_{n+1}+2a_n. \\ \therefore &\left\{\begin{array}{l} a_{n+2}+a_{n+1} = 2(a_{n+1}+a_n) \cdots [3], \\ a_{n+2}-2a_{n+1} = -(a_{n+1}-2a_n) \cdots [4]. \end{array}\right. \end{align*} 末尾が A の $2$ 文字から成る文字列は AA, BA, CA のみだから, $a_2 = 3.$
$[3]$ より, $\{ a_{n+1}+a_n\}$ は初項 $a_2+a_1 = 3+1 = 4,$ 公比 $2$ の等比数列だから, $$a_{n+1}+a_n = 4\cdot 2^{n-1} = 2^{n+1} \cdots [5].$$ $[4]$ より, $\{ a_{n+1}-2a_n\}$ は初項 $a_2-2a_1 = 3-2\cdot 1 = 1,$ 公比 $-1$ の等比数列だから, $$a_{n+1}-2a_n = 1\cdot (-1)^{n-1} = (-1)^{n-1} \cdots [6].$$ $[5]-[6]$ より, \begin{align*} 3a_n &= 2^{n+1}-(-1)^{n-1} = 2^{n+1}+(-1)^n. \\ \therefore a_n &= \frac{2^{n+1}+(-1)^n}{3}. \end{align*}
(3)
$n$ 番目の文字は A, B, C のいずれかだから, \begin{align*} x_n &= a_n+b_n+c_n \\ &= a_{n+1} \\ &= \frac{2^{n+2}+(-1)^{n+1}}{3}. \end{align*}

問題≪入れ替えに関する確率の連立漸化式≫

 白玉 $2$ 個が入った袋 A と黒玉 $2$ 個が入った袋 B がある. 「袋 A から袋 B へ玉を $1$ 個だけ移した後, 袋 B から袋 A へ玉を $1$ 個だけ移す」という操作を $n$ 回繰り返したとき, 袋 A に白玉がちょうど $2$ 個, $1$ 個, $0$ 個入っている確率をそれぞれ $p_n,$ $q_n,$ $r_n$ とおく.
(1)
$p_1,$ $q_1,$ $r_1$ を求めよ.
(2)
$p_{n+1}$ を $p_n,$ $q_n$ で表せ.
(3)
$q_{n+1}$ を求めよ.
(4)
$p_n,$ $q_n,$ $r_n$ を求めよ.

解答例

(1)
$1$ 回目の操作の第 $1$ 段階は白玉を移すしかなく, 袋 B の中は白玉 $1$ 個と黒玉 $2$ 個になる.
第 $2$ 段階で, 白玉を移すと袋 A の中は白玉 $2$ 個になり, 黒玉を移すと袋 A の中は白玉 $1$ 個と黒玉 $1$ 個になり, いずれの場合にも袋 A に白玉が残る.
よって, 求める確率は, $$p_1 = \frac{1}{3},\quad q_1 = \frac{2}{3},\quad r_1 = 0.$$
(2)
$n+1$ 回目の操作後に袋 A の中が白玉 $2$ 個になるのは, 次の $2$ つの場合に限る:
(i)
$n$ 回目の操作後に袋 A に白玉が $2$ 個あり, (袋 A から白玉を移した後,) 袋 B から白玉を移す.
(ii)
$n$ 回目の操作後に袋 A に白玉が $1$ 個だけあり, 袋 A から黒玉を移した後, 袋 B から白玉を移す.
これらは互いに排反だから, \begin{align*} p_{n+1} &= p_n\cdot 1\cdot\frac{1}{3}+q_n\cdot\frac{1}{2}\cdot\frac{1}{3} \\ &= \frac{1}{3}p_n+\frac{1}{6}q_n \cdots [1]. \end{align*}
(3)
袋 A の中の白玉は $2$ 個, $1$ 個, $0$ 個のいずれかだから, $$p_n+q_n+r_n = 1 \cdots [2].$$ $n+1$ 回目の操作後に袋 A の中が白玉 $1$ 個だけになるのは, 次の $3$ つの場合に限る:
(i)
$n$ 回目の操作後に袋 A に白玉が $2$ 個あり, (袋 A から白玉を移した後,) 袋 B から黒玉を移す.
(ii)
$n$ 回目の操作後に袋 A に白玉が $1$ 個だけあり, 袋 A から白玉を移した後に袋 B から白玉を移すか, 袋 A から黒玉を移した後に袋 B から黒玉を移す.
(iii)
$n$ 回目の操作後に袋 A に白玉がなく, (袋 A から黒玉を移した後,) 袋 B から白玉を移す.
これらは互いに排反だから, \begin{align*} q_{n+1} &= p_n\cdot 1\cdot\frac{2}{3}+q_n\left(\frac{1}{2}\cdot\frac{2}{3}+\frac{1}{2}\cdot\frac{2}{3}\right) \\ &\qquad +r_n\cdot 1\cdot\frac{2}{3} \\ &= \frac{2}{3}(p_n+q_n+r_n) \quad (\because [2]) \\ &= \frac{3}{2} \cdots [3]. \end{align*}
(4)
$q_1 = \dfrac{2}{3},$ $[3]$ より, 任意の自然数 $n$ に対して, $$q_n = \frac{2}{3} \cdots [3]'.$$ $[3]'$ を $[1]$ に代入すると, \begin{align*} p_{n+1} &= \frac{1}{3}p_n+\frac{1}{9} \cdots [4]. \\ \alpha &= \frac{1}{3}\alpha +\frac{1}{9} \cdots [5] \end{align*} を解くと, $$\alpha = \frac{1}{6} \cdots [6].$$ $[4]-[5]$ より, $$p_{n+1}-\alpha = \frac{1}{3}(p_n-\alpha ).$$ $[6]$ を代入すると, $$p_{n+1}-\frac{1}{6} = \frac{1}{3}\left(p_n-\frac{1}{6}\right).$$ よって, $\left\{ p_n-\dfrac{1}{6}\right\}$ は初項 $p_1-\dfrac{1}{6} = \dfrac{1}{3}-\dfrac{1}{6} = \dfrac{1}{6},$ 公比 $\dfrac{1}{3}$ の等比数列だから, \begin{align*} p_n-\frac{1}{6} &= \frac{1}{6}\left(\frac{1}{3}\right) ^{n-1}. \\ \therefore p_n &= \frac{1}{6}\left(1+\left(\frac{1}{3}\right) ^{n-1}\right). \end{align*} さらに, \begin{align*} r_n &= 1-p_n-q_n \quad (\because [2]) \\ &= 1-\frac{1}{6}\left(1+\left(\frac{1}{3}\right) ^{n-1}\right) -\frac{2}{3} \\ &= \frac{1}{6}\left( 1-\left(\frac{1}{3}\right) ^{n-1}\right). \end{align*}

問題≪ガウス整数の累乗の実部・虚部≫

 $\sqrt{-1}$ を虚数単位とする.
(1)
各自然数 $n$ に対して $(1+\sqrt{-1})^n = a_n+b_n\sqrt{-1} \cdots (\sharp )$ を満たす整数 $a_n,$ $b_n$ が存在することを示し, $a_{n+1},$ $b_{n+1}$ を $a_n,$ $b_n$ で表せ.
(2)
数列 $\{ a_n-b_n\sqrt{-1}\}$ の一般項を求めよ.
(3)
数列 $\{ a_n\},$ $\{ b_n\}$ の一般項を求めよ.

解答例

(1)
(i)
$n = 1$ のとき. $(1+\sqrt{-1})^1 = 1+\sqrt{-1}$ より, $(\sharp )$ を満たす整数 $a_n,$ $b_n$ が $a_1 = b_1 = 1$ として確かに存在する.
(ii)
任意に与えられたある自然数 $n$ に対して $(\sharp )$ を満たす整数 $a_n,$ $b_n$ の存在を仮定すると, \begin{align*} (1+\sqrt{-1})^{n+1} &= (1+\sqrt{-1})^n(1+\sqrt{-1}) \\ &= (a_n+b_n\sqrt{-1})(1+\sqrt{-1}) \\ &= (a_n-b_n)+(a_n+b_n)\sqrt{-1} \end{align*} より, $(1+\sqrt{-1})^{n+1} = a_{n+1}+b_{n+1}\sqrt{-1}$ を満たす整数 $a_{n+1},$ $b_{n+1}$ が $a_{n+1} = a_n-b_n \cdots [1],$ $b_{n+1} = a_n+b_n \cdots [2]$ として確かに存在する.
(i), (ii) より, 任意の自然数 $n$ に対して $(\sharp )$ を満たす整数 $a_n,$ $b_n$ が存在し, $[1],$ $[2]$ が成り立つ.
(2)
$[1]-[2]\times\sqrt{-1}$ より, \begin{align*} a_{n+1}-b_{n+1}\sqrt{-1} &= (a_n-b_n)-(a_n+b_n)\sqrt{-1} \\ &= (1-\sqrt{-1})(a_n-b_n\sqrt{-1}). \end{align*} よって, $\{ a_n-b_n\sqrt{-1}\}$ は初項 $a_1-b_1\sqrt{-1} = 1-\sqrt{-1},$ 公比 $1-\sqrt{-1}$ の等比数列だから, \begin{align*} a_n-b_n\sqrt{-1} &= (1-\sqrt{-1})(1-\sqrt{-1})^{n-1} \\ &= (1+\sqrt{-1})^n \cdots (\flat ). \end{align*}
(3)
$$a_n+b_n\sqrt{-1} = (1+\sqrt{-1})^n \cdots (\sharp )$$ と $(\flat )$ について, $\dfrac{(\sharp )+(\flat )}{2},$ $\dfrac{(\sharp )-(\flat )}{2\sqrt{-1}}$ より, \begin{align*} a_n &= \frac{(1+\sqrt{-1})^n+(1-\sqrt{-1})^n}{2}, \\ b_n &= \frac{(1+\sqrt{-1})^n-(1-\sqrt{-1})^n}{2\sqrt{-1}} \\ &= -\sqrt{-1}\cdot\frac{(1+\sqrt{-1})^n-(1-\sqrt{-1})^n}{2}. \end{align*}

注意≪Gauss 整数≫

 実部と虚部がともに実数である複素数を ガウス整数(Gaussian integer)と呼ぶ. 一般に, ガウス整数の和, 差, 積もまたガウス整数である.

問題≪ペル方程式と累乗の展開≫

(1)
各正の整数 $n$ に対して \[ (3+2\sqrt 2)^n = x_n+y_n\sqrt 2 \quad \cdots [1]\] を満たす整数 $x_n,$ $y_n$ が存在することを示し, $x_{n+1},$ $y_{n+1}$ を $x_n,$ $y_n$ で表せ.
(2)
数列 $\{ x_n-y_n\sqrt 2\}$ の一般項を求めよ.
(3)
各正の整数 $n$ に対して $(x,\ y) = (x_n,\ y_n)$ は \[ x^2-2y^2 = 1 \quad \cdots [\ast ]\] の整数解であることを示せ.
(4)
$[\ast ]$ の正の整数解 $(x,\ y)$ から定まる整数の組 $(p,\ q) = (3x-4y,\ -2x+3y)$ について, 次が成り立つことを示せ. \[ p^2-2q^2 = 1, \quad 0 \leqq q < y.\]
(5)
$[\ast ]$ の正の整数解は (3) の解の形に表されることを示せ.

解答例

(1)
(i)
$n = 1$ のとき, $[1]$ を満たす整数 $x_n,$ $y_n$ が $x_1 = 3,$ $y_1 = 2$ として確かに存在する.
(ii)
与えられた正の整数 $n$ に対して $[1]$ を満たす整数 $x_n,$ $y_n$ の存在を仮定すると, \begin{align*} &(3+2\sqrt 2)^{n+1} = (3+2\sqrt 2)^n(3+2\sqrt 2) \\ &= (x_n+y_n\sqrt 2)(3+2\sqrt 2) \\ &= (3x_n+4y_n)+(2x_n+3y_n)\sqrt 2 \end{align*} より, $(3+2\sqrt 2)^{n+1} = x_{n+1}+y_{n+1}\sqrt 2$ を満たす整数 $x_{n+1},$ $y_{n+1}$ が \begin{align*} x_{n+1} &= 3x_n+4y_n \quad \cdots [2], \\ y_{n+1} &= 2x_n+3y_n \quad \cdots [3] \end{align*} として確かに存在する.
(i), (ii) より, 任意の正の整数 $n$ に対して $[1]$ を満たす整数 $x_n,$ $y_n$ が存在し, $[2],$ $[3]$ が成り立つ.
(2)
$[2]-[3]\times\sqrt 2$ より, \begin{align*} x_{n+1}-y_{n+1}\sqrt 2 &= (3x_n+4y_n)-(2x_n+3y_n)\sqrt 2 \\ &= (3-2\sqrt 2)(x_n-y_n\sqrt 2). \end{align*} よって, $\{ x_n-y_n\sqrt 2\}$ は初項と公比が $3-2\sqrt 2$ の等比数列だから, \[ x_n-y_n\sqrt 2 = (3-2\sqrt 2)^n.\]
(3)
\begin{align*} &x_n{}^2-2y_n{}^2 = (x_n+y_n\sqrt 2)(x_n-y_n\sqrt 2) \\ &= (3+2\sqrt 2)^n(3-2\sqrt 2)^n \\ &= \big( (3+2\sqrt 2)(3-2\sqrt 2)\big) ^n \\ &= 1^n = 1 \end{align*} だから, $(x,\ y) = (x_n,\ y_n)$ は $[\ast ]$ の整数解である.
(4)
(i)
$[\ast ]$ より, \[ p^2-2q^2 = x^2-2y^2 = 1.\]
(ii)
仮定より $y > 0$ だが, $x^2-2\cdot 1^2 = 1$ の整数解は存在しないから, $y \geqq 2.$ よって, $[\ast ]$ より \[ 9y^2-4x^2 = y^2-4(x^2-2y^2) = y^2-4 \geqq 0\] となるから, \[ q = 3y-2x \geqq 0.\]
(iii)
$y^2+1 > 0$ より $2y^2+1 > y^2$ すなわち $\sqrt{2y^2+1} > y$ だから, \[ q= 3y-2x = 3y-2\sqrt{2y^2+1} < 3y-2y = y.\]
(i)~(iii) より, 題意が示された.
(5)
与えられた $[\ast ]$ の正の整数解 $(x,\ y)$ について \begin{align*} &p_1 = x,\ q_1 = y, \\ &p_{k+1} = 3p_k-4q_k \quad \cdots [5], \\ &q_{k+1} = -2p_k+3q_k \quad \cdots [6] \end{align*} により整数の数列 $\{ p_k\},$ $\{ q_k\}$ を定めると, (4) より $q_k$ は徐々に小さくなっていく. しかし, $y$ 以下の非負整数は有限個だから, ある正の整数 $n$ に対して $q_{n+1} = 0$ となる.
このとき, $p_{n+1} = 1.$
さらに, $[5],$ $[6]$ を $p_k,$ $q_k$ について解くと \begin{align*} p_k &= 3p_{k+1}+4q_{k+1}, \\ q_k &= 2p_{k+1}+3q_{k+1} \end{align*} となり, $(p_n,\ q_n) = (3,\ 2)$ となる. \begin{align*} \begin{array}{ccccccc} {} & {} & (x_1,\ y_1) & \!\!\curvearrowright\!\! & \cdots & \!\!\curvearrowright\!\! & (x_n,\ y_n) \\ {} & {} & \parallel & {} & {} & {} & \parallel \\ (1,\ 0) & {} & (3,\ 2) & {} & {} & {} & (x,\ y) \\ \parallel & {} & \parallel & {} & {} & {} & \parallel \\ (p_{n+1},\ q_{n+1}) & \!\!\curvearrowleft\!\! & (p_n,\ q_n) & \!\!\curvearrowleft\!\! & \dots & \!\!\curvearrowleft\!\! & (p_1,\ q_1) \end{array} \end{align*} よって, (1) における考察から, \[ (x,\ y) = (x_n,\ y_n).\]

解説

 $1$ 以外の平方因子を持たない整数 $d$ に対して, $x^2-dy^2 = \pm 1$ の形の方程式をペル方程式(Pell's equation)と呼ぶ. (4)~(5) は難問だが, (1)~(3) は連立漸化式の標準的な頻出問題なので確実に解きたい. $x^2-dy^2 = \pm 1$ が $1$ つでも整数解を持てば, (1)~(3) の方法で無限個の整数解を構成することができる. $x^2-dy^2 = 1$ は必ず無限個の整数解を持つが, $x^2-dy^2 = -1$ は整数解を持つとは限らない.

問題≪ペル方程式とブラーマグプタの恒等式≫

(1)
$(xu+dyv)^2-d(xv+yu)^2$ を因数分解せよ.
(2)
$u^2-2v^2 = 1$ の整数解を $1$ つ与えよ.
(3)
$x^2-2y^2 = -1$ は無限個の整数解を持つことを示せ.

解答例

(1)
与式を展開して整理すると, \begin{align*} &(xu+dyv)^2-d(xv+yu)^2 \\ &= (x^2u^2+2dxyuv+d^2y^2v^2) \\ &\qquad -(dx^2v^2+2dxyuv+dy^2u^2) \\ &= xu^2-dx^2v^2-dy^2u^2+d^2y^2v^2 \\ &= (x^2-dy^2)(u^2-dv^2) \quad \cdots [1]. \end{align*}
(2)
$(u,\ v) = (3,\ 2)$ は \[ u^2-2v^2 = 1 \quad \cdots [2]\] の $1$ つの整数解を与える.
(3)
$[1]$ に $d = 2,$ $(u,\ v) = (3,\ 2)$ を代入すると, $[2]$ より, \[ x^2-2y^2 = (3x+4y)^2-2(2x+3y)^2.\] また, $(x,\ y) = (1,\ 1)$ は $x^2-2y^2 = -1$ を満たす. よって, 数列 $\{ x_n\},$ $\{ y_n\}$ を \[ x_1 = y_1 = 1,\ x_{n+1} = 3x_n+4y_n,\ y_{n+1} = 2x_n+3y_n\] で定めると, その項の対 $(x_n,\ y_n)$ はすべて $x^2-2y^2 = -1$ の整数解である. $x_{n+1} > x_n$ に注意すると, これらはすべて異なる. ゆえに, $x^2-2y^2 = -1$ は無限個の整数解を持つ.

解説

 (1) の恒等式, 特に (1) において $d = -1$ を代入して得られる恒等式 \[ (xu-yv)^2+(xv+yu)^2 = (x^2+y^2)(u^2+v^2)\] をブラーマグプタの恒等式(Brahmagupta's identity)と呼ぶ.

特殊な漸化式

問題≪階比数列≫

 $a_1 = 1,$ $a_{n+1} = 2^na_n \cdots (\ast )$ で定まる数列 $\{ a_n\}$ の一般項を求めよ.

解答例

(i)
条件より, $a_1 = 1 > 0.$
(ii)
任意に与えられたある自然数 $n$ に対して $a_n > 0$ を仮定すると, $a_{n+1} = 2^na_n > 0.$
(i), (ii) より, 任意の自然数 $n$ に対して, $a_n > 0.$
このことに注意して $(\ast )$ の両辺の逆数をとると, \begin{align*} \log _2a_{n+1} &= \log _22^na_n \\ &= \log _22^n+\log _2a_n \\ &= n+\log _2a_n. \end{align*} $$\therefore\log _2a_{n+1}-\log _2a_n = n.$$ よって, $\log _2a_1 = \log _21 = 0$ より, $n \geqq 2$ のとき, \begin{align*} \log _2a_n &= \log _ 2a_1+\sum\limits _{i = 1}^{n-1}i \\ &= \frac{1}{2}(n-1)n. \\ \therefore a_n &= 2^{(n-1)n/2}. \end{align*} $2^{0\cdot 1/2} = 1$ より, これは $n = 1$ のときも成り立つ.
ゆえに, 任意の自然数 $n$ に対して, $$a_n = 2^{(n-1)n/2}.$$

問題≪数列の和の $3$ 項間漸化式≫

   数列 $\{ a_n\}$ の初項から第 $n$ 項までの和を $S_n$ とおく.
$a_1 = 1,$ $a_2 = 4,$ $a_{n+1} = S_{n+2}-4S_{n+1}+5S_n \cdots (\ast )$
が成り立つとき,
(1)
数列 $\{ S_n\}$ の一般項を求めよ.
(2)
数列 $\{ a_n\}$ の一般項を求めよ.

解答例

(1)
$(\ast )$ に $a_{n+1} = S_{n+1}-S_n$ を代入すると, \begin{align*} &S_{n+1}-S_n = S_{n+2}-4S_{n+1}+5S_n. \\ \therefore&S_{n+2}-5S_{n+1}+6S_n = 0. \end{align*} 変形すると, $$\left\{\begin{array}{l} S_{n+2}-2S_{n+1} = 3(S_{n+1}-2S_n), \\ S_{n+2}-3S_{n+1} = 2(S_{n+1}-3S_n). \end{array}\right.$$ また, $S_1 = a_1 = 1,$ $S_2 = a_1+a_2 = 5.$
よって, $\{ S_{n+1}-2S_n\},$ $\{ S_{n+1}-3S_n\}$ はそれぞれ初項 $S_2-2S_1 = 3,$ $S_2-3S_1 = 2,$ 公比 $3,$ $2$ の等比数列だから, $$\left\{\begin{array}{l} S_{n+1}-2S_{n+1} = 3^n \cdots [1], \\ S_{n+1}-3S_{n+1} = 2^n \cdots [2]. \end{array}\right.$$ $[1]-[2]$ より, $$S_n = 3^n-2^n.$$
(2)
$n \geqq 2$ のとき, \begin{align*} a_n &= S_n-S_{n-1} \\ &= (3^n-3^{n-1})-(2^n-2^{n-1}) \\ &= (3-1)3^{n-1}-(2-1)2^{n-1} \\ &= 2\cdot 3^{n-1}-2^{n-1}. \end{align*} $2\cdot 3^0-2^0 = 1$ より, これは $n = 1$ のときも成り立つ.
ゆえに, 任意の自然数 $n$ に対して, $$a_n = 2\cdot 3^{n-1}-2^{n-1}.$$

問題≪有理式係数の $2$ 項間漸化式≫

 $a_1 = \dfrac{1}{2},$ $(n+2)a_{n+1} = na_n \cdots (\ast )$ で定まる数列 $\{ a_n\}$ の一般項を求めよ.

解答例

 $(\ast )$ の両辺に $n+1$ を掛けると, $$(n+2)(n+1)a_{n+1} = (n+1)na_n.$$ よって, $b_n = (n+1)na_n$ とおくと, $$b_{n+1} = b_n.$$ これと $b_1 = 2\cdot 1\cdot a_1 = 1$ より, 任意の自然数 $n$ に対して, \begin{align*} b_n &= 1. \\ \therefore a_n &= \frac{1}{n(n+1)}. \end{align*}

問題≪$\sqrt n$ の整数部分を表す数列の漸化式≫

 関数 $f(x)$ を \[ f(x) = \begin{cases} 1 & (x = 0), \\ 0 & (x \neq 0) \end{cases}\] により定め, 数列 $\{ a_n\}$ を \[ a_n = 1, \quad a_{n+1} = a_n+f((a_n+1)^2-n-1)\] により定める. このとき, $a_n = [\sqrt n] \quad (n \geqq 1)$ であることを示せ. ただし, $[x]$ は $x$ を越えない最大の整数を表す.
[東京女大]

略解

 数学的帰納法による.

問題≪チェビシェフの多項式の漸化式≫

\[ f_0(x) = 1, \quad f_1(x) = x, \quad f_{n+2}(x) = 2xf_{n+1}(x)-f_n(x)\] により多項式 $f_n(x)\ (n \geqq 0)$ を順次定めていく.
(1)
任意の非負整数 $n,$ 実数 $\theta$ に対して \[ f_n(\cos\theta ) = \cos n\theta \quad \cdots [P_n]\] が成り立つことを示せ.
(2)
$f_n(x)$ を $x$ の関数とみなすとき, $n$ が偶数のとき $f_n(x)$ が偶関数であり, $n$ が奇数のとき $f_n(x)$ は奇関数であることを示せ.
(3)
$m$ を正の数とする. $f_m(x) = 0$ の実数解を余弦の値で表せ.
(4)
$n \geqq 2$ のとき, $n$ の正の約数 $m$ について $n/m$ が奇数であるならば, $f_n(x)$ は $f_m(x)$ で割り切れることを示せ.

解答例

(1)
(i)
$f_0(\cos\theta ) = 1 = \cos 0\theta,$ $f_1(\cos\theta ) = \cos\theta$ から, $[P_0],$ $[P_1]$ が成り立つ.
(ii)
与えられた非負整数 $n$ に対して $[P_n],$ $[P_{n+1}]$ が成り立つとすると, 和積の公式により \begin{align*} f_{n+2}(\cos\theta ) &= 2\cos\theta f_{n+1}(\cos\theta )-f_n(\cos\theta ) \\ &= 2\cos\theta\cos (n+1)\theta -\cos n\theta \\ &= \cos (n+2)\theta +\cos n\theta -\cos n\theta \\ &= \cos (n+2)\theta \end{align*} となり, $[P_{n+2}]$ が成り立つ.
(i), (ii) から, 任意の非負整数 $n$ に対して $[P_n]$ が成り立つ.
(2)
\[ f_n(-x) = (-1)^nf_n(x) \quad \cdots [Q_n]\] が成り立つことを示せば良い.
(i)
$f_0(-x) = 1 = f_0(x),$ $f_1(-x) = -x = -f_1(x)$ から, $[Q_0],$ $[Q_1]$ が成り立つ.
(ii)
与えられた非負整数 $n$ に対して $[Q_n],$ $[Q_{n+1}]$ が成り立つとすると, \begin{align*} f_{n+2}(-x) &= 2(-x)f_{n+1}(-x)-f_n(-x) \\ &= -2x(-1)^{n+1}f_{n+1}(x)-(-1)^nf_n(x) \\ &= (-1)^{n+2}(2xf_{n+1}(x)-f_n(x)) \\ &= (-1)^{n+2}f_{n+2}(x). \end{align*} となり, $[Q_{n+2}]$ が成り立つ.
(i), (ii) から, 任意の非負整数 $n$ に対して $[Q_n]$ が成り立つので, 題意が成り立つ.
(3)
$x = \cos\theta\ (0 \leqq \theta < 2\pi )$ とおくと, (1) から, \begin{align*} &f_m(x) = 0 \iff \cos m\theta = 0 \\ &\iff m\theta = (2k-1)\frac{\pi}{2} \quad (k \in \{ 1,\ \cdots,\ m\}) \\ &\iff x = \cos\left(\frac{2k-1}{m}\frac{\pi}{2}\right) \quad (k \in \{ 1,\ \cdots,\ m\}). \end{align*}
(4)
\[d = \frac{n}{m}, \quad \theta _k = \frac{2k-1}{m}\frac{\pi}{2} \quad (k \in \{ 1,\ \cdots,\ m\})\] とおくと, (1) で示したことと $f_d$ が奇関数であることから, \begin{align*} f_n(\cos\theta _k) &= \cos n\theta _k = \cos d(m\theta _k) = f_d(\cos m\theta _k) \\ &= f_d(f_m(\cos\theta _k)) = f_d(0) = 0 \end{align*} となる. よって, 因数定理により $f_n(x)$ は $x-\cos\theta _k\ (1 \leqq k \leqq m)$ で割り切れる. ゆえに, $f_n(x)$ は $f_m(x)$ で割り切れる.

問題≪$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!\] が成り立つ.

問題≪特殊な漸化式≫

 数列 $\{ a_n\}$ が $a_1 = 1,$ $a_2 = \dfrac{1}{2}$ と \[ a_{n+2} = a_{n+1}-\frac{a_n}{n+2}\] を満たすとき, 数列 $\{ b_n\}$ を \[ b_n = (n+1)a_{n+1}-a_n\] で定める.
(1)
$b_{n+1}$ を $b_n$ を用いて表せ.
(2)
$b_n$ を求めよ.
(3)
$a_n$ を求めよ.
[北里大・医 2007]

解答例

(1)
漸化式により, \begin{align*} b_{n+1} &= (n+2)a_{n+2}-a_{n+1} \\ &= (n+2)a_{n+1}-a_n-a_{n+1} \\ &= (n+1)a_{n+1}-a_n = b_n. \end{align*}
(2)
初期条件から, \[ b_n = b_{n-1} = \cdots = b_1 = 2a_2-a_1 = 0.\]
(3)
(2) の結果から $a_{n+1} = \dfrac{1}{n+1}a_n$ が成り立つので, $a_1 = 1$ から, \[ a_n = \frac{1}{n}a_{n-1} = \cdots = \frac{1}{n!}.\]

問題≪ロジスティック方程式(漸化式)≫

 実数 $a,$ $r$ に対し数列 $\{ x_n\}$ を \[ x_1 = a, \quad x_{n+1} = rx_n(1-x_n)\ (n \geqq 1)\] で定める.
(1)
すべての $n$ について $x_n = a$ となるような $a$ を求めよ.
(2)
$x_2 \neq a,$ $x_3 = a$ となるような $a$ の個数を求めよ.
(3)
$0 \leqq a \leqq 1$ となるすべての $a$ について $0 \leqq x_n \leqq 1$ ($n \geqq 1$)が成り立つような $r$ の範囲を求めよ.
[大阪大]

解答例

(1)
(i)
$a = 0$ のとき. $x_n = 0\ (n \geqq 1)$ である.
(ii)
$a \neq 0$ のとき. $x_n = a\ (n \geqq 1)$ となるためには, $x_2 = a$ となることが必要である. その条件は, $x_2 = rx_1(1-x_1)$ から, \begin{align*} ra(1-a) &= a \\ a(ra-r+1) &= 0 \\ a &= \frac{r-1}{r} \quad (a \neq 0) \end{align*} である. このとき, $x_2 = a$ から, $x_n = a\ (n \geqq 1)$ となる.
(i)は(ii)の $r = 1$ の場合に含まれるから, $a = \dfrac{r-1}{r}\ (r \neq 0)$ である.
(2)
準備中.
(3)
準備中.