$ \DeclareMathOperator{\arccosh}{arccosh} \DeclareMathOperator{\arcsinh}{arcsinh} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\rot}{rot} \DeclareMathOperator{\grad}{grad} \DeclareMathOperator{\diver}{div} $

一般の線形漸化式の一般項

公開: 2012/08/01
この記事では、
\begin{equation} a_{n+1} = p_n a_n + q_n \end{equation}
(1)
をみたす数列 $\set{a_n}_{n=1,2,\cdots}$ の一般項を求めたいと思います。 ただし $\set{p_n}_{n=1,2,\cdots}, \set{q_n}_{n=1,2,\cdots}$ は既知の数列だとします。 なお「線形漸化式」の「線形」は、ここでは $a_n$ の高々一次式で表される、 ぐらいの意味であまり深い意味はありません。
途中の計算で特に難しい数学は一切使わないので、 漸化式を習いたての高校生でも (一応) 読めるはずです。 なので「現役高校生に負けてられるかっ」という理系大学生や、 腕に覚えのある高校生の方は本記事を読み進める前にぜひ一度、 自力で解いてみてください。
なお、ここでの議論は一つの数列に関する二項間漸化式の一般項を求めることに限定しますが、 より一般に多項間連立漸化式に対しても容易に一般化できます。 もし興味があれば、ぜひ考えてみてください。

1簡単に解ける形

さて、難しい問題を解くときの常套(じょうとう)手段ではありますが、 一般の場合を考える前に、まずは簡単な形を考えてみましょう。

1.1差分型

一般的な名称ではないのですが、この記事では $p_n \equiv 1$ の形の漸化式、
\begin{equation} a_{n+1} = a_n + q_n \end{equation}
(2)
を「差分型の漸化式」と呼ぶことにします。
この形の漸化式の一般項はすぐに求めることができます。
\begin{equation} a_n = a_{n-1} + q_{n-1} \end{equation}
(3)
の右辺の $a_{n-1}$ に対して、
\begin{equation} a_{n-1} = a_{n-2} + q_{n-2} \end{equation}
(4)
を代入して、
\begin{align*} a_n & = (a_{n-2} + q_{n-2}) + q_{n-1} \\ & = a_{n-2} + (q_{n-2} + q_{n-1}) \end{align*}
(5)
を得ます。 この手続きを繰り返し適用することで、
\begin{equation} a_n = a_1 + (q_1 + q_2 + \cdots + q_{n-1}) \end{equation}
(6)
を得ます。 もしくは総和記号 $\sum$ を用いて、
\begin{equation} a_n = a_1 + \sum_{k=1}^{n-1} q_k \end{equation}
(7)
が求めるべき一般項となります。

1.2比例型

こちらも一般的な名称ではありませんが、$q_n \equiv 0$ の形の漸化式、
\begin{equation} a_{n+1} = p_n a_n \end{equation}
(8)
を「比例型の漸化式」と呼ぶことにします。
こちらの一般項もすぐに求めることができます。
\begin{equation} a_n = p_{n-1} a_{n-1} \end{equation}
(9)
の右辺の $a_{n-1}$ に対して、
\begin{equation} a_{n-1} = p_{n-2} a_{n-2} \end{equation}
(10)
を代入して、
\begin{align*} a_n & = p_{n-1} \cdot (p_{n-2} a_{n-2}) \\ & = (p_{n-1} p_{n-2}) \cdot a_{n-2} \end{align*}
(11)
を得ます。 この手続きを繰り返し適用することで、
\begin{equation} a_n = (p_{n-1} p_{n-2} \cdots p_1) \cdot a_1 \end{equation}
(12)
を得ます。 もしくは総乗記号 $\prod$ を用いて、
\begin{equation} a_n = \left( \prod_{k=1}^{n-1} p_k \right) a_1 \end{equation}
(13)
が求めるべき一般項となります。

2練習問題

上で二種類の非常に特殊な場合について一般項が容易に求まることをみました。 逆に、この二種類のうちどちらかの形に帰着することが出来れば、容易に一般項が求まってしまう、 とも言うことができます[1]。 どちらかの形に帰着させる、と書きましたが、「帰着させる」とは具体的にどういうことをすればいいのでしょうか? 雰囲気を掴んでもらうために、いくつか例題を解いてみましょう。

2.1例題1: $a_{n+1} = 2a_n + 1$

$p_n \equiv 2, q_n \equiv 1$ の場合、
\begin{equation} a_{n+1} = 2a_n + 1 \end{equation}
(14)
を考えてみましょう。

2.1.1比例型に帰着させる

