2014/08/25

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

分野: 数列  レベル: 最難関大学

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


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

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

例題1

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

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

解答

$(n+1)!a_{n+1}=n!a_n+1$ より,
$n!a_n=b_n$ とおくと,
$b_{n+1}=b_n+1$
よって $b_{n}$ は公差 $1$ の等差数列なので
$b_{n}=b_{1}+n-1=n$
よって $a_n=\dfrac{b_n}{n!}=\dfrac{1}{(n-1)!}$

漸化式を観察すると,「大雑把に見れば $a_{n+1}$ は $a_n$ の $\dfrac{1}{n}$ 倍くらいなので爆発的に $0$ に近づく」ことが分かります。よって,$n!a_n$ を新たな数列 $b_n$ でおくと減少を抑えられてうまくいくかもしれないと期待できます。
追記:この発想は少々強引な気もします。

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

例題2

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

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

解答

$\dfrac{a_{n+1}}{(n+1)!}=\dfrac{a_n}{n!}+\dfrac{n}{(n+1)!}$ より,
$\dfrac{a_{n}}{n!}=b_{n}$ とおくと,
$b_{n+1}=b_{n}+\dfrac{n}{(n+1)!}$
これは階差数列型なので部分分数分解のノリで $\dfrac{n}{(n+1)!}$ を $f(n+1)-f(n)$ の形にしようと試みる:
$\dfrac{n}{(n+1)!}=\dfrac{1}{n!}-\dfrac{1}{(n+1)!}$
よって,$b_{k+1}-b_{k}=\dfrac{1}{k!}-\dfrac{1}{(k+1)!}$

これを利用して $b_n$ を求める。
$b_n=b_1+\displaystyle\sum_{k=1}^{n-1}(b_{k+1}-b_{k})\\
=2+\displaystyle\sum_{k=1}^{n-1}(\dfrac{1}{k!}-\dfrac{1}{(k+1)!})\\
=2+1-\dfrac{1}{n!}\\
=3-\dfrac{1}{n!}$

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

漸化式を観察すると,「大雑把に見れば $a_{n+1}$ は $a_n$ の $n$ 倍くらいで爆発的に大きくなる」ことが分かります。よって,$\dfrac{a_n}{n!}$ を新たな数列 $b_n$ でおくと爆発を抑えられてうまくいくかもしれないと期待できます。
追記:この発想は少々強引な気もします。

三項間漸化式にも使える

攪乱順列の公式で登場した漸化式です。

例題3

$a_2=1,\:a_3=2$ のもとで $a_n=(n-1)(a_{n-1}+a_{n-2})$ を解け。

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

解答

$\dfrac{a_n}{n!}=\dfrac{n-1}{n!}a_{n-1}+\dfrac{1}{n}\dfrac{a_{n-2}}{(n-2)!}$ より,
$\dfrac{a_{n}}{n!}=b_{n}$ とおくと,$b_n=\dfrac{n-1}{n}b_{n-1}+\dfrac{1}{n}b_{n-2}$
次の変形を思いつくのが少し難しい:
$b_n-b_{n-1}=\dfrac{-1}{n}(b_{n-1}-b_{n-2})$
これを繰り返し用いると,
$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!}$
$b_n$ の階差数列が求まったので足し合わせればよい:
$a_n=n!b_n\\
=n!(b_2+\displaystyle\sum_{k=3}^{n}\dfrac{(-1)^k}{k!})\\
=n!\displaystyle\sum_{k=2}^{n}\dfrac{(-1)^k}{k!}$

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

Tag: 漸化式の解き方と応用例まとめ

分野: 数列  レベル: 最難関大学