次: 漸化式で解く 上: 内部構造の分析 前: 考え方

帰納的定義

数列と漸化式

数学で自然数はもっとも基本的なものであるが， この自然数 $n=1,\ 2,\ 3,\ \cdots$に対して， 例えば数$a_n$，関数$f_n(x)$，行列$A_n$など 何らかの数学的対象が定まるとき，これを広い意味の数列という． 詳しくいうときは数の場合を数列，関数の場合は関数列などという． 行列の場合は行列列とはあまりいわない．

数列はどのように定められるのか． それは直接定義と帰納的定義である． 直接定義とは，自然数$n$に対して

$$a_n=n^2-n,\ f_n(x)=nx^2-(n^2+2)x-3n$$

のように，まさに直接定めるものである．

これに対して帰納的定義は例えば次のようなものである．

$$a_1=1,\ a_{n+1}=3a_n+5$$

このように$a_n$に対して$a_{n+1}$を定める式を(二項間)漸化式という． 一般にいえば

1. $a_1$の値を定める．
2. 数列$\{a_n\}$に対して第$n+1$項$a_{n+1}$を， 第$n$項$a_n$と$n$を含む式$F(a_n,\ n)$によって
   
   $$a_{n+1}=F(a_n,\ n)$$
   
   
   で定める．

$a_1$の値は与えられているので， それを順に代入していけば，数列が定まる． それは数学的帰納法によって示される．

$n=1$のときの値は与えられている．

$n=k$の値が決まるとする．このとき $a_{k+1}=F(a_k,\ k)$によって$a_{k+1}$の値が定まる．

したがってすべての$n$に対して，$a_n$の値が確定する．

これを漸化式による数列の帰納的定義という． $a_n$と$a_{n+1}$に対して$a_{n+2}$が定まるようなときは， 初期値は$a_1,\ a_2$が必要だ． 数列を帰納的に定義する関係式が漸化式なのだ．

漸化式を立てて解く

数列と漸化式の関係は， 文章題と方程式のようなものである． 植木算や鶴亀算などの文章問題も，方程式を立てることを知れば， 一般的な方法で解くことができる． 数列の場合も，漸化式ができれば一般項が機械的な計算で求まることもある． 少なくとも，順次代入することで必要な番号の値を知ることはできる．

漸化式は，漸化式が問題の中で与えられたときに解くだけのものだ， と考えていないだろうか．実はそうではなく， 確率や場合の数を求める場合に漸化式を立てて求める， 数列を求めるために漸化式を立てる，ということが大切なのだ．

状態の変化と漸化式

確率や場合の数を求める場合の漸化式について考えよう． 自然数$n$に対して事象が変化し， その事象の総数や確率が定まっていくような場合である．

その総数や確率の漸化式を立てるにあたって大切なことは， 起こりうるすべての場合を数列に置くということである． こうすれば，$n$のときのどの状態も1回試行を増やすことで， $n+1$のときのいずれかの状態になるので， $n+1$のときの事象が$n$のときの事象からどのように定まるかを， 樹形図や場合分けを考え，その相互関係を求めることで必ず漸化式ができる．

漸化式を立てるのは方程式を立てるのと同じ意味をもつことである．

• 漸化式で解く
• マルコフ過程
• 数列を漸化式に戻す
• 問題と考え方