漸化式の解法あれこれ： a_{n+1} = a_n + f(n)

初項と漸化式が

　　 ${ \displaystyle \begin{align*} \begin{cases} a_1\quad = a \\ a_{n+1} = a_n + f(n) \end{cases} \end{align*} }$

で与えられる数列 ${ a_n }$ の一般項を得る方法を見ていきましょう。　ただし ${ f(n) }$ は ${ n }$ の何らかの関数です。

解法

数列 ${ a_n }$ の階差数列を ${ b_n }$ とします：

　　 ${ \displaystyle \begin{align*} b_n = a_{n+1} - a_n \end{align*} }$

このとき漸化式より

　　 ${ \displaystyle \begin{align*} b_n = f(n) \end{align*} }$

となり、階差数列の一般項は分かりました。　ここで、以前導いた、階差数列から元の数列を求める公式

　　 ${ \displaystyle \begin{align*} a_n = \begin{cases} a & (n=1) \\ \displaystyle{ a + \sum_{k=1}^{n-1} b_k} & (n \ge 2) \end{cases} \end{align*} }$

より

　　 ${ \displaystyle \begin{align*} a_n = \begin{cases} a & (n=1) \\ \displaystyle{ a + \sum_{k=1}^{n-1} f(k)} & (n \ge 2) \end{cases} \end{align*} }$

となります。　まぁ、公式をそのまま書いただけですが・・・。　ちなみに、数列が第0項から始まる場合 ( ${ a_0 = a }$ ) は

　　 ${ \displaystyle \begin{align*} a_n = \begin{cases} a & (n=0) \\ \displaystyle{ a + \sum_{k=0}^{n-1} f(k)} & (n \ge 1) \end{cases} \end{align*} }$

です。

いつすべての ${ n }$ について1つの形でかけるのか？

さて、具体的な問題を解いてみると、大抵の場合は ${ n=1 }$ のときと ${ n \ge 2 }$ の場合をまとめて1つの式で書けることが分かります。　では、どういった条件が満たされていれば ${ n=1 }$ の場合を別に書かずに済むのでしょうか？　この条件を求めるために、まず

　　 ${ \displaystyle \begin{align*} F(n) = \sum_{k=1}^{n-1} f(n) \end{align*} }$

とおきましょう。　このとき、 ${ n \ge 2 }$ の ${ a_n }$ は

　　 ${ \displaystyle \begin{align*} a_n = a + F(n-1) \end{align*} }$

と書けます。　ここで、 ${ F(n) }$ は定義より ${ n \ge 2 }$ でなければいけませんが、n の関数形が求まっているとして、上式で ${ n = 1 }$ とおくと

　　 ${ \displaystyle \begin{align*} a_1 = a + F(0) \end{align*} }$

となります。　この式より、 ${ n=1 }$ の場合も ${ n \ge 2 }$ のときと同じように書けるためには

　　 ${ \displaystyle \begin{align*} F(0) = 0 \end{align*} }$

が成り立っていればいいことが分かります。　では、典型的な ${ f(n) }$ でこれが成り立っているかどうかを見ていきましょう。

${ f(n) }$ が定数のとき

まずは最も簡単で最もつまらない（？）場合として

　　 ${ \displaystyle \begin{align*} f(n) &= f & \left(a_{n+1} = a_n + f\right) \end{align*} }$

ただし ${ f }$ は定数のとき。

　　 ${ \displaystyle \begin{align*} F(n) &= \sum_{k=1}^n f \\ &= fn \end{align*} }$

より ${ F(0) = 0 }$ となって、このときは ${ a_n }$ を1つの形にまとめて書けます：

　　 ${ \displaystyle \begin{align*} a_n = a + f(n-1) \end{align*} }$

これは初項 ${ a }$ 公差 ${ f }$ の等差数列ですね。

${ f(n) }$ が等差数列のとき

${ f(n) }$ が初項 ${ f }$ 、公差 ${ d }$ の等差数列のとき、つまり

　　 ${ \displaystyle \begin{align*} f(n) &= f + (n-1)d & \left(a_{n+1} = a_n + f + (n-1)d\right) \end{align*} }$

のとき。　 ${ F(n) }$ を計算すると