少し順番が前後してしまいますが、まずはじめに比例型に帰着することを考えます。
(14) 式を眺めると、
\begin{equation} a_{n+1} + 1 = 2 (a_n + 1) \end{equation}
(15)
と変形することができると分かります。 従って、$b_n := a_n + 1$ とおくと上の式は、
\begin{equation} b_{n+1} = 2b_n \end{equation}
(16)
となりますから、これは明らかに比例型の漸化式です。 これより与えられた漸化式を比例型の漸化式に帰着することができ、 上の方で行った議論により一般項は、
\begin{equation} b_n = \left( \prod_{k=1}^{n-1} 2 \right) b_1 = 2^{n-1} b_1 \end{equation}
(17)
と求まります。 従ってこの式に $b_n = a_n + 1, b_1 = a_1 + 1$ を代入して整理すると、
\begin{equation} a_n = 2^{n-1} (a_1 + 1) - 1 \end{equation}
(18)
と一般項を求めることが出来ました。

2.1.2差分型に帰着させる

(14) 式に対して (ややトリッキーな変形ではありますが) 両辺を $2^{n+1}$ で割ってあげれば、
\begin{equation} \frac{a_{n+1}}{2^{n+1}} = \frac{a_n}{2^n} + \frac{1}{2^{n+1}} \end{equation}
(19)
という式になるので、$b_n := a_n / 2^n$ とおいてあげると、
\begin{equation} b_{n+1} = b_n + \frac{1}{2^{n+1}} \end{equation}
(20)
となり、差分型の漸化式に帰着させることができます。 従って上の方で行った議論から一般項は、
\begin{equation} b_n = \sum_{k=1}^{n-1} \frac{1}{2^{k+1}} + b_1 = \frac{1/4 - 1/2^{n+1}}{1 - 1/2} + b_1 = \frac{1}{2} - \frac{1}{2^n} + b_1 \end{equation}
(21)
であると分かります。 従って $b_n = a_n / 2^n, b_1 = a_1 / 2$ を代入して整理することで、
\begin{equation} a_n = 2^{n-1} - 1 + 2^{n-1} a_1 = 2^{n-1} (a_1 + 1) - 1 \end{equation}
(22)
と一般項を求めることが出来ました。

2.2例題2: $a_{n+1} = na_n + 1$

さて、上の練習問題でなんとなく「差分型、もしくは比例型の漸化式に帰着させる」ということがどういうことか 分かっていただけたと思います[2]。 しかしいくらなんでも $p_n$$q_n$ も定数ではあまりにも簡単すぎてお粗末なので、 少しだけ難しくするために $p_n = n, q_n = 1$ と片方だけ $n$ に依存させてみます。 念の為、改めて漸化式を書くと、
\begin{equation} a_{n+1} = na_n + 1 \end{equation}
(23)
です。

2.2.1比例型に帰着させる

例題 1 と同様に、(23) 式を変形して、
\begin{equation} a_{n+1} - b_{n+1} = n (a_n - b_n) \end{equation}
(24)
という形に出来れば (ただし $b_n$ は何らかの数列) 比例型の漸化式に帰着できたことになり、 簡単に一般項が求まりそうです。 そこで上の (24) 式と与えられた漸化式 (23) 式を見比べると (両式の辺々を引くと) 、
\begin{equation} b_{n+1} = nb_n + 1 \end{equation}
(25)
を得るので、この式の解を一つ見つけることが出来れば目的は達成です、めでたしめでたし。
…と言いたいところですが、世の中そうは甘くありません。 上式は明らかに求めたかった漸化式である (23) 式と同一です。 この時点で手詰まり感満載です。 ここで「この方法じゃダメだ、諦めよう」というのは簡単ですが、折角なのでもう少し粘ってみましょう。
とても勘のいい人は $b_n$ として、
\begin{eqnarray*} b_n = & & (n-1) \times (n-2) \times \cdots \times 3 \times 2 \\ & + & (n-1) \times (n-2) \times \cdots \times 3 \\ & + & \hspace{3.5em} \vdots \\ & + & (n-1) \times (n-2) \\ & + & (n-1) \\ & + & 1 \end{eqnarray*}
(26)
とすると (25) 式を満たしそうだ、とひらめくかもしれません[3]。 実際この $b_n$$n$ をかけて $1$ を足してみると、
\begin{eqnarray*} nb_n+1 = & & n \times (n-1) \times \cdots \times 3 \times 2 \\ & + & n \times (n-1) \times \cdots \times 3 \\ & + & \hspace{3.5em} \vdots \\ & + & n \times (n-1) \\ & + & n \\ & + & 1 = b_{n+1} \end{eqnarray*}
(27)
となって、たしかに $b_{n+1} = nb_n + 1$ を満たしていることがわかります。 このまま書くと冗長なので、総和記号を使って書きなおすと、
\begin{equation} b_n = \sum_{k=1}^{n-1} \frac{(n-1)!}{k!} \end{equation}
(28)
となります。
従ってあとは始めに行った議論から、
\begin{equation} a_n - b_n = \left( \prod_{k=1}^{n-1} k \right) (a_1 - b_1) = (n-1)! \cdot (a_1 - b_1) \end{equation}
(29)
ですから、$b_1 = 0$[4] および $b_n$ に上で発見したものを代入して、
\begin{equation} a_n = \sum_{k=1}^{n-1} \frac{(n-1)!}{k!} + (n-1)! \cdot a_1 \end{equation}
(30)
と一般項を求めることが出来ました。
さて、無事に一般項は分かったわけですが、この方法では多くの人はできないと思います。 途中で $b_n$ を天下り的に与えてしまったのですが、これをパッと思いつくのは至難の業です。 今回は $p_n = n$ と非常に単純なものだったので、もしかしたら思いつける人もいるかもしれませんが、一般の形の場合には不可能に近いです。
途中で出てきた数列 $b_n$ はもとの数列 $a_n$ と全く同じ漸化式を満たしますが、 初期値が指定されていない ($b_1 = 0$ と決まっていてこちらが指定することができない) ため、 このようなものを初期値が特殊な値に固定されているという事で「特殊解」といいます。 そのため、ここで使った方法は「特殊解を使った解法」などと言われることがあります。

