階乗を用いる漸化式の解法

漸化式の ana_nan1a_{n-1} の係数に nn が含まれている場合,両辺に何かしらかけたり割ったりして f(n+1)an+1f(n+1)a_{n+1}f(n)anf(n)a_n を作り出せばうまくいくことが多い

かけたり割ったりするものは階乗とは限りませんが,ここでは階乗が活躍する例題を3つ解説します。

階乗をかけることで漸化式を解く

例題1

a1=1a_1=1 のもとで漸化式 (n+1)an+1=an+1n!(n+1)a_{n+1}=a_n+\dfrac{1}{n!} を解け。

両辺に n!n! をかけるとうまくいきます。これは右辺に 1n!\dfrac{1}{n!} があるので分かりやすい例です。

解答

(n+1)!an+1=n!an+1(n+1)!a_{n+1}=n!a_n+1 より,n!an=bnn!a_n=b_n とおくと,

bn+1=bn+1 b_{n+1}=b_n+1

よって bnb_{n} は公差 11 の等差数列なので

bn=b1+n1=n b_{n}=b_{1}+n-1=n

よって an=bnn!=1(n1)! a_n=\dfrac{b_n}{n!}=\dfrac{1}{(n-1)!}

漸化式を観察すると,「大雑把に見れば an+1a_{n+1}ana_n1n\dfrac{1}{n} 倍くらいなので爆発的に 00 に近づく」ことが分かります。よって,n!ann!a_n を新たな数列 bnb_n でおくと減少を抑えられてうまくいくかもしれないと期待できます。

追記:この発想は少々強引な気もします。

階乗で割ることで漸化式を解く

例題2

a1=2a_1=2 のもとで漸化式 an+1=(n+1)an+na_{n+1}=(n+1)a_n+n を解け。

両辺を (n+1)!(n+1)! で割るとうまくいきます。和の計算には部分分数分解など差に分解する4つの恒等式の恒等式3を用います。

解答

an+1(n+1)!=ann!+n(n+1)!\dfrac{a_{n+1}}{(n+1)!}=\dfrac{a_n}{n!}+\dfrac{n}{(n+1)!} より, ann!=bn\dfrac{a_{n}}{n!}=b_{n} とおくと,

bn+1=bn+n(n+1)! b_{n+1}=b_{n}+\dfrac{n}{(n+1)!}

これは階差数列型なので部分分数分解のノリで n(n+1)!\dfrac{n}{(n+1)!}f(n+1)f(n)f(n+1)-f(n) の形にしようと試みる:

n(n+1)!=1n!1(n+1)! \dfrac{n}{(n+1)!}=\dfrac{1}{n!}-\dfrac{1}{(n+1)!}

よって,bk+1bk=1k!1(k+1)!b_{k+1}-b_{k}=\dfrac{1}{k!}-\dfrac{1}{(k+1)!}

これを利用して bnb_n を求める。

bn=b1+k=1n1(bk+1bk)=2+k=1n1(1k!1(k+1)!)=2+11n!=31n!\begin{aligned} b_n &= b_1 + \sum_{k=1}^{n-1} (b_{k+1}-b_{k})\\ &= 2+\sum_{k=1}^{n-1}(\dfrac{1}{k!}-\dfrac{1}{(k+1)!})\\ &=2+1-\dfrac{1}{n!}\\ &=3-\dfrac{1}{n!} \end{aligned}

よって,an=n!bn=3(n!)1a_n=n!b_{n}=3(n!)-1

漸化式を観察すると,「大雑把に見れば an+1a_{n+1}ana_nnn 倍くらいで爆発的に大きくなる」ことが分かります。よって,ann!\dfrac{a_n}{n!} を新たな数列 bnb_n でおくと爆発を抑えられてうまくいくかもしれないと期待できます。

追記:この発想は少々強引な気もします。

三項間漸化式にも使える

攪乱順列(完全順列)の個数を求める公式で登場した漸化式です。

例題3

a2=1,a3=2a_2=1,\:a_3=2 のもとで an=(n1)(an1+an2)a_n=(n-1)(a_{n-1}+a_{n-2}) を解け。

例題2に近いタイプです。両辺を n!n! で割るとうまくいきます。

解答

ann!=n1n!an1+1nan2(n2)! \dfrac{a_n}{n!}=\dfrac{n-1}{n!}a_{n-1}+\dfrac{1}{n}\dfrac{a_{n-2}}{(n-2)!} より,ann!=bn\dfrac{a_{n}}{n!}=b_{n} とおくと, bn=n1nbn1+1nbn2 b_n=\dfrac{n-1}{n}b_{n-1}+\dfrac{1}{n}b_{n-2}

次の変形を思いつくのが少し難しい:

bnbn1=1n(bn1bn2) b_n-b_{n-1}=\dfrac{-1}{n} (b_{n-1}-b_{n-2})

これを繰り返し用いると,

bnbn1=(1)n3n(n1)4(b3b2)=(1)n1n(n1)4(1312)=(1)nn!\begin{aligned} b_n-b_{n-1} &= \dfrac{(-1)^{n-3}}{n\cdot (n-1)\cdots 4} (b_3-b_2)\\ &=\dfrac{(-1)^{n-1}}{n\cdot (n-1)\cdots 4} (\dfrac{1}{3}-\dfrac{1}{2})\\ &= \dfrac{(-1)^n}{n!} \end{aligned}

bnb_n の階差数列が求まったので足し合わせればよい:

an=n!bn=n!(b2+k=3n(1)kk!)=n!k=2n(1)kk!\begin{aligned} a_n&=n!b_n\\ &=n!(b_2+\sum_{k=3}^{n}\dfrac{(-1)^k}{k!})\\ &=n!\sum_{k=2}^{n}\dfrac{(-1)^k}{k!} \end{aligned}

漸化式の中でも比較的難しい部類の問題です。

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