こんにちは、しゅがーです。
今回は漸化式の解き方を解説します。
漸化式は正しく勉強できているかが鍵の分野です。闇雲にただ解法を覚えただけでは応用問題を解くのは難しいです。
というのも、適切に正解の解法を選ぶのが難しい分野です。
そのため、漸化式の勉強は解法の「分類」が攻略の鍵となるのです。
よく「漸化式の形」で分類している解説を見かけます。が、そういった分類は正直微妙です。
そうではなく、「手法」で分類した方がはるかに記憶量が少なくて済み、応用が効きます。めちゃくちゃ単純なんです。
今回は「手法の分類」という方向性で解説していきます。
目次 [非表示]
漸化式の構造を理解しよう
まず漸化式の構造を理解してほしいです。というのも、漸化式って「ゴール」はたった2つなんです。
ゴールは2つ
隣合う「係数」に着目する。これです。
漸化式を見てみて、例えばa_{n+1}の係数を1としたときにa_nの係数が
1かそれ以外か
でゴールはだいたい見えてくるのです。

そう、係数が1のときは階差数列に帰着して、係数が1以外のときは等比数列に帰着するのです。
ゴールはこれです。これを常に意識するのです。「この漸化式はどっちのゴールに帰着させるんだろう?」と考えるのです。

さらに、大体の難しい形をしている漸化式って、「仕掛け」があって、これを式変形で紐解くとこの2つのゴールに帰着するのです。

そしてこの式変形にはだいたいパターンが決まっています。
紐解く式変形
のちほど詳しく説明しますが、
「式変形」は主に4つ。
・「かたまり」を作る
・差を取る
・逆数を取る
・対数を取る
これです。
これらを行うと、先ほどの「2つのゴール」に帰着するのです。

思考方法
2つのゴール(等比数列・階差数列)に帰着させるには、
・「かたまり」を作る
・差を取る
・逆数を取る
・対数を取る
これらのどの式変形をすれば良いのかな?
と考えると漸化式をめちゃくちゃ攻略しやすくなります。

それでは実際に問題をやってみましょう。
問題演習
2つのゴールを意識する
2つのゴール
「等比数列型」
「階差数列型」
の超基本の漸化式をおさえていきましょう。
問題1
基本的な問題ですよね。解ける人は多いかとは思いますが、思考法を今一度確認してほしいです。
今回係数は1以外です。


よって等比数列型になんとか帰着させたい、と考えるのです。
ここで
a_{n+1}=\displaystyle\frac{3}{2}a_n-1の特性方程式
\alpha=\displaystyle\frac{3}{2}\alpha-1
を考えます。すると、この特性方程式が解を持つと仮定したうえで、
「差を取る」

を実行すると・・・

このように −1 の部分をうまく消去することができます!
a_n-\alpha=b_nとおいてあげれば、この漸化式は
b_{n+1}=\displaystyle\frac{3}{2}b_n
となり、等比数列の漸化式に帰着させることが出来ました。
あとは初項を代入したりして、求めるだけです。

問題2
a_1=3,a_{n+1}=a_n+2^n+n+1
この問題も基本問題です。が、思考方法も含めて確認しましょう。
今回係数は1です。


よって階差数列型なので、階差数列型の解き方を当てはめるだけです。
階差数列型の解き方は、

これです。これに当てはめてみれば解けます。

かたまりを作る
いよいよ式変形編です。

今回は上記の式変形のうち、「かたまりを作る」式変形を見ていきます。
「かたまりを作る」式変形をしたうえで、
2つのゴール
・階差数列型
・等比数列型
のどちらかに帰着させようと考えるわけです。具体的に問題をやってみましょう。
問題3
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}
となります。これは解ける漸化式ですね。
簡単にまとめると、要は解ける形になるような置換をするための「かたまり」を作るのが、「かたまりを作る」という式変形です。
これはいくつか練習を積めばコツをつかめるようになりますので、このタイプの問題は多く扱います。
この問題の答えはこちら。

問題4
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}
さきほどの問題3と形がなんとなく似ているのがわかりますか?
それぞれ両辺を
\displaystyle\frac{1}{n+1}で割って上げると、
\scriptsize\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)}
となり、係数が1なので、

階差数列型に帰着するとわかります。
\displaystyle \sum_{k=1}^{n-1} \frac{1}{(k+1)(k+2)}
の計算さえできればいいですね。よく見るとこちらは部分分数分解だと気づいて、このΣ計算はできるとわかるので、一般項は求められるとわかります。
部分分数分解の解き方は以下の記事でまとめています。
解答はこちら。

問題5
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
となり、これは特性方程式で解ける漸化式ですよね(問題1で扱いました)。
解答です。

問題6
a_1=2,a_{n+1}=(n+1)a_n-n
こちらの問題も、いかに「かたまり」を作るかと考えます。
さきほどの問題5では「指数」で割りました。
今回の問題でも構造が似ていて、「階乗」で割るとうまく「かたまり」を作れます。
やっていきましょう。
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)!}
となり係数が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!}
と綺麗に求められます。
あとは式を整理するだけです。
解答です。