2.2.2差分型に帰着させる

前の例題と同様、少しトリッキーな変形になってしまいますが、(23) 式の両辺を $n!$ で割ってあげると、
\begin{equation} \frac{a_{n+1}}{n!} = \frac{a_n}{(n-1)!} + \frac{1}{n!} \end{equation}
(31)
となるので (分母と分子でひとつ分だけずれていて分かりにくいですが) $b_n := a_n/(n-1)!$ とおいてあげれば、
\begin{equation} b_{n+1} = b_n + \frac{1}{n!} \end{equation}
(32)
とできて、差分型の漸化式に変形できます。 従って一番初めの議論から $b_n$ の一般項は、
\begin{equation} b_n = \sum_{k=1}^{n-1} \frac{1}{k!} + b_1 \end{equation}
(33)
であり、$b_1 = a_1/0! = a_1$ および $b_n = a_n/(n-1)!$ を代入して整理することで、
\begin{equation} a_n = \sum_{k=1}^{n-1} \frac{(n-1)!}{k!} + (n-1)! \cdot a_1 \end{equation}
(34)
と一般項を求めることが出来ました。

[1]もちろん、この方法以外にも漸化式を解く方法は存在します。例えば母函数を使う方法などが有名です
[2]というかこれ以上分かりやすい説明はできないです、ゴメンナサイ (>o<) どうしてもわからない、という人は高校数学の教科書を引っ張り出して読んでみてください。 この説明よりもずっと詳しく、かつ分かりやすい解説が載っているはずです
[3]少なくとも自分には無理です (差分型に帰着させる方法で求めた答えをカンニングしてでっち上げました)
[4]$b_1 = 0$ であることはあまり自明ではありませんが、$b_2 = 1$ は明らかなので $b_2 = 1 \cdot b_1 + 1$ から正当化できます。

3一般の線形漸化式の一般項

3.1差分型に帰着させる

