目次
まえがき
今回の記事（から数回連続）では漸化式の解法について述べていきます。高校の指導過程では「このタイプの漸化式を見たらこの解法だ！」となっているケースが多いようで、解法暗記に嫌気がさしたという方も少なくないはずです。そこで本記事では線形２項間漸化式（以下で定義を補足しますが、大学数学で出てくる線形性とはまた違う意味で使っています。）の解法を別の切り口から提示し、より一般性が高く明解なものに仕上げていきます。抽象論がやたら多くなってしまいますが、具体例も適宜書いていますので合わせて理解していただければ幸いです。
本記事を執筆するにあたり、駿台の2018年度高２エクストラ数学α（井辺先生）の内容をベースとし、そこに自分が受験期に実践した内容を組み込みました。
本記事の内容を説明するにあたり、独自の言い回しが見られると思われますが、適宜その意味するところを補足してあります。
では、ぜひ最後までご覧になってください。
※以下、特に指定がない場合は漸化式はすべての自然数\(n\)について成立するとします。
解ける漸化式
一般に「漸化式」という時、数列の各項をそれ以前の項の関数として定める等式、という認識がなされており、これにはすごくごちゃごちゃしていて複雑なもの（＝高校数学の範囲では（ましてやたとえ大学数学の範囲に拡張したとしても）その一般項を記述できないもの）が含まれており、しかもそれらが大半を占めます。ですが、高校数学（ⅡB範囲）で扱うのは基本的には一般項を記述可能な漸化式（以下、「解ける漸化式」という）のみであり、解ける漸化式の形は決まっています。解ける漸化式は教科書・参考書を見ていると様々にあるように思えますが、つまるところ本質的には以下の３パターンに（ほとんど）帰着させることができます。
①\(a_{n+1}=a_n+d\) (等差型)
②\(a_{n+1}=ra_n\) （等比型）
③\(a_{n+1}=a_n+f(n)\) （階差型）
既知であるとは思いますが念のため①から③の解法を提示しておきます。（これに関してはあまりにも簡単なため、具体例は省略します。）
解ける漸化式の解法
①\(a_{n+1}=a_n+d\) (等差型)
等差数列の公式を用いることにより、\(a_n=a_1+(n-1)d\) （答え）
②\(a_{n+1}=ra_n\) （等比型）
等比数列の公式を用いることにより、\(a_n=a_1r^{n-1}\) （答え）
③\(a_{n+1}=a_n+f(n)\) （階差型）
移行することにより、
\(a_{n+1}-a_n=f(n)\)
上式のnをkで置き換えた式で、\(\displaystyle \sum_{k=1}^{n-1}\)として、\(n≧2\)のとき、
\(\displaystyle \sum_{k=1}^{n-1}(a_{n+1}-a_n)=\displaystyle \sum_{k=1}^{n-1}f(k)\)
左辺の途中の項は相殺するから、
\(a_n-a_1=\displaystyle \sum_{k=1}^{n-1}f(k)\)
∴ \(a_n=a_1+\displaystyle \sum_{k=1}^{n-1}f(k)\) \(n≧2\)
あとは\(n=1\)で成立するかを調べればOk. （答え）
次数論
以下で説明する革命的解法を分かりやすくするために、次数論（自分で命名しました）という概念を導入します。次数論とは、ある数列に対して、\(b_n=a_{n+1}-pa_n\)を考える時に、もとの数列{\(a_n\)}と新しい数列{\(b_n\)}の\(n\)の多項式の部分の次数の関係について述べた概念です。あまりにも抽象的で分かりにくいと思いますので、具体例をあとで添えておきます。
以下、{\(a_n\)}と{\(b_n\)}の\(n\)の多項式の部分の次数が同じとき不変、次数が下がっている場合は降下と言うことにします。
①\(a_n=(nの多項式) \)のとき
以下、\((nの多項式)=\displaystyle \sum_{i=0}^{N}c_i n^i\) （\(c_N≠0\)）（\(n\)の\(N\)次式）としておく。
（Case1） \(p≠1\)のとき
\(b_n=a_{n+1}-pa_n=\displaystyle \sum_{i=0}^{N}c_i (n+1)^i -p\displaystyle \sum_{i=0}^{N}c_i n^i\)
最右辺の\(n\)の\(N\)次の係数に着目すると、
\((nのN次の係数)=c_N-pc_N=c_N(1-p)≠0 \)
（Case2） \(p=1\)のとき
上式へ\(p=1\)を代入して、\((nのN次の係数)=0\)
→以上のことにより、\(p≠1\)のとき次数は不変であり、\(p=1\)のとき次数は降下することが結論づけられます。（階差の場合のみ次数が下がっています。）
②\(a_n=(nの多項式) \times q^n\)のとき （\(q≠0\)）
（Case1） \(p≠q\)のとき
\(b_n=a_{n+1}-pa_n=\displaystyle \sum_{i=0}^{N}c_i (n+1)^i q^{n+1}-p\displaystyle \sum_{i=0}^{N}c_i n^i q^n\)
最右辺の\(q^n\)にかかっている\(n\)の多項式の部分の\(n\)の\(N\)次の係数に着目すると、
\((nのN次の係数)=c_Nq^{n+1}-c_Npq^n=c_N(q-p) q^n≠0 \)
（Case2） \(p=q\)のとき
上式へ\(p=q\)を代入して、\((nのN次の係数)=0\)
→以上のことにより、\(p≠q\)のとき次数は不変であり、\(p=q\)のとき次数は降下することが結論づけられます。（等比倍の場合のみ次数が下がっています。）
具体例
①\(a_n=n^2\)のとき
\(a_{n+1}-pa_n=({n+1})^2-pn^2=(1-p)n^2+2n+1\) (\(p≠1\))
→2次式（不変）
\(a_{n+1}-a_n=({n+1})^2-n^2=2n+1\)
→1次式（降下）
②\(a_n=(2n-1)3^n\)のとき
\(a_{n+1}-qa_n=(2n+1)3^{n+1}-(2n-1)q3^n=((6-2q)n+3+q)3^n\) (\(q≠3\))
→\((nの1次式) \times 3^n\)（不変）
\(a_{n+1}-qa_n=(2n+1)3^{n+1}-(2n-1)3 \times 3^n=6 \cdot 3^n\) (\(q=3\))
→\((nの0次式) \times 3^n\)（降下）
このように、上記の次数論が正しいことがわかりました。では以下で実際に漸化式の革命的解法について言及していきます。
漸化式の革命的解法
従来の解法では、各々の漸化式を１つ１つ解ける漸化式に帰着させる必要がありましたが、今回紹介する解法では、わずか２つの解法で済みます。それを以下で提示します。こちらもあまりにも抽象的で分かりにくいと思いますので、具体例をあとで添えておきます。
以下では、一般に高校数学で扱う線形２項間漸化式を\(a_{n+1}=ra_n+f(n)\)と書くことにします。
（本記事では、\(a_{n+1}\)が\(a_n\)の実数倍に\(n\)の関数を加えたもので表せる漸化式を線形２項間漸化式として扱っています。）
※特に、今回は\(f(n)\)に\(n\)の多項式あるいは\((nの多項式)×(指数関数)\)が来る場合に限定して話を進めています。というのも、高校数学で扱う線形２項間漸化式の中でややこしいものはせいぜいこれらにとどまるからです。とりわけ、確率漸化式の問題では、解きようによってはかなり汚い漸化式に遭遇することもありますが、ほぼ以上の２形式のいずれかになります。
①\(r=1\)のとき
これは、解ける漸化式の階差型（等差型も含む）と全く同じになるので簡単に解けます。（\(f(n)\)が定数の場合が等差型になるので、等差型は階差型の部分集合であるといえます。ですので、ここではまとめて階差型として扱っても差し支えないでしょう。）
移行することにより、
\(a_{n+1}-a_n=f(n)\)
上式のnをkで置き換えた式で、\(\displaystyle \sum_{k=1}^{n-1}\)として、\(n≧2\)のとき、
\(\displaystyle \sum_{k=1}^{n-1}(a_{n+1}-a_n)=\displaystyle \sum_{k=1}^{n-1}f(k)\)
左辺の途中の項は相殺するから、
\(a_n-a_1=\displaystyle \sum_{k=1}^{n-1}f(k)\)
∴ \(a_n=a_1+\displaystyle \sum_{k=1}^{n-1}f(k)\) \(n≧2\)
あとは\(n=1\)で成立するかを調べればOk.
稀に初項だけ解いた漸化式が当てはまらない数列があるので確認を怠らないようにしましょう。記述式答案では減点対象になってしまいます。
②\(r≠1\)のとき （これが本記事のメインテーマです！）
解ける漸化式②\(a_{n+1}=ra_n\)（等比型）に帰着させることを考えます。（この数列{\(a_n\)}は以下の数列{\(a_n\)}とは全く違うものです、ご注意ください）
したがって、今しなければならないことは、
\(a_{n+1}=ra_n+f(n) \tag1\)
をうまく同値変形することによって、
\(c_{n+1}=rc_n \tag2\)
となる数列{\(c_n\)}を探すことです。
ここで、
\(c_n=a_n+g(n) \tag3\)
となるような\(n\)の関数\(g(n)\)を探し出すことができれば、
(2)式へ代入することで、
\(a_{n+1}+g(n+1)=r(a_n+g(n))\)
∴\(a_{n+1}=ra_n+(rg(n)-g(n+1)) \tag4\)
となりますが、(1)式と(4)式は恒等的に同じであるから、
\(f(n)=rg(n)-g(n+1)\)
∴\(g(n+1)-rg(n)=-f(n) \tag5\)
(5)式より\(f(n)\)を見た段階で\(g(n)\)を想起することができないかということを考えます。
ここで前の章で導入した次数論のお話を思い出してもらうと、\(r≠1\)のもとでは等比倍の場合のみ次数が降下していました。前の章ではまず\(a_n\)が分かっていて、次に\(b_n\)を計算して求めましたが、今求められていることはその真逆の操作であり、
前の章の言葉を借りれば、まず\(b_n\)が分かっていて、次に\(a_n\)を計算して求めることがするべきことです。
（前の章の\(a_n\)、\(b_n\)はそれぞれこの章の\(g(n)\)、\(f(n)\)に対応しています。）
ごちゃごちゃしているので、まとめておきます。
まとめ
（Case1）\(r\)が\(f(n)\)の指数関数の部分の底とは異なるとき または \(f(n)\)に指数関数が含まれないとき
\(g(n)\)の\(n\)の多項式の部分の次数は\(f(n)\)の\(n\)の多項式の部分の次数と等しい。
（Case2）\(r\)が\(f(n)\)の指数関数の部分の底と等しいとき
\(g(n)\)の\(n\)の多項式の部分の次数は\(f(n)\)の\(n\)の多項式の部分の次数よりも1上昇する。
このようにすることで、\(g(n)\)の関数としての形式を予測することができました。後は、\(g(n)\)の\(n\)の多項式の部分の係数を自分で設定して、(5)式が自然数（場合によっては\(n=0\)を含めて定義する数列になることもある）\(n\)についての恒等式となるように、その係数を自分で計算して求めることになります。
このようにすれば、(2)式および(3)式より、等比型の漸化式の解法にしたがって、
\(a_n+g(n)=r^{n-1}(a_1+g(1))\)
∴\(a_n=r^{n-1}(a_1+g(1))-g(n)\)
となって漸化式を解くことができました。
具体例
例① \(a_{n+1}=3a_n-2n-1\) \(a_1=5\)
→\(a_n\)の係数は3であり、指数関数もないので、②の（Case1）にあたり、\(g(n)=αn+β\)と置いてα、βを求めることにする。
\(a_{n+1}+α(n+1)+β=3(a_n+αn+β)\)
\(a_{n+1}=3a_n+2αn+(-α+2β)\)
もとの漸化式と比較して、
\((α,β)=(-1,-1)\)となるから、
\(a_{n+1}-(n+2)=3(a_n-(n+1))\)
\(a_n-(n+1)=3^{n-1}(a_1-(1+1))\)
∴\(a_n=3^n+n+1\) （答え）
例② \(a_{n+1}=3a_n+2 \cdot 3^n\) \(a_1=1\)
→\(a_n\)の係数は3であり、指数関数の底と等しいので、②の（Case2）にあたり、指数関数にかかる\(n\)の多項式の部分の次数は上昇するので、\(g(n)=(αn+β)3^{n-1}\)と置いて、（指数部分は\(n\)でも\(n-1\)でもよいのですが、計算の都合上今回は\(n-1\)と置きました。）
\(a_{n+1}+(α(n+1)+β)3^{n}=3(a_n+(αn+β)3^{n-1})\)
\(a_{n+1}=3a_n-α3^n\)
もとの漸化式と比較して、
\((α,β)=(-2,0)\)
βは任意の数となりますが、どんな数で置いても最終的には必ず消えます。計算の都合上、書くのが面倒なので、このような場合は\(β=0\)と置いてしまって問題ありません。
これより、\(a_{n+1}-2(n+1)3^n=3(a_n-2n3^{n-1})\)
\(a_n-2n3^n=3(a_1-2 \cdot 1 \cdot 3^{1-1})\)
∴\(a_n=(2n-1)3^{n-1}\) （答え）
注意
１°）実際の記述式答案には、g(n)を導出する過程は書く必要はなく、いきなり等比型に帰着させた形を記述するべきである。
これは駿台数学科の井辺先生が実際に仰っていたことなのですが、このような\(g(n)\)の求め方は漸化式の解の一意性を無視したものになっています。高校数学で扱う線形２項間漸化式にその解が一意でないものは経験上全くありませんが、採点官に自明か否か不明瞭である一意性を前提とした答案を見せることには、減点されるリスクがあるとはいえないからです。
「こんな変形どう思い付いたの？急にぶっ飛びすぎて逆に減点されるんじゃいの？」という反論があるかもしれませんが、自分自身、ましてや自分の友達がこの解法を使っていて減点されたことは一度もありません。
２°）自分で定めた係数が任意の数になった場合、それを\(0\)としてもよい。
0以外で計算したとしても結局その文字は最終的に一般項を求めた時点で相殺します。（実際に自分で確かめてみましょう。）ですので、初めから\(0\)としてしまったほうが記述が楽です。
あとがき
最後まで閲覧していただきありがとうございました。
今回は線形２項間漸化式の革命的な解法を紹介しましたがいかがだったでしょうか。もちろんこの手法が自分に合う・合わないはあると思いますが、漸化式の解法パターン暗記に疲れたという方は一度お手持ちの問題集の問題をこの手法で解いてみてはいかがでしょうか。（人によっては慣れるまでに時間がかかるかもしれません。）
今回扱ったような漸化式は難関大学では、おもに確率漸化式として確率の問題に現れることが多いですが、この解法を一度マスターしてしまえば、経験上ある程度複雑な漸化式でも解くことができます。
次回以降では、階比型、次数相異型、分数型の２項間漸化式および教科書では基本扱われていない３項間漸化式の発展例にも言及し、高校数学で扱う漸化式を網羅していくつもりです。
今後も定期的に更新していきますので、ブックマークやツイッターアカウントのフォローのほうぜひしてみてください！
当サイトがいいな、と思った方はぜひ知人・友人に勧めてみてください！
当サイトについての質問・問い合わせなどは当サイトのフォーラムへコメントまたは自分の個人用のツイッターアカウントにDMをくだされば幸いです。（アカウントは@skrdy0121です。）
最終更新：2020 9/18(Fri.)
