漸化式 aₙ₊₁ = paₙ + rⁿ 型〜両辺を rⁿ で割って解く

$a_{n + 1} = 3 a_{n} + 2^{n}$ のように、付け足される部分が定数ではなく指数の形になっている漸化式があります。

定数のときは、動かない値を引けば等比数列になりました。ところが $2^{n}$ は $n$ とともに動くので、同じ手が使えません^[1]。

$x = 3 x + 2^{n}$

この式は $n$ ごとに答えが変わってしまい、特性方程式として役に立たない。動く相手には、別の道具が要ります。

動く相手で割る

$2^{n}$ が邪魔なら、 $2^{n}$ で割ってしまう。これが基本の発想です。

両辺を $2^{n + 1}$ で割ります。左辺の番号に合わせて、指数も $n + 1$ にそろえるところがこつです。

$\frac{a _{n + 1}}{2 ^{n + 1}} = \frac{3}{2} \cdot \frac{a _{n}}{2 ^{n}} + \frac{1}{2}$

$b_{n} = \frac{a _{n}}{2 ^{n}}$ と置けば、右辺の第 2 項が定数になりました。

$b_{n + 1} = \frac{3}{2} b_{n} + \frac{1}{2}$

見慣れた形です。あとは特性方程式で不動点を求め、等比数列に直すだけ^[2]。

割ったあとの数列を見る

$a_{1} = 1$ のときの値を並べます。もとの数列は $1, 5, 19, 65, 211$ と急に伸びますが、割った先には規則が見えます。

いちばん下の行が公比 $\frac{3}{2}$ の等比数列です。ここまで来れば、あとは戻すだけになります。

例題 1：3 倍して 2 のべき乗を足す

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

両辺を $2^{n + 1}$ で割り、 $b_{n} = \frac{a _{n}}{2 ^{n}}$ と置くと $b_{n + 1} = \frac{3}{2} b_{n} + \frac{1}{2}$ です。

特性方程式 $x = \frac{3}{2} x + \frac{1}{2}$ を解くと $x = - 1$ 。

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

$b_{1} = \frac{1}{2}$ なので $b_{1} + 1 = \frac{3}{2}$ です。

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

$b_{n} = (\frac{3}{2})^{n} - 1$ を $a_{n} = 2^{n} b_{n}$ に戻します。

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

$n = 2$ で確かめます。漸化式では $3 \cdot 1 + 2 = 5$ 、公式では $9 - 4 = 5$ 。合いました。

例題 2：係数を入れかえる

$a_{1} = 1$ 、 $a_{n + 1} = 2 a_{n} + 3^{n}$ を解きます。今度は $3^{n + 1}$ で割ります。

$b_{n + 1} = \frac{2}{3} b_{n} + \frac{1}{3}, b_{n} = \frac{a _{n}}{3 ^{n}}$

特性方程式 $x = \frac{2}{3} x + \frac{1}{3}$ から $x = 1$ 。 $b_{1} = \frac{1}{3}$ です。

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

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

例題 1 と同じ答えが出ました。偶然ではありません。

$a_{n} = 3^{n} - 2^{n}$ は、 $3$ 倍して $2^{n}$ を足しても、 $2$ 倍して $3^{n}$ を足しても、次の項 $3^{n + 1} - 2^{n + 1}$ になります。実際に計算すると確かめられます。

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

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

$2$ と $3$ という 2 つの数が対等に効いているためです。どちらを係数にしても同じ数列が出てきます。

p と r が等しいとき

$a_{n + 1} = p a_{n} + p^{n}$ の形では、事情が変わります。両辺を $p^{n + 1}$ で割ります。

$\frac{a _{n + 1}}{p ^{n + 1}} = \frac{a _{n}}{p ^{n}} + \frac{1}{p}$

$b_{n + 1} = b_{n} + \frac{1}{p}$ となり、公差 $\frac{1}{p}$ の等差数列です。特性方程式は要りません。

例題 3：p と r が等しい場合

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