二つの簡単な例題についてそれぞれ「比例型」もしくは「差分型」の漸化式に帰着させることで一般項を求めてみたわけですが、 実際にどのように工夫をすれば一般項が求まるのか、というのが分かっていただけたでしょうか?
少し長くなってしまいましたが上の例題を参考にしながら、 そろそろ本題である $p_n, q_n$ が一般的な場合の一般項を求めて行きましょう。
まず方針として「差分型に帰着させる方法」をとることとします。 なぜなら二番目の例題で見たとおり、「比例型」の漸化式に帰着させる方法は、 特殊解を見つけるという非常に発見的な方法になっており、一般の場合にはとてもできそうにないからです[1]
しつこいですが、一般項を求めたい漸化式を再度書いてみると、
\begin{equation} a_{n+1} = p_n a_n + q_n \end{equation}
(35)
でした。 いままで $p_n$ は任意だとしてきましたが、これからは簡単のために $p_n \ne 0$ であることを仮定します。 もし $p_k = 0$ なる $k$ があった場合、数列の前の情報は一旦「忘れて」しまい、 それ以降は初項が $a_{k+1} = q_k$ である数列が続いていくと思うことができるため、このように仮定しても一般性はほとんど失われません。
さて、この仮定のもとで両辺を $p_n \cdot p_{n-1} \cdots p_1 = \prod_{k=1}^n p_k$ で割ってみます。 すると、
\begin{equation} \frac{a_{n+1}}{\prod_{k=1}^n p_k} = \frac{a_n}{\prod_{k=1}^{n-1} p_k} + \frac{q_n}{\prod_{k=1}^n p_k} \end{equation}
(36)
と変形できます。 ここで、
\begin{equation} b_n := \frac{a_n}{\prod_{k=1}^{n-1} p_k} \end{equation}
(37)
とおいてあげると、(36) 式は、
\begin{equation} b_{n+1} = b_n + \frac{q_n}{\prod_{k=1}^n p_k} \end{equation}
(38)
と変形できます。 これは明らかに差分型の漸化式ですので一般項はすぐに求まって、
\begin{equation} b_n = \sum_{l=1}^{n-1} \frac{q_l}{\prod_{k=1}^l p_k} + b_1 \end{equation}
(39)
です。 最後に $b_1 = a_1$ および $b_n = a_n / \prod_{k=1}^{n-1} p_k$ を代入して整理してあげることで、
\begin{equation} a_n = \sum_{l=1}^{n-1} \frac{\prod_{k=1}^{n-1} p_k}{\prod_{k=1}^{l} p_k} q_l + a_1 \prod_{k=1}^{n-1} p_k \end{equation}
(40)
もしくは、
\begin{equation} a_n = \sum_{l=1}^{n-1} \left[ \left( \prod_{k=l+1}^{n-1} p_k \right) q_l \right] + a_1 \prod_{k=1}^{n-1} p_k \end{equation}
(41)
と一般項を求めることが出来ました! めでたし、めでたし。

3.2線形漸化式の一般項の公式 (一般の場合)

公式 1: 線形漸化式の一般項 (一般の場合)
$\set{p_n}_{n=1,2,\cdots}, \set{q_n}_{n=1,2,\cdots}$ を既知の数列とし、任意の自然数 $n$ に対して $p_n \ne 0$ であると仮定する。 このとき漸化式、
\begin{equation} a_{n+1} = p_n a_n + q_n \hspace{1em} \text{for $n=1, 2, \cdots$} \end{equation}
(42)
を満たすような数列 $\set{a_n}_{n=1,2,\cdots}$ の一般項は、
\begin{equation} a_n = \sum_{l=1}^{n-1} \left[ \left( \prod_{k=l+1}^{n-1} p_k \right) q_l \right] + a_1 \prod_{k=1}^{n-1} p_k \end{equation}
(43)
で与えられる[2]
$p_n$$q_n$ の具体的な表式がわからないとこれ以上簡単な形に変形することはできません。 ですが折角なのでこの公式を用いて上で解いた例題の答えが再現できることを確認してみましょう。

3.3例題ふたたび

3.3.1例題1

$p_n = 2, q_n = 1$ を公式に代入して、
\begin{align*} a_n & = \sum_{l=1}^{n-1} \left[ \left( \prod_{k=l+1}^{n-1} 2 \right) \cdot 1 \right] + a_1 \prod_{k=1}^{n-1} 2 \\ & = \sum_{l=1}^{n-1} 2^{n-1} \cdot 2^{-l} + a_1 \cdot 2^{n-1} \\ & = 2^{n-1} (1-2^{-n+1}) + 2^{n-1} a_1 \\ & = 2^{n-1} (a_1 + 1) - 1 \end{align*}
(44)
となって、確かに前に求めた結果と一致します。

3.3.2例題2

$p_n = n, q_n = 1$ を公式に代入して、
\begin{align*} a_n & = \sum_{l=1}^{n-1} \left[ \left( \prod_{k=l+1}^{n-1} k \right) \cdot 1 \right] + a_1 \prod_{k=1}^{n-1} k \\ & = \sum_{l=1}^{n-1} (l+1) \times \cdots \times (n-1) + a_1 \cdot (n-1)! \\ & = \sum_{l=1}^{n-1} \frac{1 \times \cdots \times (n-1)}{1 \times \cdots \times l} + (n-1)! \cdot a_1 \\ & = \sum_{l=1}^{n-1} \frac{(n-1)!}{l!} + (n-1)! \cdot a_1 \end{align*}
(45)
となって、確かに前に求めた結果と一致します。

[1]もしできる方法を見つけたら是非教えてください (-_-;)
[2]ただし右辺の総乗記号の開始値が終了値よりも大きな場合は $1$ であると解釈してください