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

漸化式(ぜんかしき)についてわかりやすく解説します。漸化式の意味から,解き方12パターンをすべて紹介します。

漸化式とは

  • 2,5,8,11,...2,5,8,11,... のように,数がたくさん並んでいるものを考えます。数列と呼びます。

  • 数列の nn 番目の数を ana_n と書きます。上の例だと a1=2,a2=5,a3=8,...a_1=2,a_2=5,a_3=8,... です。

  • 漸化式とは,数列において「前の数」から「新しい数」を作る規則のことです。 漸化式

漸化式の例

an=an1+3a_n=a_{n-1}+3

は漸化式である。この漸化式は,nn 番目の数」は「n1n-1 番目の数」に 33 を加えたものという意味の式。

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

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

例題1

a1=2a_1=2an=an1+3a_n=a_{n-1}+3 という漸化式で表される数列の一般項を計算せよ。

この漸化式は,さきほど見たように,nn 番目の数」は「n1n-1 番目の数」に 33 を加えたものという意味です。つまりこの数列は,初項が 22 で,公差が 33 である等差数列です。よって nn 番目の数は,

an=2+3×(n1)=3n1a_n=2+3\times(n-1)=3n-1

となります。

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

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

例題2

a1=3a_1=3an=2an1a_n=2a_{n-1} という漸化式で表される数列の一般項を計算せよ。

この漸化式は,nn 番目の数」は「n1n-1 番目の数」を 22 倍したものという意味です。つまりこの数列は,初項が 33 で,公比が 22 である等比数列です。よって nn 番目の数は,

an=3×2n1a_n=3\times 2^{n-1}

となります。

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

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

例題3

a1=1a_1=1an=an1+na_n=a_{n-1}+n という漸化式で表される数列の一般項を計算せよ。

漸化式を繰り返し使ってみると,

an=an1+n=an2+(n1)+n=an3+(n2)+(n1)+n==a1+k=2nka_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までの和の公式を使うと,

k=2nk=12n(n+1)1\displaystyle\sum_{k=2}^n k=\dfrac{1}{2}n(n+1)-1

となるので,結局

an=12n(n+1)a_n=\dfrac{1}{2}n(n+1)

となります。

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

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

例題4

a1=1a_1=1an+1=2an+3a_{n+1}=2a_n+3 という漸化式で表される数列の一般項を計算せよ。

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

よって,{an+3}\{a_n+3\} は公比が 22 の等比数列です。そして,初項は a1+3=4a_1+3=4 です。よって,

an+3=4×2n1a_n+3=4\times 2^{n-1}

よって,an=2n+13a_n=2^{n+1}-3

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

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

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

例題5

a1=1a_1=1a2=1a_2=1an+2=5an+16ana_{n+2}=5a_{n+1}-6a_n という漸化式を解け。

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

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

また,三項間漸化式が解ければ,有名なフィボナッチ数列の一般項を計算することもできます。→フィボナッチ数列の7つの性質(一般項・黄金比・互いに素)

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

漸化式の解き方6:累乗を含む二項間漸化式

例題6

a1=1a_1=1an+1=3an2na_{n+1}= 3a_n - 2^n という漸化式を解け。

累乗が入った漸化式の解き方は,knk^n をかけたり割ったりすることで,より単純な漸化式に帰着できる場合が多いです。例えば,両辺を kn+1k^{n+1} などで割って bn=anknb_n = \dfrac{a_n}{k^n} とおくことで,bnb_n に関する漸化式が得られます。

解き方

与式の両辺を 2n+12^{n+1} で割ると an+12n+1=32an2n12 \dfrac{a_{n+1}}{2^{n+1}} = \dfrac{3}{2} \dfrac{a_n}{2^n} - \dfrac{1}{2} となる。ここで bn=an2nb_n = \dfrac{a_n}{2^n} とおくと, bn+1=32bn122bn+1=3bn1 b_{n+1} = \dfrac{3}{2} b_n - \dfrac{1}{2}\\ 2b_{n+1} = 3 b_n - 1 となる。また b1=12b_1 = \dfrac{1}{2} となる。解き方4により,これを解くと bn=13(32)n+1b_n = - \dfrac{1}{3} \left( \dfrac{3}{2} \right)^n + 1 が得られる。

こうして an=2nbn=2n3n1\begin{aligned} a_n &= 2^n b_n\\ &= 2^n - 3^{n-1} \end{aligned} となる。

この後登場する階乗を含む漸化式と似た変形です。

難しい漸化式の解き方

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

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

例題7

a1=1a_1=1an+1=2an+3n2a_{n+1}=2a_n+3n-2

このような,an+1=pan+f(n)a_{n+1}=pa_n+f(n) 型の漸化式は,階差数列を何度も取ることで解けます。

詳細:f(n)を含む二項間漸化式の2通りの解き方

例題8

a1=1a_1=1an+1=2anan+4a_{n+1}=\dfrac{2a_n}{a_n+4}

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

例題9

a1=2a_1=2b1=1b_1=-1 のもとで,連立漸化式

an+1=3an+bna_{n+1}=3a_n+b_n
bn+1=2an+2bnb_{n+1}=2a_n+2b_n

を解け。

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

例題10

a1=1a_1=1(n+1)an+1=an+1n!(n+1)a_{n+1}=a_n+\dfrac{1}{n!}

これは6で登場した累乗を含む漸化式と解き方は近いです。

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

例題11

an+1=4an(1an)a_{n+1}=4a_n(1-a_n)

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

例題12

c0=1,cn+1=i=0ncicnic_0=1, c_{n+1}=\displaystyle\sum_{i=0}^nc_ic_{n-i}

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

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

漸化式の応用

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

Tag:数学Bの教科書に載っている公式の解説一覧