　　 ${ \displaystyle \begin{align*} F(n) &= \sum_{k=1}^n\left\{f + (k-1)d\right\} \\ &= \frac{1}{2}n\left\{2f + (n-1)d\right\} \end{align*} }$

となるので、 ${ F(0) = 0 }$ となって、 ${ a_n }$ を1つの形にまとめて書けます：

　　 ${ \displaystyle \begin{align*} a_n = a + \frac{1}{2}(n-1)\left\{2f + (n-2)d\right\} \end{align*} }$

${ f(n) }$ が等比数列のとき

${ f(n) }$ が初項 ${ f }$ 、公比 ${ r\,(r \ne 1) }$ の等比数列のとき

　　 ${ \displaystyle \begin{align*} f(n) &= f r^{n-1} & \left(a_{n+1} = a_n + fr^{n-1}\right) \end{align*} }$

となるので、 ${ F(n) }$ は

　　 ${ \displaystyle \begin{align*} F(n) &= \sum_{k=1}^n fr^{n-1} \\ &= \frac{f(r^n - 1)}{r-1} \end{align*} }$

となって、 ${ F(0) = 0 }$ 。　よって、 ${ a_n }$ を1つの形にまとめて書けます：

　　 ${ \displaystyle \begin{align*} a_n = a + \frac{f(r^{n-1} - 1)}{r-1} \end{align*} }$

ちなみに、 ${ r=1 }$ のときは ${ f(n) }$ が定数のときになりますね。　また、特に ${ f = r }$ のとき、漸化式は

　　 ${ \displaystyle \begin{align*} a_{n+1} = a_n + r^n \end{align*} }$

となり、このときの一般項は

　　 ${ \displaystyle \begin{align*} a_n = a + \frac{r^n - r}{r-1} \end{align*} }$

となります。

${ f(n) }$ が（等差数列）×（等比数列）の形のとき

次は ${ f(n) }$ が（等差数列）×（等比数列）の形の場合、つまり ${ p,\,q,\,r\,(r \ne 1) }$ を定数として

　　 ${ \displaystyle \begin{align*} f(n) &= (pn + q)r^{n-1} & \left(a_{n+1} = a_n + (pn+q)r^{n-1}\right) \end{align*} }$

という形の場合を考えましょう。　このとき

　　 ${ \displaystyle \begin{align*} f(n) = pnr^{n-1} + qr^{n-1} \end{align*} }$

と展開して、第1項、第2項を別々に和を考えましょう。　第1項について、これは以前の記事「数列 [tex:{ nr^{n-1} }] の和」で和を計算していて、

　　 ${ \displaystyle \begin{align*} \sum_{k=1}^n pkr^{k-1} = \frac{p\left\{1-(n+1)r^n + nr^{n+1}\right\}}{(1-r)^2} \end{align*} }$

となります。　また、第2項は単なる等比級数で

　　 ${ \displaystyle \begin{align*} \sum_{k=1}^n qr^{k-1} = \frac{q(1-r^n)}{1-r} \end{align*} }$

を得ます。　よって

　　 ${ \displaystyle \begin{align*} F(n) = \frac{p\left\{1-(n+1)r^n + nr^{n+1}\right\}}{(1-r)^2} + \frac{q(1-r^n)}{1-r} \end{align*} }$

となり、 ${ F(0) = 0 }$ となります。　ということで ${ a_n }$ は1つの形にまとめて書けて

　　 ${ \displaystyle \begin{align*} a_n = a + \frac{p\left\{1-nr^{n-1} + (n-1)r^n\right\}}{(1-r)^2} + \frac{q(1-r^{n-1})}{1-r} \end{align*} }$

${ f(n) }$ がある関数の差分のような形で書けるとき

ちょっとこの場合の ${ f(n) }$ の条件を文章で説明しにくいですが、数式で書くと以下のような形になる場合です：　 ${ g(x) }$ をある関数（ ${x }$ が整数値で発散などしない）、 ${ m }$ を自然数として

　　 ${ \displaystyle \begin{align*} f(n) &= g(n) - g(n+m) & \left(a_{n+1} = a_n + g(n) - g(n+m)\right) \end{align*} }$

と書ける。　例えば、 ${ f(x) = \frac{1}{x},\,m=1 }$ のとき