両辺を $2^{n + 1}$ で割ると $b_{n + 1} = b_{n} + \frac{1}{2}$ です。 $b_{1} = \frac{1}{2}$ なので、

$b_{n} = \frac{1}{2} + (n - 1) \cdot \frac{1}{2} = \frac{n}{2}$

$a_{n} = 2^{n} \cdot \frac{n}{2} = n \cdot 2^{n - 1}$

$n = 3$ で確かめます。漸化式では $a_{2} = 4$ 、 $a_{3} = 2 \cdot 4 + 4 = 12$ 。公式では $3 \cdot 4 = 12$ 。合いました。

$n$ が前に出る形になりました。指数関数と $n$ の積という、等比数列だけでは出てこない形です。

別解：p のべき乗で割る

$r^{n + 1}$ ではなく $p^{n + 1}$ で割る手もあります。例題 1 を $3^{n + 1}$ で割ってみます。

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

$c_{n} = \frac{a _{n}}{3 ^{n}}$ と置くと、右辺に $c_{n}$ しか残りません。差が分かっている形なので、足し上げれば求まります。

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

等比数列の和を計算して $3^{n}$ を掛け直せば、同じ答えにたどりつきます。

どちらで割っても結果は同じです。 $r^{n + 1}$ で割ると 1 次の漸化式、 $p^{n + 1}$ で割ると足し上げの形。慣れているほうを選べば足ります^[3]。

例題 4：定数も付いている場合

$a_{1} = 1$ 、 $a_{n + 1} = 2 a_{n} + 3^{n} + 1$ を解きます。指数の項と定数が両方あります。

答えの形を先に予想します。 $3^{n}$ に対応する部分、定数に対応する部分、そして $2^{n}$ の部分が出るはずです。

$a_{n} = A \cdot 3^{n} + B + C \cdot 2^{n}$

漸化式に入れて係数をくらべます。 $3^{n}$ の部分は $3 A = 2 A + 1$ から $A = 1$ 、定数の部分は $B = 2 B + 1$ から $B = - 1$ 。

$a_{1} = 1$ から $3 - 1 + 2 C = 1$ 、すなわち $C = - \frac{1}{2}$ です。

$a_{n} = 3^{n} - 1 - 2^{n - 1}$

$n = 3$ で確かめます。漸化式では $a_{2} = 6$ 、 $a_{3} = 2 \cdot 6 + 9 + 1 = 22$ 。公式では $27 - 1 - 4 = 22$ 。合いました。

足されている部分を型ごとに分けて、それぞれに対応する形を用意する。付け足しが増えても、やることは変わりません。

練習問題

$a_{n + 1} = 5 a_{n} + 4^{n}$ を解くとき、両辺を何で割りますか。

$4^{n}$
$4^{n + 1}$
$5^{n}$
$n$

__RESULT__

左辺が $a_{n + 1}$ なので、指数も $n + 1$ にそろえます。 $4^{n + 1}$ で割ると $b_{n + 1} = \frac{5}{4} b_{n} + \frac{1}{4}$ になります。

$a_{n + 1} = 3 a_{n} + 3^{n}$ を $3^{n + 1}$ で割ると、どんな数列になりますか。

等比数列
公差 $\frac{1}{3}$ の等差数列
定数の数列
三項間漸化式

__RESULT__

$p$ と $r$ が等しいので $b_{n + 1} = b_{n} + \frac{1}{3}$ になります。特性方程式を使わずに、そのまま足し上げれば解けます。

参考文献

Recurrence relation - Wikipedia

Suite arithmético-géométrique - Wikipédia（フランス語）

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

a(n+1) = 3a(n) + 2 の n 乗のように、付け足される部分が n とともに動く漸化式では、不動点を引く手が使えません。邪魔な指数で両辺を割ってしまえば、見慣れた 1 次の漸化式に戻ります。割ったあとの数列が等比になる様子を数値で追い、係数を入れかえても同じ一般項が出る理由、p と r が等しいときに等差数列になる場合、定数も付いた形まで扱います。