階差型漸化式 aₙ₊₁ = aₙ + f(n) - 差を足し上げて一般項を出す

$a_{n + 1} = a_{n} + f (n)$ は、次の項へ進むときの増え方が $f (n)$ で決まっている漸化式です。階差型といいます。

$a_{n + 1} - a_{n} = f (n)$

増え方が分かっているので、あとは初項から足し上げるだけ。 $a_{1}$ に $f (1), f (2), \dots$ を順に積み上げれば $a_{n}$ に届きます。

$a_{n} = a_{1} + k = 1 \sum n - 1 f (k) (n \geq 2)$

階段を上るように

$a_{1}$ から $a_{n}$ までに通る段の数は $n - 1$ 個です。 $n$ 個ではありません。

橙の部分が増えぶんです。第 $n$ 項に届くまでに、橙は $n - 1$ 個しか積まれていません。

$n = 1$ のときは、この式が使えません。 $\sum_{k = 1}^{0}$ に意味がないためです。求めた式に $n = 1$ を入れて $a_{1}$ と一致するかを、最後に必ず確かめます。

差の和は両端だけが残る

なぜ足し上げでよいのか。差を並べて書くと分かります^[1]^[2]。

$k = 1 \sum n - 1 (a_{k + 1} - a_{k}) = a_{n} - a_{1}$

途中の項が打ち消し合い、両端だけが残ります。左辺は $\sum f (k)$ そのものなので、移項すれば公式になります。

差をとる操作と和をとる操作が、たがいに逆になっている。微分と積分の関係と同じ構図です^[1]。

例題 1：f(n) が 1 次式

$a_{1} = 1$ 、 $a_{n + 1} = a_{n} + 2 n$ を解きます。

$a_{n} = 1 + k = 1 \sum n - 1 2 k = 1 + 2 \cdot \frac{( n - 1 ) n}{2} = n^{2} - n + 1$

$n = 1$ で $1 - 1 + 1 = 1$ 。一致したので、すべての $n$ で使えます。

$n = 4$ でも確かめます。 $16 - 4 + 1 = 13$ 。漸化式で追うと $1, 3, 7, 13$ となり合いました。

例題 2：f(n) が等比数列

$a_{1} = 2$ 、 $a_{n + 1} = a_{n} + 3^{n}$ を解きます。

$a_{n} = 2 + k = 1 \sum n - 1 3^{k}$

$\sum 3^{k}$ は $k = 1$ から始まるので、初項が $3$ 、公比が $3$ 、項数が $n - 1$ の等比数列の和です。

$= 2 + \frac{3 ( 3 ^{n - 1} - 1 )}{3 - 1} = 2 + \frac{3 ^{n} - 3}{2} = \frac{3 ^{n} + 1}{2}$

$n = 1$ で $\frac{3 + 1}{2} = 2$ 。合っています。初項が $3^{0}$ ではなく $3^{1}$ である点に気をつけます。

例題 3：f(n) が 2 次式

$a_{1} = 0$ 、 $a_{n + 1} = a_{n} + n^{2}$ を解きます。

$a_{n} = 0 + k = 1 \sum n - 1 k^{2} = \frac{( n - 1 ) n ( 2 n - 1 )}{6}$

公式 $\sum_{k = 1}^{m} k^{2} = \frac{m ( m + 1 ) ( 2 m + 1 )}{6}$ に $m = n - 1$ を入れました^[3]。

$m$ を $n - 1$ に置きかえるところでミスが出ます。公式の $m$ に何を入れるかを、いったん書き出してから代入すると確実です。

例題 4：f(n) が分数

$a_{1} = 1$ 、 $a_{n + 1} = a_{n} + \frac{1}{n ( n + 1 )}$ を解きます。

分数は部分分数に分けます。

$k = 1 \sum n - 1 \frac{1}{k ( k + 1 )} = k = 1 \sum n - 1 (\frac{1}{k} - \frac{1}{k + 1}) = 1 - \frac{1}{n}$

$a_{n} = 1 + 1 - \frac{1}{n} = 2 - \frac{1}{n}$

$n = 1$ で $2 - 1 = 1$ 。合っています。 $n$ を大きくすると $2$ に近づきますが、 $2$ には届きません。

f の型と答えの型

$f (n)$ の形から、答えの形が予想できます。

例題 5：添字がずれた形

$a_{1} = 3$ 、 $a_{n} = a_{n - 1} + (2 n - 1) (n \geq 2)$ を解きます。

$a_{n + 1} = a_{n} + f (n)$ の形ではなく、 $1$ つずれています。この場合は $k$ を $2$ から $n$ まで動かします。

$a_{n} = a_{1} + k = 2 \sum n (2 k - 1)$

$\sum_{k = 1}^{n} (2 k - 1) = n^{2}$ なので、 $k = 1$ の項 $1$ を引きます。

$a_{n} = 3 + (n^{2} - 1) = n^{2} + 2$

$n = 1$ で $3$ 、 $n = 3$ で $11$ 。漸化式で追うと $3, 6, 11$ となり合いました。

添字がどこからどこまで動くのかを、毎回書き出す。ここを勘で済ませると必ずずれます。

検算の手順

答えが出たら、次の 3 つを確かめます。

n = 1

を代入して初項に一致するか。

n = 2

や

n = 3

を漸化式で直接追った値と一致するか。

a_{n + 1} - a_{n}

を計算して

f (n)

に戻るか。

3 番目がいちばん強い検算です。求めた一般項の差をとって、もとの $f (n)$ に戻れば、途中の計算はまず合っています。

例題 1 で試します。 $a_{n} = n^{2} - n + 1$ なら、

$a_{n + 1} - a_{n} = {(n + 1)^{2} - (n + 1) + 1} - (n^{2} - n + 1) = 2 n$

ちゃんと $f (n) = 2 n$ に戻りました。

練習問題

$a_{1} = 2$ 、 $a_{n + 1} = a_{n} + 4 n$ の一般項はどれですか。

$a_{n} = 2 n^{2} - 2 n$
$a_{n} = 2 n^{2} - 2 n + 2$
$a_{n} = 4 n^{2} - 4 n + 2$
$a_{n} = 2 n^{2} + 2$

__RESULT__

$2 + 4 \cdot \frac{( n - 1 ) n}{2} = 2 + 2 n^{2} - 2 n$ です。 $n = 1$ で $2$ になることも確かめられます。

階差型の公式 $a_{n} = a_{1} + \sum_{k = 1}^{n - 1} f (k)$ で、和の上端が $n - 1$ なのはなぜですか。

$f (n)$ が $n$ の関数だから
第 1 項から第 $n$ 項までに、増えぶんを $n - 1$ 回通るから
$n = 1$ のときを除くため
公式を簡単にするため

__RESULT__

$a_{1}$ から $a_{n}$ へ進むには $f (1)$ から $f (n - 1)$ までを足します。段の数は項の数より 1 つ少なくなります。

参考文献

Finite difference - Wikipedia

Oscar Levin, *Discrete Mathematics: An Open Introduction*, 2.4 Solving Recurrence Relations, University of Northern Colorado

Summation - Wikipedia

a(n+1) = a(n) + f(n) は、次へ進むときの増え方が f(n) で決まっている形です。初項から順に積み上げれば一般項に届き、通る段の数は項の数より 1 つ少ない。和の上端が n-1 になる理由をここから説明します。f が 1 次式・2 次式・等比数列・分数の場合を順に計算し、添字が 1 つずれた形の扱いと、差をとって戻す検算まで。