○漸化式
数列において，前の項から次の項を作る手続きを表す関係式を漸化式という．
(例) \( \displaystyle a_1=1, a_{n+1}=2a_n+1 \)のとき，
\( \displaystyle a_2=2a_1+1=3 \)
\( \displaystyle a_3=2a_2+1=7 \)
\( \displaystyle a_4=2a_3+1=15 \)
\( \displaystyle \cdots \)
(基本的な漸化式)
◯漸化式の解法
(基本的なもの)
※(線形漸化式の，\( \displaystyle b_n \)の見つけ方について)\( \displaystyle b_n \)は，\( \displaystyle Q(n) \)に似た形の中から探すとよい．
\( \displaystyle Q(n) \)が\( \displaystyle n \)次式→\( \displaystyle b_n \)は\( \displaystyle n \)次式
\( \displaystyle Q(n) \)が(指数)→\( \displaystyle b_n \)は指数
\( \displaystyle Q(n) \)が(\( \displaystyle n \)次式)\( \displaystyle \times \)(指数)→\( \displaystyle b_n \)は(\( \displaystyle n \)次式)\( \displaystyle \times \)(指数)
※階差型をつくるために\( \displaystyle P(1)P(2)\cdots P(n) \)で割る操作は，\( \displaystyle 1 \)階線形微分方程式において積分因子(かけることで，\( \displaystyle 2 \)項が積の微分としてまとめられる)をかける操作に対応する．
(その他漸化式の解法)
(例) 次の条件によって定められる数列\( \displaystyle \{a_n\} \)の一般項を求める．
\( \displaystyle a_1=1, a_2=5, a_{n+2}-5a_{n+1}+6a_n=0 \)
※上の計算を一般化すると，以下のことがわかる．
漸化式\( \displaystyle a_{n+2}-pa_{n+1}+qa_n=0 \)において，
\( \displaystyle \alpha+\beta=p, \alpha\beta=q \)となる異なる\( \displaystyle 2 \)つの数\( \displaystyle \alpha, \beta \)が見つかったとすると，
\( \displaystyle \ \ \ \ \ a_n=A\alpha^{n-1}+B\beta^{n-1} \) (\( \displaystyle A,B \)は定数)
という形になる(指数は\( \displaystyle n \)にしてもよいが，\( \displaystyle n-1 \)の方が計算が少し楽になる)．
※特性方程式が重解をもつときは\( \displaystyle 1 \)つの式しか得られないが，そこから階差数列による処理が可能．
実際，
\( \displaystyle \ \ \ \ \ a_{n+2}-\alpha a_{n+1}=\alpha(a_{n+1}-\alpha a_n) \)
の形にできたとき，
\( \displaystyle a_{n+1}-\alpha a_n=\alpha^{n-1}(a_2-\alpha a_1)=\alpha^{n-1} \cdot A \) (\( \displaystyle a_2-\alpha a_1=A \)とおいた)
両編を\( \displaystyle \alpha^{n+1} \)でわって
\( \displaystyle \ \ \ \ \ \frac{a_{n+1}}{\alpha^{n+1}}-\frac{a_n}{\alpha^n}=\frac{A}{\alpha^2} \)
となるから，階差数列\( \displaystyle \left\{ \frac{a_n}{\alpha^n} \right\} \)の処理に帰着される．
(例) 次の条件によって定められる数列\( \displaystyle \{a_n\}, \{b_n\} \)の一般項を求める．
\( \displaystyle \begin{cases} a_1=1 \\ b_1=2 \end{cases} , \ \begin{cases} a_{n+1}=5a_n+6b_n \ \ \cdots \text{①} \\ b_{n+1}=3a_n+2b_n \ \ \cdots \text{②} \end{cases} \)
※\( \displaystyle \alpha \)の方程式が重解をもつときは\( \displaystyle 1 \)つの式しか得られないが，その場合は線形漸化式の処理をすればよい．
例えば本問で，単純に足すことで
\( \displaystyle a_n+b_n=3 \cdot 8^{n-1} \)
だけがわかったとすると，①から\( \displaystyle b_n \)を消去して，
\( \displaystyle a_{n+1}=5a_n+6(3 \cdot 8^{n-1}-a_n) \)
\( \displaystyle ( \iff a_{n+1}=-a_n+18 \cdot 8^{n-1} ) \)
を解けばよい．
◯漸化式の立式方法
| 方法 1 | 「状態\( \displaystyle n \rightarrow \) 状態\( \displaystyle n+1 \)」の変化に注目して立式 |
| 方法 2 | (状態\( \displaystyle n \)で，履歴の場合分けが難しい場合など) 「最初の \( \displaystyle 1 \) 手」に注目して立式 |
(例1，典型問題)
平面上に\( \displaystyle n \)本の直線があり，それらのどの\( \displaystyle 2 \)本も平行でなく，どの\( \displaystyle 3 \)本も\( \displaystyle 1 \)点で交わらないとき，これらの\( \displaystyle n \)本の直線によって平面が\( \displaystyle a_n \)個の部分に分けられるとする．\( \displaystyle a_n \)を\( \displaystyle n \)を用いて表す．
(例\( \displaystyle 2 \)，典型問題)階段をのぼる
\( \displaystyle 1 \)歩で\( \displaystyle 1 \)段または\( \displaystyle 2 \)段のどちらかで階段を上るとき，\( \displaystyle 9 \)段の階段を上る方法は全部で何通りあるか，漸化式を作って求める．
\( \displaystyle n \)段の階段の上り方の総数を\( \displaystyle a_n \)通りとする．\( \displaystyle n \geqq 3 \)のとき，\( \displaystyle n \)段の階段の上り方は，
(ア)最初に\( \displaystyle 1 \)段上り，残りの\( \displaystyle n-1 \)段を\( \displaystyle 1 \)or\( \displaystyle 2 \)段ずつ上る
(イ)最初に\( \displaystyle 2 \)段上り，残りの\( \displaystyle n-2 \)段を\( \displaystyle 1 \)or\( \displaystyle 2 \)段ずつ上る
の\( \displaystyle 2 \)つの場合があるから，
\( \displaystyle a_n=a_{n-1}+a_{n-2} \ \ (n \geqq 3) \)
\( \displaystyle a_1=1 \)，\( \displaystyle a_2=2 \)であるから，
\( \displaystyle \ \ \ \ \ a_3=2+1=3, \ a_4=3+2=5, \)
\( \displaystyle \ \ \ \ \ a_5=5+3=8, \ a_6=8+5=13, \)
\( \displaystyle \ \ \ \ \ a_7=13+8=21, \ a_8=21+13=34, \)
\( \displaystyle \ \ \ \ \ a_9=34+21=55 \)
よって，求める総数は，\( \displaystyle a_9=55 \) 通り (答)
※\( \displaystyle n \)はまず十分大きいと考えて考察し，\( \displaystyle a_{n-1} \)，\( \displaystyle a_{n-2} \)がでてくるから\( \displaystyle n \geqq 3 \)の範囲，と後からわかる．
※「最初の\( \displaystyle 1 \)手」ではなく，状態\( \displaystyle n \)の周辺から考えることもできる．実際，
(ア)\( \displaystyle n \)段目から\( \displaystyle 2 \)段登って\( \displaystyle n+2 \)段目に到達
(イ)\( \displaystyle n+1 \)段目から\( \displaystyle 1 \)段上って\( \displaystyle n+2 \)段目に到達
の\( \displaystyle 2 \)パターンの合計として\( \displaystyle a_{n+2} \)がもとまる．すなわち，
\( \displaystyle a_{n+2}=a_{n+1}+a_n \ \ (n \geqq 1) \)
が導ける．
※(補足)この問題の\( \displaystyle \{a_n\} \)は，フィボナッチ数列という(\( \displaystyle a_0=1 \))．
○数学的帰納法
規則性(漸化式)のある命題の証明→数学的帰納法
[STEP1]「最初」での成立を確認する
[STEP2]「前」での成立を仮定して「次」での成立を確認する
(例，和歌山県) 2次方程式 \( \displaystyle x^2-7x+5=0 \) の2つの解を \( \displaystyle \alpha, \beta \) とする．
このとき，すべての自然数 \( \displaystyle n \) について \( \displaystyle \alpha^n+\beta^n-7^n \) は \( \displaystyle 5 \) の倍数であることを証明する.
この記事は役に立ちましたか？
間違い/不具合かな？
と思ったらこちらへ
