最終更新:2021/01/05

漸化式の解き方11パターンと応用例まとめ

分野: まとめ    

  • 漸化式の意味,
  • 漸化式の解き方(基礎から超難問まで11パターン)
  • 漸化式の応用4種類

を整理しました。

漸化式とは

漸化式(ぜんかしき)とは,大雑把に言うと,「前の数字」から「新しい数字」を作る規則のことです。

例えば,
$a_n=a_{n-1}+3$
という漸化式について考えてみます。この漸化式は,
「$n$ 番目の数」は「$n-1$ 番目の数」に $3$ を加えたものという意味です。

例えば $a_1=2$ という条件のもとで漸化式を適用すると,
$a_2=a_1+3=5$
$a_3=a_2+3=8$
$a_4=a_3+3=11$
のように,数列の各項を計算することができます。

漸化式の解き方1:等差数列型

例題1:
$a_1=2$,$a_n=a_{n-1}+3$ という漸化式で表される数列の一般項を計算してみましょう。

この漸化式は,さきほど見たように,「$n$ 番目の数」は「$n-1$ 番目の数」に $3$ を加えたものという意味です。つまり,この数列は,初項が $2$ で,公差が $3$ である等差数列です。よって $n$ 番目の数は,
$a_n=2+3\times(n-1)=3n-1$
となります。

ポイント:
このように,$a_n=a_{n-1}+d$ というタイプの漸化式は,等差数列を理解していれば解くことができます。

漸化式の解き方2:等比数列型

例題2:
$a_1=3$,$a_n=2a_{n-1}$ という漸化式で表される数列の一般項を計算してみましょう。

この漸化式は,「$n$ 番目の数」は「$n-1$ 番目の数」を $2$ 倍したものという意味です。つまり,この数列は,初項が $3$ で,公比が $2$ である等比数列です。よって $n$ 番目の数は,
$a_n=3\times 2^{n-1}$
となります。

ポイント:
このように,$a_n=ra_{n-1}$ というタイプの漸化式は,等比数列を理解していれば解くことができます。

漸化式の解き方3:階差数列型

例題3:
$a_1=1$,$a_n=a_{n-1}+n$ という漸化式で表される数列の一般項を計算してみましょう。

漸化式を繰り返し使ってみると,
$a_n=a_{n-1}+n\\
=a_{n-2}+(n-1)+n\\
=a_{n-3}+(n-2)+(n-1)+n\\
=\cdots\\
=a_1+\displaystyle\sum_{k=2}^n k$
となります。ここで,1からnまでの和の公式を使うと,
$\displaystyle\sum_{k=2}^n k=\dfrac{1}{2}n(n+1)-1$
となるので,結局
$a_n=\dfrac{1}{2}n(n+1)$
となります。

ポイント:
このように,$a_n=a_{n-1}+f(n)$ というタイプの漸化式は,$f(n)$ の和を計算することで解くことができます。

漸化式の解き方4:一次の二項間漸化式

例題4:
$a_1=1$,$a_{n+1}=2a_n+3$ という漸化式で表される数列の一般項を計算してみましょう。

漸化式は,
$a_{n+1}+3=2(a_n+3)$
と変形できます(※)

よって,$\{a_n+3\}$ は公比が $2$ の等比数列です。そして,初項は $a_1+3=4$ です。よって,
$a_n+3=4\times 2^{n-1}$
よって,$a_n=2^{n+1}-3$

※なぜその変形が思いつくのか?
→特性方程式 $\alpha=2\alpha+3$ の解が $\alpha=-3$ だからです。詳しくはf(n)を含む二項間漸化式の2通りの解き方 の最初の例題を参照。

ポイント:
このように,$a_{n+1}=pa_n+q$ というタイプの漸化式は,平行移動して等比数列にすることで解くことができます。

漸化式の解き方5:一次の三項間漸化式

例題5:
$a_1=1$,$a_2=1$,$a_{n+2}=5a_{n+1}-6a_n$ という漸化式を解いてみましょう。

答えは,$a_n=2^n-3^{n-1}$ になります。

$a_{n+2}=pa_{n+1}+qa_{n}$ という三項間漸化式の解き方は3通りあります。詳細は,三項間漸化式の3通りの解き方

また,三項間漸化式が解ければ,有名なフィボナッチ数列の一般項を計算することもできます。
フィボナッチ数列の一般項と数学的帰納法

また,一般に一次の $k$ 項間漸化式については,
漸化式の特性方程式の意味とうまくいく理由
で解説しています。

難しい漸化式の解き方

上記の5パターンが解ければ漸化式の基礎はバッチリです。

ここからは,より難しい漸化式を一気に紹介します。それぞれ説明が長くなるので,詳細はリンク先の記事で詳しく説明しています。

例題6:
$a_1=1$,$a_{n+1}=2a_n+3n-2$

このような,$a_{n+1}=pa_n+f(n)$ 型の漸化式は,階差数列を何度も取ることで解けます。
詳細:f(n)を含む二項間漸化式の2通りの解き方

例題7:
$a_1=1$,$a_{n+1}=\dfrac{2a_n}{a_n+4}$

一次分数型の漸化式は,必要なら平行移動した上で逆数を取ることで解けます。
一次分数型の漸化式の解法と例題

例題8:
$a_1=2$,$b_1=-1$ のもとで,連立漸化式
$a_{n+1}=3a_n+b_n$
$b_{n+1}=2a_n+2b_n$
を解け。

連立漸化式は,3通りの解き方があります。例えば,$b_n$ を消去すると,三項間漸化式に帰着させることができます。
連立漸化式の3通りの解き方

例題9:
$a_1=1$,$(n+1)a_{n+1}=a_n+\dfrac{1}{n!}$

階乗を含む置き換えを使うことで,漸化式が解ける場合があります。
階乗を用いる漸化式の解法

例題10:
$a_{n+1}=4a_n(1-a_n)$

一見解けないけど三角関数を用いることで一般項が表せる,有名な漸化式です。
詳細:ロジスティック写像と漸化式

例題11:
$c_0=1, c_{n+1}=\displaystyle\sum_{i=0}^nc_ic_{n-i}$

カタラン数と呼ばれる有名な数字を表す漸化式です。
カタラン数の意味と漸化式
数列の母関数とその応用例

ちなみに,解けない漸化式というのもたくさん存在します。つまり,上の11個の例題のように「漸化式で表される数列の一般項が $n$ のきれいな式で表せる」のはむしろ特別な場合と言えます。

漸化式の応用

破産の確率と漸化式
漸化式は場合の数,確率の問題でも頻繁に顔を出します。

sinのn乗,cosのn乗の積分公式
$n$ 乗の積分といえば部分積分&漸化式。積分にも漸化式が登場。

漸化式で表される数列の極限
漸化式は極限にも登場します。一般項が求まらない場合でも数列の極限なら求まる場合もあります。

漸化式を用いた関数方程式の解法
関数方程式にまで漸化式が登場。

漸化式は数学のいろいろな分野に顔を出す重要な道具です。