　　 ${ \displaystyle \begin{align*} f(n) = \frac{1}{n} - \frac{1}{n+1} = \frac{1}{n(n+1)} \end{align*} }$

また、 ${ f(x) = \sqrt{x},\,m=1 }$ のとき

　　 ${ \displaystyle \begin{align*} f(n) = \sqrt{n} - \sqrt{n+1} = -\frac{1}{\sqrt{n} + \sqrt{n+1}} \end{align*} }$

などとなります。

このとき、以前の記事「とある級数に対する双対性」で得た結果より

　　 ${ \displaystyle \begin{align*} F(n) &= \sum_{k=1}^n\left\{g(k) - g(k + m)\right\} \\ &= \sum_{k=1}^m\left\{g(k) - g(k+n)\right\} \end{align*} }$

となって、 ${ F(0) = 0 }$ となります。　よって ${ a_n }$ は1つの形にまとめて書けて

　　 ${ \displaystyle \begin{align*} a_n = a + \sum_{k=1}^m\left\{g(k) - g(k+n-1)\right\} \end{align*} }$

${ f(n) }$ が ${ n }$ の冪乗のとき

${ m }$ を自然数の定数として ${ f(n) }$ が

　　 ${ \displaystyle \begin{align*} f(n) &= n^m & \left(a_{n+1} = a_n + n^m\right) \end{align*} }$

の形の場合、これまた以前の記事「自然数の冪乗和の公式を導いてみるよ」より

　　 ${ \displaystyle \begin{align*} F(n) = \sum_{i=0}^m \frac{(-)^i B_i \,_{m+1}C_i}{m+1} n^{m-i+1} \end{align*} }$

となります（ ${ B_n }$ はベルヌーイ数、 ${ \,_nC_r }$ は二項係数）。　ここに現れている ${ i }$ についての和は0から ${ m }$ ですが、この範囲において ${ n }$ の冪は常に1以上なので、結局 ${ F(0) = 0 }$ とあいなります。　よって ${ a_n }$ は1つの形にまとめて書けて

　　 ${ \displaystyle \begin{align*} a_n = a + \sum_{i=0}^m \frac{(-)^i B_i \,_{m+1}C_i}{m+1} (n-1)^{m-i+1} \end{align*} }$

を得ます。

外挿可能とでも言っておくか

上記のように ${ F(n) }$ が ${ F(0) = 0 }$ を満たすとき、和をとる前の関数（というか実質的には数列だけど） ${ f(n) }$ を外挿可能 (extrapolatable) とでも呼んでおきましょう。　全く公式な用語ではありませんけど（他の意味でこの用語が使われてたらごめんなさい、無関係です）。　上記で導いたように

定数
等差数列
等比数列
（等差数列）×（等比数列）
差分のような形の数列 ${ g(n) - g(n+m) }$
${ n }$ の冪乗和

は外挿可能でした。　また、 ${ \sum }$ の線形性より、外挿可能関数の線型結合も外挿可能ですね。　これで、高校に出てきそうな数列は外挿可能らしいことが分かりました。

では、どんな関数（数列）が外挿可能ではないのか？

いろいろな関数について、それが外挿可能かどうかを計算してみましたが、大抵のものは外挿可能だということが分かりました。　では逆に、どのような関数が外挿可能ではないのか？　もし全ての関数が外挿可能なら、いちいち場合分けして書く必要ないんじゃないか？と疑問が湧いてきます。　まぁ、残念ながら外挿可能でない関数を作ることは可能です。　ちょっと無理矢理な感じがしますが、以下のような f(n) は外挿可能ではありません：

　　 ${ \displaystyle \begin{align*} f(n) = \begin{cases} 2 & (n=1) \\ n & (n \ge 2) \end{cases} \end{align*} }$

実際、 ${ F(n) }$ を計算すると

　　 ${ \displaystyle \begin{align*} F(n) = \frac{1}{2}n(n+1)+1 \end{align*} }$

となり、 ${ F(0) = 1 \ne 0 }$ より、この ${ f(n) }$ は外挿可能ではありません。　あら残念。　ということで、この形の漸化式を解くときや階差数列からもとの数列を求めたいときは、 ${ n=1 }$ と ${ n \ge 2 }$ の場合をキチンと場合分けして解きましょう。