差をとる
次の式変形です。

式変形の中で2つ目の「差を取る」式変形です。
漸化式にnが含んでいたり、
S_nが漸化式に含んでいたりするときに使います。
「差を取る」式変形をしたうえで、
2つのゴール
・階差数列型
・等比数列型
のどちらかに帰着させようと考えます。やっていきましょう。
問題7
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
となります。
この漸化式は問題1で扱ったタイプです。特性方程式です。
解答です。


問題8
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
これは問題1のタイプで、特性方程式で解けます。
解答です。

逆数をとる
次に式変形で3つ目の「逆数を取る」式変形についてです。

分数形のときに使えます。
さっそく問題で見てみましょう。
問題9
a_1=2,a_{n+1}=\displaystyle\frac{3a_n}{1-5a_n}
注意点が、逆数を取る前にa_n\neq0であることを背理法で簡単に示さなきゃいけないということです。
0で割ることはできないという大原則です。
さて、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}
これは問題1と同じタイプです。
解答です。


対数を取る
最後です。式変形で4つ目の「対数を取る」式変形についてです。

ルート、指数、積の形でぐちゃぐちゃ、などの特徴のときに使えます。
さっそく問題で見てみましょう。
問題10
a_1=1,a_{n+1}=\displaystyle 2\sqrt{a_n}
注意点がさきほどの「逆数をとる」と同じようにあります。それが、対数を取る前に
(真数)>0
であることを数学的帰納法で簡単に示すことです。
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
となり、問題1のタイプに帰着できます。
解答です。


知らなきゃ解けない漸化式
・隣接3項間
・連立漸化式
・分数形
・何かと見立てる(三角関数など)
これらの4つの漸化式は知らなきゃできない系です。完全に知識です。
注意すべきなのは、これらの4つは誘導がつくこともあるということです。その場合は誘導に乗ることを最優先にすべきです。とはいえ、もし誘導にうまく乗れなかったときも、そもそも誘導がなかったときも、いずれにしても今回扱う知識は役に立つと思います。
それではやっていきましょう。
隣接3項間
隣接3項間は問題を解きながら解き方をまとめていきます。
問題11
a_1=0,a_2=1,a_{n+2}=a_{n+1}+6a_n
やっていきます。
3項間漸化式のポイントは、特性方程式が二次方程式になるということです。
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})
と式変形できます。※もともとの漸化式と同じ式です。(証明は省略)(この2式の形を覚えましょう)
すると、これらは等比数列の漸化式なので、
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を求めることが出来るのです。
大まかにまとめると、3つポイントがあります。この3つを流れとして覚えておきましょう。
・特性方程式(※二次方程式)を立式&解く
・特性方程式の解から、2つの漸化式を立式
・漸化式を解き、2つの漸化式を引くことでa_nを求める
解答です。

連立漸化式
連立漸化式については、色々な解き方が存在します。
主に3つです。
・足したり引いたりしてみる
・変数減らして3項間漸化式に帰着
・a_{n+1}+xb_{n+1}=y(a_n+xb_n)とおいてx,yを求める
いきなり全ての解法を頭に入れるよりは、まずは一つ、
・足したり引いたりしてみる
の解法をおさえておきましょう。
問題12
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をそれぞれ求めることが出来ます。
解答です。

ただし、今回のように足したり引いたりしてみてうまくのは、すべての連立漸化式では成り立ちません。問題作成者が足したり引いたりしてうまくいくように係数を調整するかはそのときによります。
うまくいかないときのために、3項間漸化式に帰着させる解法も軽くまとめておきます。
今回の問題でいうと、
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}
となり、3項間漸化式に帰着します。あとはさきほどの3項間漸化式の解き方に当てはめるだけです。
分数形
次は分数形です。
正直このタイプはかなりの確率で誘導はつきます。が、知識としておさえておくと良いと思います。
問題13
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)
次に−4を引くと・・・
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}
となり、これは等比数列型だとわかります。
あとはいつも通りのパターンです。
解き方のポイントを簡単にまとめると、
・特性方程式を立式&解く
・漸化式から、特性方程式の2つの解をそれぞれ引いて、整理
・式を割ることで等比数列型に帰着
解答です。


何かと見立てる(三角関数など)
最後です。
はっきりいってこのタイプは嫌いです。本当に知識だからつまんない。
出題者のオ◯ニーだからです。本来、作問とは解答者とのセ◯◯スです。
キモい冗談はさておき、紹介します。
問題14
数列a_0,a_1,a_2,\cdotsを\displaystyle a_n=\sqrt{\frac{1+a_{n-1}}{2}},a_0=\cos{\theta},0<\theta<\piにより定義するとき、
(1)a_nを求めよ。
(2)A_n=4^n(1-a_n)とするとき、\displaystyle\lim_{n\to\infty}A_nを求めよ。
(2)は数III要素入ってますね。以下の記事で紹介しています。
※準備中
※解答も準備中
ここにコンテンツを記載 x_{n+1}=4x_n(1-x_n)のやつ
最終手段は帰納法
帰納法のパターンもおさえておきたいです。
特に、誘導で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