こんにちは、本日は漸化式について話していこうと思います。基本的のところから話していきますが、応用的な考え方も混ぜていきますので読んでくれると嬉しいです。
数列に関して、まだ全然わからないっていう人はまずは以下の記事から読んでもらったほうがいいと思います。
漸化式とは
漸化式とは数列の前後の値の関係を式にしたものです。
例えば公差が１の等差数列は１個後の項は前の項より１大きいわけです。それを漸化式では\(a_{n+1}=a_{n}+1\)と書くわけです。
逆に漸化式を見てそれがどんな数列なのかすなわち数列の一般項を求められるようになることが大学入試にすごく大事な技術なのです。
なぜなら、数列の問題に生かされるだけでなくほぼ毎年大学入試で出題される\(n\)回目の確率を求める問題で使うことができるからです。
漸化式の多くが隣り合う２項に関する関係式ですが、３項の関係式でもいいですし、何項の関係式でもいいのです。
ただし、数列が１つに決まるためはこの関係式だけでは不十分です。
なぜなら、この関係式はただ項同士の相対的な関係なのでどこかの項が決まっている必要があるのです。そのため、多くの漸化式の問題では初項が与えられているのです。
隣り合う２項に関する関係と初項が分かれば、ドミノのように初項→第２項→第３項→\(\dots\)というように順番に項が求まっていくのです。
最も基本の漸化式
今回は初級編なので基本的な漸化式のみの紹介をします。数列の基礎にして、漸化式の基礎となるのは以下の２つの漸化式です。
- \(a_{n+1}=a_{n}+1\)
- \(a_{n+1}=2 a_{n}\)
１は先ほど紹介した等差数列型の漸化式です。流石にこれは分かってもらえると思います。このパターンは漸化式にすると公差も明らかです。
2は公比2の等比数列型となります。これも数列を少し勉強していれば分かっていただけるでしょう。
階差数列パターンの漸化式
次に基本となるのが階差数列パターンの漸化式です。
\(a_{n+1}=a_{n}+n\)
階差数列パターンとはこのような漸化式のことです。この漸化式を公差が\(n\)の等差数列とは言ってはダメですよ。
なぜなら、\(n\)は一定の数では無いので「等差」では無いわけです。そうではなく階差数列の一般項が\(n\)の数列になるわけです。
階差数列が分かれば基本的に元の数列も分かります。階差数列の一般項を\(b_{n}\)とすると元の数列は、
\(a_{n}=a_{1}+\sum_{k=1}^{n-1}{a_{k}}\)
となります。ただし、実際の記述式の答案を書くときは\(n=1\)だけ場合分けしなければいけないので注意してください。階差数列の一般項がシグマ計算のできる式であれば元の式の一般項も求めることができるのです。
特性方程式を使う漸化式
最後に説明するのが特性方程式を用いて解くタイプです。
\(a_{n+1}=aa_{n}+b\)
このように\(a_{n+1}\)が\(a_{n}\)の１次式で表されているような漸化式がこのタイプです。
まずは、教科書的な解き方を説明します。
\(a_{n+1}=2a_{n}-2,a_{1}=1\)の一般項を求めてみます。
まずは\(a_{n+1}\)と\(a_{n}\)を\(α\)に変えた式を考えます。この式を特性方程式と呼びます。
今回でいうと\(α=2α-2\)が特性方程式です。
\(a_{n+1}=2a_{n}-2\tag{1}\)
\(α=2α-2\tag{2}\)
この特性方程式を考える意味は(1)-(2)することにあります。(1)-(2)をすると、
\(a_{n+1}-α=2(a_{n}-α)\)
となるのです。こうすることで、\(\{a_{n}-α\}\)という数列を考えると公比2の等比数列となるのです。
\(α=2α-2\)を解くと、\(α=2\)となるので、\(\{a_{n}-2\}\)という数列を考えると初項が\(a_{1}-2=-1\)で公比が２の等比数列なので、\(a_{n}-2=-1\times2^{n-1}=-2^{n-1}\)
頭を柔らかくして考える
基本となるのは今まであげた漸化式となります。最後に頭を柔らかくして特性方程式を解いてみます。次回応用の特性方程式にも関わることなので、少しだけ読んでください。
先ほどの\(a_{n+1}=2a_{n}-2,a_{1}=1\)の一般項を別の方法で求めてみましょう。
両辺を\(2^{n+1}\)で割ってみます。
\(\frac{a_{n+1}}{2^{n+1}}=\frac{a_{n}}{2^{n}}-2^{-n}\)
こういう式を見たときに反応できるようになることが大事です。\(\frac{a_{n+1}}{2^{n+1}}\)と\(\frac{a_{n}}{2^{n}}\)は\(n\)と\(n+1\)が違うだけなのです。つまり\(\{\frac{a_{n}}{2^{n}}\}\)という数列を考えると階差数列型の漸化式と考えることができます。
すなわち階差数列の漸化式が\(-2^{-n}\)で初項が\(\frac{1}{2}\)の数列となるのです。ちなみにこの階差数列は等比数列なのでシグマ（和）を計算できるので元の数列も求めることができるわけです。
まとめ
もちろんこのやり方は先ほどの特性方程式よりもややこしいので実用的ではありません。
大事なのは、どのような難しい漸化式であっても一般項が求まる限り（問題で求めろと言われてるなら求まるはず）等差数列型、等比数列型、階差数列型、特性方程式型のいずれかに帰着させることができます。
次回はもっと応用的な漸化式の解き方を紹介しますのでまた読んでくれると嬉しいです。
