こんにちは、しゅがーです。
今回は漸化式の解き方を解説します。
漸化式は正しく勉強できているかが鍵の分野です。闇雲にただ解法を覚えただけでは応用問題を解くのは難しいです。
というのも、適切に正解の解法を選ぶのが難しい分野です。
そのため、漸化式の勉強は解法の「分類」が攻略の鍵となるのです。
よく「漸化式の形」で分類している解説を見かけます。が、そういった分類は正直微妙です。
そうではなく、「手法」で分類した方がはるかに記憶量が少なくて済み、応用が効きます。めちゃくちゃ単純なんです。
今回は「手法の分類」という方向性で解説していきます。
目次
漸化式の構造を理解しよう
まず漸化式の構造を理解してほしいです。というのも、漸化式って「ゴール」はたった２つなんです。
ゴールは２つ
隣合う「係数」に着目する。これです。
漸化式を見てみて、例えば\(a_{n+1}\)の係数を１としたときに\(a_n\)の係数が
１かそれ以外か
でゴールはだいたい見えてくるのです。
そう、係数が１のときは階差数列に帰着して、係数が１以外のときは等比数列に帰着するのです。
ゴールはこれです。これを常に意識するのです。「この漸化式はどっちのゴールに帰着させるんだろう？」と考えるのです。
さらに、大体の難しい形をしている漸化式って、「仕掛け」があって、これを式変形で紐解くとこの２つのゴールに帰着するのです。
そしてこの式変形にはだいたいパターンが決まっています。
紐解く式変形
のちほど詳しく説明しますが、
「式変形」は主に４つ。
・「かたまり」を作る
・差を取る
・逆数を取る
・対数を取る
これです。
これらを行うと、先ほどの「２つのゴール」に帰着するのです。
思考方法
２つのゴール（等比数列・階差数列）に帰着させるには、
・「かたまり」を作る
・差を取る
・逆数を取る
・対数を取る
これらのどの式変形をすれば良いのかな？
と考えると漸化式をめちゃくちゃ攻略しやすくなります。
それでは実際に問題をやってみましょう。
問題演習
２つのゴールを意識する
２つのゴール
「等比数列型」
「階差数列型」
の超基本の漸化式をおさえていきましょう。
問題１
基本的な問題ですよね。解ける人は多いかとは思いますが、思考法を今一度確認してほしいです。
今回係数は１以外です。
よって等比数列型になんとか帰着させたい、と考えるのです。
ここで
\(a_{n+1}=\displaystyle\frac{3}{2}a_n-1\)の特性方程式
\(\alpha=\displaystyle\frac{3}{2}\alpha-1\)
を考えます。すると、この特性方程式が解を持つと仮定したうえで、
「差を取る」
を実行すると・・・
このように −１ の部分をうまく消去することができます！
\(a_n-\alpha=b_n\)とおいてあげれば、この漸化式は
\(b_{n+1}=\displaystyle\frac{3}{2}b_n\)
となり、等比数列の漸化式に帰着させることが出来ました。
あとは初項を代入したりして、求めるだけです。
問題２
\(a_1=3,a_{n+1}=a_n+2^n+n+1\)
この問題も基本問題です。が、思考方法も含めて確認しましょう。
今回係数は１です。
よって階差数列型なので、階差数列型の解き方を当てはめるだけです。
階差数列型の解き方は、
これです。これに当てはめてみれば解けます。
かたまりを作る
いよいよ式変形編です。
今回は上記の式変形のうち、「かたまりを作る」式変形を見ていきます。
「かたまりを作る」式変形をしたうえで、
２つのゴール
・階差数列型
・等比数列型
のどちらかに帰着させようと考えるわけです。具体的に問題をやってみましょう。
問題３
\(a_1=1,(n+2)a_{n+1}=na_n\)
さてこちらの問題です。
「かたまり」を作るとは？
簡単に言えば、置換するための行為です。
例えば今回の問題の漸化式、
\((n+2)a_{n+1}=na_n\)
こちらは\(b_{n}=na_n\)と置換したところで、
\(b_{n+1}=(n+1)a_{n+1}\)となるので、
\((n+2)a_{n+1}=na_n\)
こちらを解ける漸化式になるような置換をできません。
そこで「かたまり」を意識します。両辺に\((n+1)\)をかけてみると・・・
\((n+2)(n+1)a_{n+1}=(n+1)na_n\)
となります。
\(b_{n}=(n+1)na_n\)と置換すると、
\(b_{n+1}=(n+2)(n+1)a_{n+1}\)となるので
\((n+2)(n+1)a_{n+1}=(n+1)na_n\)
この漸化式は
\(b_{n+1}=b_{n}\)
となります。これは解ける漸化式ですね。
簡単にまとめると、要は解ける形になるような置換をするための「かたまり」を作るのが、「かたまりを作る」という式変形です。
これはいくつか練習を積めばコツをつかめるようになりますので、このタイプの問題は多く扱います。
この問題の答えはこちら。
問題４
\(a_1=2,a_{n+1}=\displaystyle\frac{n+2}{n}a_n+1\)
こちらの問題はどのように「かたまり」を作りますか？
\(a_{n+1}=\displaystyle\frac{n+2}{n}a_n+1\)
\(a_{n+1}\)、\(a_n\)でそれぞれ「かたまり」を作りたいので、とりあえず両辺を\((n+2)\)で割りましょう。
\(\displaystyle\frac{1}{n+2}a_{n+1}=\frac{1}{n}a_n+\frac{1}{n+2}\)
さきほどの問題３と形がなんとなく似ているのがわかりますか？
それぞれ両辺を
\(\displaystyle\frac{1}{n+1}\)で割って上げると、
\(\displaystyle\frac{1}{(n+2)(n+1)}a_{n+1}=\frac{1}{(n+1)n}a_n+\frac{1}{(n+1)(n+2)}\)
うまく「かたまり」を作れているのがわかりますかね。
\(\displaystyle b_n=\frac{1}{(n+1)n}a_n\)
とおくと、
\(\displaystyle b_{n+1}=\frac{1}{(n+2)(n+1)}a_{n+1}\)
と、うまく今回の漸化式の形にハマるからです。
よって、
\(\displaystyle b_n=\frac{1}{(n+1)n}a_n\)
とおくと、今回の漸化式は、
\(\displaystyle b_{n+1}=b_n+\frac{1}{(n+1)(n+2)}\)
となり、係数が１なので、
階差数列型に帰着するとわかります。
\(\displaystyle \sum_{k=1}^{n-1} \frac{1}{(k+1)(k+2)}\)
の計算さえできればいいですね。よく見るとこちらは部分分数分解だと気づいて、このΣ計算はできるとわかるので、一般項は求められるとわかります。
部分分数分解の解き方は以下の記事でまとめています。
解答はこちら。
問題５
\(a_1=3,a_{n+1}=2a_n+3^{n+1}\)
こちらの問題は有名手法なので知っている人はいるかとは思いますが、この問題の解法はまさに「かたまり」を作る良い例なので扱います。
\(a_{n+1}=2a_n+3^{n+1}\)
こちらの漸化式を\(3^{n+1}\)で割ると、
\(\displaystyle\frac{a_{n+1}}{3^{n+1}}=2\frac{a_n}{3^{n+1}}+1\)
こちらをちょっと整理すれば、
\(\displaystyle\frac{a_{n+1}}{3^{n+1}}=\frac{2}{3}\frac{a_n}{3^{n}}+1\)
このように「かたまり」が作れているのがわかりますね。
\(\displaystyle b_n=\frac{a_n}{3^{n}}\)
とおけば、
\(\displaystyle b_{n+1}=\frac{a_{n+1}}{3^{n+1}}\)
となって、うまくハマるからです。
置換後の式は
\(\displaystyle b_{n+1}=\frac{2}{3}b_n+1\)
となり、これは特性方程式で解ける漸化式ですよね（問題１で扱いました）。
解答です。
問題６
\(a_1=2,a_{n+1}=(n+1)a_n-n\)
こちらの問題も、いかに「かたまり」を作るかと考えます。
さきほどの問題５では「指数」で割りました。
今回の問題でも構造が似ていて、「階乗」で割るとうまく「かたまり」を作れます。
やっていきましょう。
\(a_{n+1}=(n+1)a_n-n\)
\((n+1)!\)で割ると、
\(\displaystyle\frac{a_{n+1}}{(n+1)!}=\frac{(n+1)}{(n+1)}\cdot\frac{a_n}{n!}-\frac{n}{(n+1)!}\)
\(\displaystyle\frac{a_{n+1}}{(n+1)!}=\frac{a_n}{n!}-\frac{n}{(n+1)!}\)
となって、「かたまり」がつくれています。
\(\displaystyle b_n=\frac{a_n}{n!}\)
とおくと、
\(\displaystyle b_{n+1}=\frac{a_{n+1}}{(n+1)!}\)
となって、うまくハマっているからです。
置換後の式は
\(\displaystyle b_{n+1}=b_n-\frac{n}{(n+1)!}\)
となり係数が１なので、階差数列型に帰着するとわかります。
あとは、
\(\displaystyle \sum_{k=1}^{n-1} \frac{k}{(k+1)!}\)
のΣ計算ができれば良いですね。
このΣ計算は確かに難しいです。
が、「エグい形ほど部分分数分解を疑え」というお決まりを考えます。
部分分数分解の解き方は、
こちらです。
「差」の形を作れれば良いわけです。
\(\displaystyle \sum_{k=1}^{n-1} \frac{k}{(k+1)!}\)
について、分子に式変形の自由度があることに注目すると、
\(=\displaystyle \sum_{k=1}^{n-1} \frac{(k+1)-1}{(k+1)!}\)
\(=\displaystyle \sum_{k=1}^{n-1} \frac{(k+1)}{(k+1)!}-\frac{1}{(k+1)!}\)
\(=\displaystyle \sum_{k=1}^{n-1} \frac{1}{k!}-\frac{1}{(k+1)!}\)
とできるので、
\(=\displaystyle 1-\frac{1}{n!}\)
と綺麗に求められます。
あとは式を整理するだけです。
解答です。
差をとる
次の式変形です。
式変形の中で２つ目の「差を取る」式変形です。
漸化式にnが含んでいたり、
\(S_n\)が漸化式に含んでいたりするときに使います。
「差を取る」式変形をしたうえで、
２つのゴール
・階差数列型
・等比数列型
のどちらかに帰着させようと考えます。やっていきましょう。
問題７
\(a_1=1,a_{n+1}=3a_n+4n\)
こちらの問題は、差を取ってみるとうまくnを消せます。
どういうことかというと、nの式をn+1にずらしてみて、それぞれ引いてみるということです。具体的にやってみましょう。
\(a_{n+2}=3a_{n+1}+4(n+1)\)
\(a_{n+1}=3a_n+4n\)
それぞれ引くと、
\((a_{n+2}-a_{n+1})=3(a_{n+1}-a_{n})+4\)
\(b_n=a_{n+1}-a_{n}\)とおくことで、
\(b_{n+1}=a_{n+2}-a_{n+1}\)となるので、漸化式は、
\(b_{n+1}=3b_{n}+4\)
となります。
この漸化式は問題１で扱ったタイプです。特性方程式です。
解答です。
問題８
\(S_{n}=3a_n+2n-1\)（ただし\(\displaystyle\sum_{k=1}^n a_k=S_n\)）
nの式をn+1にずらしてみて、それぞれ引いてみる
今回もこれです。
\(S_{n+1}=3a_{n+1}+2(n+1)-1\)
\(S_{n}=3a_n+2n-1\)
それぞれ引いて、
\(S_{n+1}-S_n=3a_{n+1}-3a_n+2\)
となります。
ここで、
\(S_{n+1}-S_n=a_{n+1}\)と、\(a_{n+1}\)を引きずり出せるというのを使います。
なぜなら、
\(S_{n+1}=a_{n+1}+a_n+\cdots+a_2+a_1\)
\(S_{n}=a_n+\cdots+a_2+a_1\)
これらをそれぞれ引くと、
\(S_{n+1}-S_n=a_{n+1}\)
となるからです。
さきほどの漸化式に戻って、
\(S_{n+1}-S_n=3a_{n+1}-3a_n+2\)
\(a_{n+1}=3a_{n+1}-3a_n+2\)
整理して、
\(\displaystyle a_{n+1}=\frac{3}{2}a_n-1\)
これは問題１のタイプで、特性方程式で解けます。
解答です。
逆数をとる
次に式変形で３つ目の「逆数を取る」式変形についてです。
分数形のときに使えます。
さっそく問題で見てみましょう。
問題９
\(a_1=2,a_{n+1}=\displaystyle\frac{3a_n}{1-5a_n}\)
注意点が、逆数を取る前に\(a_n\neq0\)であることを背理法で簡単に示さなきゃいけないということです。
０で割ることはできないという大原則です。
さて、\(a_n\neq0\)を証明できたとしましょう。
逆数を取ってみると、
\(\displaystyle\frac{1}{a_{n+1}}=\frac{1-5a_{n}}{3a_n}\)
\(\displaystyle\frac{1}{a_{n+1}}=\frac{1}{3}\cdot\frac{1}{a_n}-\frac{5}{3}\)
\(\displaystyle b_n=\frac{1}{a_n}\)とおけば、
\(\displaystyle b_{n+1}=\frac{1}{3}b_n-\frac{5}{3}\)
これは問題１と同じタイプです。
解答です。
対数を取る
最後です。式変形で４つ目の「対数を取る」式変形についてです。
ルート、指数、積の形でぐちゃぐちゃ、などの特徴のときに使えます。
さっそく問題で見てみましょう。
問題１０
\(a_1=1,a_{n+1}=\displaystyle 2\sqrt{a_n}\)
注意点がさきほどの「逆数をとる」と同じようにあります。それが、対数を取る前に
（真数）＞０
であることを数学的帰納法で簡単に示すことです。
\(a_{n}>0\)であることを証明できたとします。
対数を取ってみると、
\(\log_2 a_{n+1}=\log_2 {2\sqrt{a_n}}\)
整理すると、
\(\displaystyle \log_2 a_{n+1}=1+\frac{1}{2}\log_2 {a_n}\)
\(\log_2 a_{n}=b_n\)とおくことで、
\(\displaystyle b_{n+1}=1+\frac{1}{2}b_n\)
となり、問題１のタイプに帰着できます。
解答です。
知らなきゃ解けない漸化式
・隣接３項間
・連立漸化式
・分数形
これらの３つの漸化式は知らなきゃできない系です。完全に知識です。
注意すべきなのは、これらの３つは誘導がつくこともあるということです。その場合は誘導に乗ることを最優先にすべきです。とはいえ、もし誘導にうまく乗れなかったときも、そもそも誘導がなかったときも、いずれにしても今回扱う知識は役に立つと思います。
それではやっていきましょう。
隣接３項間
隣接３項間は問題を解きながら解き方をまとめていきます。
問題１１
\(a_1=0,a_2=1\),\(a_{n+2}=a_{n+1}+6a_n\)
やっていきます。
３項間漸化式のポイントは、特性方程式が二次方程式になるということです。
\(a_{n+2}=a_{n+1}+6a_n\)
↓
\(x^2=x+6\) ←これが特性方程式
この解を\(\alpha,\beta\)とします。この\(\alpha,\beta\)を用いると、
\(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})\)
と式変形できます。※もともとの漸化式と同じ式です。（証明は省略）（この２式の形を覚えましょう）
すると、これらは等比数列の漸化式なので、
\(a_{n+1}-\alpha a_{n} = \beta^{n-1} (a_2-\alpha a_1)\cdots(1)\)
\(a_{n+1}-\beta a_{n} = \alpha^{n-1} (a_2-\beta a_1)\cdots(2)\)
(1)-(2)を実行することで、\(a_{n+1}\)を消去でき、\(a_n\)を求めることが出来るのです。
大まかにまとめると、３つポイントがあります。この３つを流れとして覚えておきましょう。
・特性方程式（※二次方程式）を立式＆解く
・特性方程式の解から、２つの漸化式を立式
・漸化式を解き、２つの漸化式を引くことで\(a_n\)を求める
解答です。
連立漸化式
連立漸化式については、色々な解き方が存在します。
主に３つです。
・足したり引いたりしてみる
・変数減らして３項間漸化式に帰着
・\(a_{n+1}+xb_{n+1}=y(a_n+xb_n)\)とおいてx,yを求める
いきなり全ての解法を頭に入れるよりは、まずは一つ、
・足したり引いたりしてみる
の解法をおさえておきましょう。
問題１２
\(a_1=1,b_1=2\),\(a_{n+1}=2a_n+b_n\),\(b_{n+1}=a_n+2b_n\)
\(a_{n+1}=2a_n+b_n\)
\(b_{n+1}=a_n+2b_n\)
これらの漸化式をそれぞれ足したり引いたりしてみるってことです。
足してみると、
\(a_{n+1}+b_{n+1}=3(a_n+b_n)\)
となり、うまく等比数列型になっています。
よって、
\(a_n+b_n=3^{n-1}(a_1+b_1)\)
と求めることが出来ます。
次に、
\(a_{n+1}=2a_n+b_n\)
\(b_{n+1}=a_n+2b_n\)
それぞれ引いてみると、
\(a_{n+1}-b_{n+1}=1\cdot(a_n-b_n)\)
となり、これもうまく等比数列型になっています。
よって、
\(a_n-b_n=(a_1-b_1)\)
と求めることが出来ます。
並べてみると、
\(a_n+b_n=3^{n-1}(a_1+b_1)\)
\(a_n-b_n=(a_1-b_1)\)
となり、これらを更に足したり引いたりすると
\(a_n,b_n\)をそれぞれ求めることが出来ます。
解答です。
ただし、今回のように足したり引いたりしてみてうまくのは、すべての連立漸化式では成り立ちません。問題作成者が足したり引いたりしてうまくいくように係数を調整するかはそのときによります。
うまくいかないときのために、３項間漸化式に帰着させる解法も軽くまとめておきます。
今回の問題でいうと、
\(a_{n+1}=2a_n+b_n\cdots(1)\)
\(b_{n+1}=a_n+2b_n\cdots(2)\)
で、(2)式に着目して、式変形すると、
\(a_n=b_{n+1}-2b_n\)
nをn+1にずらして
\(a_{n+1}=b_{n+2}-2b_{n+1}\)
これらを(1)式に代入すると、
\(b_{n+2}-2b_{n+1}=2(b_{n+1}-2b_n)+b_n\)
これを整理すると、
\(b_{n+2}=4b_{n+1}-3b_{n}\)
となり、３項間漸化式に帰着します。あとはさきほどの３項間漸化式の解き方に当てはめるだけです。
分数形
次は分数形です。
正直このタイプはかなりの確率で誘導はつきます。が、知識としておさえておくと良いと思います。
問題１３
\(a_1=4\),\(a_{n+1}=\displaystyle\frac{4a_n+8}{a_n+6}\)
分数形といえば逆数をとるとうまくいくというパターンを紹介しましたが、今回のような分数形の漸化式はうまくいきません。
そこで、特性方程式の出番です。
\(a_{n+1}=\displaystyle\frac{4a_n+8}{a_n+6}\)
↓
\(x=\displaystyle\frac{4x+8}{x+6}\) ←これが特性方程式
この解を\(\alpha,\beta\)とすると、
これら\(\alpha,\beta\)を連立漸化式からそれぞれ引くとうまくいきます。
今回でいうと、
\(x=\displaystyle\frac{4x+8}{x+6}\)
を解くと、
\(x=2,-4\)
となるので、
\(a_{n+1}=\displaystyle\frac{4a_n+8}{a_n+6}\)
からそれぞれ、2,-4を引きます。
2を引くと・・・
\(a_{n+1}-2=\displaystyle\frac{4a_n+8}{a_n+6}-2\)
整理すると・・・
\(a_{n+1}-2=\displaystyle2\cdot\frac{a_n-2}{a_n+6}\cdots(1)\)
次に−４を引くと・・・
\(a_{n+1}+4=\displaystyle\frac{4a_n+8}{a_n+6}+4\)
整理すると・・・
\(a_{n+1}+4=\displaystyle8\cdot\frac{a_n+4}{a_n+6}\cdots(2)\)
となり、(1)を(2)で割ると・・・
\(\displaystyle\frac{a_{n+1}-2}{a_{n+1}+4}=\frac{1}{4}\cdot\frac{a_n-2}{a_n+4}\)
となり、これは等比数列型だとわかります。
あとはいつも通りのパターンです。
解き方のポイントを簡単にまとめると、
・特性方程式を立式＆解く
・漸化式から、特性方程式の２つの解をそれぞれ引いて、整理
・式を割ることで等比数列型に帰着
解答です。
最終手段は帰納法
帰納法のパターンもおさえておきたいです。
特に、誘導で\(a_1,a_2,a_3\)などをわざわざ求めさせる問題は、
「推測して帰納法で示してください」っていうメッセージだと受け取りましょう。
また、そのような誘導がなくても、全く手も足も出ないような漸化式は、
推測→帰納法のパターンしかないって予想しましょう。
各項が正の数である数列\(\{a_n\}\)が\(a_1=2\)と関係式
\(a_{n+1}^{2}a_n=a_{n+1}+\displaystyle\frac{2(n+2)}{n(n+1)}\)
\((n=1,2,3,\cdots)\)
を満たすとき、次の問いに答えよ。
(1)\(a_2,a_3\)を求めよ。
(2)\(a_n\)を\(n\)の式で表せ。
（横浜国立大）
解答です。
\(a_1=-\displaystyle\frac{1}{2},a_{n+1}=\displaystyle\frac{3}{2}a_n-1\)