次: $a_{n+1}=ra_n+f(n)$の解法 上: 二項間漸化式

漸化式とは何か

漸化式の定義

早苗　 漸化式 $a_{n+1}=3a_n+5\cdot 2^n$の解法を習いました． 両辺を$2^{n+1}$で割って解く方法を習いましたが， $3^{n+1}$で割っても解けるということで，やってみたら出来ました．

解き方がいろいろあって，どの解き方にするのか迷ったり， わからなかったりします．

このような2項間の漸化式について， およそのどのような解法があるのか，知りたいのですが．

南海　 確かに，いろんな解法をまとめて書いてある参考書は少なそうだ．

ここでいろいろと考えてみよう． ただ，漸化式は必ずしも解くことがすべてではない． 数列の整数的な性質などでは， 漸化式で定まる数列の性質を漸化式そのものから示すことも大切なのだ．

また，確率や場合の数の漸化式では， 解く以前に漸化式を立てることが問題を解く要であったりする． そして立てた漸化式をもとに確率を計算していく問題も多い．

そのことを前提として指摘しておこう． そのうえで，ではまず，漸化式とは何か．

早苗　 $a_{n+1}=3a_n+5\cdot 2^n$のように，$a_{n+1}$を$a_n$ で表した等式です．

南海　 漸化式は何を定めるのだろうか．

早苗　 数列$\{a_n\}$を定めます．

南海　 どのようにして定めるのか？

早苗　 $a_1$の値は与えられていますので， それを順に代入していけば，数列が求まります．

南海　 それは何を意味しているのだろう． そのことを，ここでは2項間の漸化式で考えよう．

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$の値が与えられれば,この数列$\{a_n\}$は一意に確定する．

それは数学的帰納法によって示される．

早苗　

$$a_2=F(a_1,\ 1),\ a_3=F(a_2,\ 2),\ a_4=F(a_3,\ 3),\ \cdots$$

と決まっていきます． このことを数学的帰納法で示すのですね．

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

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

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

ですね． そうか，数列$\{a_n\}$は初項をもとに漸化式によって定まることが数学的帰納法で示されるのですね．

南海　 そうなのだ．これを漸化式による数列の帰納的定義という．

漸化式を解く

早苗　 $n$に対して$a_n$が定まるのだから， $a_n$は$n$の式で書けるはずだ，ということですね．

南海　 いや．定まることと書けることは同じではない． 例えば

$$a_{n+1}=-{a_n}^2+a_n+2$$

のような2次の項のある漸化式は，書けるかもしれないが簡単ではないはずだ．

$a_n$を$n$の式で書くことを漸化式を解くという．

早苗　 すると数列$\{a_n\}$は未知数列で， それを満たす数列を具体的に求めることが，漸化式を解くことなのですね．

南海　 未知数列であることをはっきりさせるためには， $x_{n+1}=F(x_n,\ n)$ のようにした方が分かりやすいとも言える．

何にせよ，漸化式を解くことは簡単ではないのだ．

早苗　 $a_{n+1}=n^2 a_n+3n$ なんかも難しそうです．