22.3 線形再帰方程式

目次

ここまでに紹介した再帰方程式を解く手法は推測検証と定義代入の二つである。これらの手法には、実数の列または式を見てパターンを見つけるステップが存在する。本節と次節では、それぞれ特定の大きなクラスに属する再帰方程式を解く機械的な手法を示す。これらの手法は洞察を一切必要とせず、レシピに従えば必ず解が求まる。

22.3.1 階段を上る方法の個数

階段を \(1\) 歩ごとに \(1\) 段または \(2\) 段だけ進めるとき、\(n\) 段の階段を上る方法は何通りあるだろうか？ 例えば、\(4\) 段の階段を上る方法は \(5\) 通りある:

この問題を使って、特定の種類の再帰方程式を機械的に解く一つ目の手法の使い方を説明する。その後に詳細を詰めて一般的な形式を示す。

再帰方程式を見つける

特殊ケースとして、\(0\) 段の階段を上る方法は \(1\) 通り、\(1\) 段の階段を上る方法は \(1\) 通りある。それ以外のケースでは、\(n\) 段の階段の任意の上り方は最初の \(1\) 歩で \(1\) 段上ってから残りの \(n - 1\) 段を上るか、最初の \(1\) 歩で \(2\) 段上ってから残りの \(n - 2\) 段を上るかのいずれかである。つまり \(n\) 段を上る方法の個数は、\(n - 1\) 段を上る方法の個数と \(n - 2\) 段を上る方法の個数の和に等しい。以上の観察から次の再帰方程式が分かる:

\[ \begin{aligned} f(0) &= 1 \\ f(1) &= 1 \\ f(n) &= f(n - 1) + f(n - 2) \qquad (n \geq 2) \end{aligned} \]

\(f(n)\) は \(n\) 段の階段を上る方法の個数を表す。ここでは添え字を使った \(T_{n}\) や \(f_{n}\) といった記法ではなく関数風の記法を使っている。これは見た目を変えているだけで現時点では大きな意味を持たないものの、関数のように表記しておくと以降の議論が滑らかになる。

上記の再帰方程式は Fibonacciフィボナッチ 数 (Fibonacci number) を表す有名な再帰方程式である。Fibonacci 数は様々な場面で姿を現す。例えば:

再帰方程式を解く

上記の再帰方程式は線形再帰方程式 (linear recurrence) と呼ばれるクラスに属する。一時間もあれば、このクラスに属する事実上全ての再帰方程式を解く手法をマスターできる。Fibonacci の再帰方程式がほぼ六世紀にわたって未解決だったことを考えると、これはなかなか驚異的なことだ！

一般に、斉次線形再帰方程式 (homogeneous linear recurrence) は次の形をしている:

\[ f(n) = a_{1} f(n - 1) + a_{2} f(n - 2) + \cdots + a_{d} f (n - d) \]

ここで \(a_{1}\), \(\ldots\), \(a_{d}\), \(d\) は定数を表す。\(d\) を線形再帰方程式の次数 (order) と呼ぶ。典型的に、関数 \(f\) の値はいくつかの点で固定される: それらの条件を境界条件 (boundary condition) と呼ぶ。例えば Fibonacci の再帰方程式では \(d = 2\) および \(a_{1} = a_{2} = 1\) であり、境界条件 \(f(0) = 1\) と \(f(1) = 1\) が存在する。「斉次 (homogenous)」という単語を恐ろしく感じたかもしたないが、ここでは単に「簡単な種類の」を意味すると考えて問題ない。さらに複雑な斉次でない線形再帰方程式は本節の最後にまた議論する。

数世紀分の数学の知識を利用して Fibonacci の再帰方程式を解いてみよう。一般に、線形再帰方程式の解は指数関数的な形をしていることが多い。そこで次のように推測してみる:

\[ f(n) = x^{n} \]

ここで \(x\) は詳細を後回しにするために導入されたパラメータであり、その値はこれから決定される。再帰方程式 \(f(n) = f(n - 1) + f(n - 2)\) からは次の等式が分かる:

\[ x^{n} = x^{n-1} + x^{n-2} \]

両辺を \(x^{n-2}\) で割れば次の二次方程式を得る:

\[ x^{2} = x + 1 \]

この二次方程式を解くと、\(x\) として可能な値が二つ存在することが分かる:

\[ x = \frac{1 \pm \sqrt{5}}{2} \]

これは、境界条件を無視するとき再帰方程式の解が少なくとも二つ存在することを意味する。つまり次の二つの関数はどちらも \(f(n) = f(n - 1) + f(n - 2)\) を満たす:

\[ f(n) = \left( \frac{1 + \sqrt{5}}{2} \right)^{\! n}, \quad f(n) = \left( \frac{1 - \sqrt{5}}{2} \right)^{\! n} \]

斉次線形再帰方程式が持つ次の素晴らしい性質からは、任意の解の線形結合も解だと分かる:

定理 22.3.1

\(f(n)\) と \(g(n)\) が斉次線形再帰方程式 \(R\) の解なら、任意の実数 \(s, t \in \mathbb{R}\) に対して \(h(n) = s f(n) + t g(n)\) も \(R\) の解である。

証明

\[ \begin{aligned} h (n) &= s f(n) + t g(n) \\ &= s (a_{1} f(n-1) + \cdots + a_{d} f(n - d)) + t (a_{1} g(n-1) + \cdots + a_{d} g(n - d)) \\ &= a_{1} (s f(n-1) + tg(n-1)) + \cdots + a_{d}(s f(n-d) + tg(n - d)) \\ &= a_{1} h(n - 1) + \cdots + a_{d} h (n - d) \end{aligned} \]

最初の等号は関数 \(h\) の定義から、次の式変形は \(f\) と \(g\) が \(R\) の解である事実から分かる。その次の二つの式変形では式を整理してからもう一度 \(h\) の定義を使っている。最初の式は最後の式と等しいので、\(h\) は \(R\) の解である。 ■

この定理が示す事実「解の線形結合は解」は多くの微分方程式や物理系でも成り立つ。線形再帰方程式と線形微分方程式は非常によく似ているので、読者がこれから受講する数学の講義で線形微分方程式の話題になったときは居眠りをしても問題ないだろう。

Fibonacci 再帰方程式に戻ろう。定理 22.3.1 からは、任意の実数 \(s\), \(t\) に対して

\[ f(n) = s \left( \frac{1 + \sqrt{5}}{2} \right)^{\! n} + t \left( \frac{1 - \sqrt{5}}{2} \right)^{\! n} \]

が \(f(n) = f(n - 1) + f(n - 2)\) を満たすと分かる。二つしかなかった解が非加算無限個に増加した！ 続いて、境界条件 \(f(0) = 1\) と \(f(1) = 1\) が満たされる解をこの中から見つけよう。それぞれの境界条件はパラメータ \(s\), \(t\) を制約する。例えば \(f(0) = 1\) からは次の制約が分かる:

\[ f(0) = s \left( \frac{1 + \sqrt{5}}{2} \right)^{\! 0} + t \left( \frac{1 - \sqrt{5}}{2} \right)^{\! 0} = s + t = 1 \]

そして \(f(1) = 1\) は次の制約を意味する:

\[ f(1) = s \left( \frac{1 + \sqrt{5}}{2} \right)^{\! 1} + t \left( \frac{1 - \sqrt{5}}{2} \right)^{\! 1} = 1 \]

これで \(2\) 個の変数が満たす線形方程式が \(2\) 個手に入った。この連立方程式は退化しておらず、次に示す一意な解を持つ:

\[ s = \frac{1}{\sqrt{5}} \cdot \frac{1 + \sqrt{5}}{2}, \quad t = -\frac{1}{\sqrt{5}} \cdot \frac{1 - \sqrt{5}}{2} \]

\(s\), \(t\) がこれらの値のとき、\(f(n)\) は境界条件を含めた Fibonacci 再帰方程式を満たす。つまり、\(n\) 番目の Fibonacci 数 \(f(n)\) は次の式で計算できる:

\[ \begin{aligned} f(n) &= \frac{1}{\sqrt{5}} \frac{1 + \sqrt{5}}{2} \left( \frac{1 + \sqrt{5}}{2} \right)^{\!\! n} - \frac{1}{\sqrt{5}} \frac{1 - \sqrt{5}}{2} \left( \frac{1 - \sqrt{5}}{2} \right)^{\!\! n} \\ &= \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^{\!\! n+1} - \frac{1}{\sqrt{5}} \left( \frac{1 - \sqrt{5}}{2} \right)^{\!\! n+1} \\ \end{aligned} \]

六世紀にわたって誰もこの解を見つけられなかった事実は容易に納得できる: 全ての Fibonacci 数は整数であるにもかかわらず、その一般項を表す式には \(5\) の平方根が山ほど含まれる！ 驚くべきことに、これらの平方根は常に全て打ち消される。\(n = 0, 1, 2\) などを代入してみれば、この式が本当に Fibonacci 数を与えることを確認できる。

Fibonacci 数を表す上記の閉形式の式は Binetビネ の公式 (Binet's formula) と呼ばれ、いくつかの系を持つ。例えば、一つ目の項が持つ指数の底 \((1 + \sqrt{5})/2 = 1.618\ldots\) は \(1\) より大きいので、\(n\) が無限大に向かうとき無限に大きくなる。一方、二つ目の項が持つ指数の底 \((1 - \sqrt{5})/2 = -0.618\ldots\) は絶対値が \(1\) より小さいので、\(n\) が無限大に向かうとき \(0\) に向かう。よって、\(f(n)\) は次の関係を満たすと分かる:

\[ f(n) = \frac{\varphi^{n+1}}{\sqrt{5}} + o(1) \]

ここで \(\varphi\) は黄金比 \((1 + \sqrt{5})/2\) である。この関係によると、\(n\) が大きいとき無理数の整数乗が絡む式 \(\varphi^{n+1} / \sqrt{5}\) は非常に整数に近くなる！ 例えば次の等式が成り立つ:

\[ \frac{\varphi^{20}}{\sqrt{5}} = 6765.00029 \approx f(19) \]

また、連続する Fibonacci 数の比が黄金比に急速に近づくことも分かる。例えば:

\[ \frac{f(20)}{f(19)} = \frac{10946}{6765} = 1.6180339985\ldots \approx 1.6180339887\ldots = \varphi \]

22.3.2 斉次線形再帰方程式の解法

Fibonacci の再帰方程式を解くのに使った手法は任意の斉次線形再帰方程式を解くのに利用できる。つまり、定数 \(a_{1}\), \(\ldots\), \(a_{n}\), \(d\) を使って

\[ f(n) = a_{1} f(n - 1) + a_{2} f(n - 2) + \cdots + a_{d} f (n - d) \]

と書ける再帰方程式は次の手順で解ける。まず、解を \(f(n) = x^{n}\) と推測する。このとき以前と同じように、再帰方程式から次の等式が分かる:

\[ x^{n} = a_{1} x^{n - 1} + a_{2} x^{n - 2} + \cdots + a_{d} x^{n - d} \]

両辺を \(x^{n-d}\) で割れば次の方程式を得る:

\[ x^{d} = a_{1} x^{d-1} + a_{2} x^{d-2} + \cdots + a_{d-1} x + a_{d} \]

これを再帰方程式の特性方程式 (characteristic equation) と呼ぶ。特性方程式は元の再帰方程式と同じ係数を持つので、簡単に得られる。

斉次線形再帰方程式の解は、その特性方程式の根を使って記述できる。つまり、境界条件を無視するとき次のことが言える:

そして定理 22.3.1 から、これらの解の任意の線形結合も解だと分かる。

例えば、特性多項式が重根でない根 \(s\), \(t\) と重複度 \(2\) の重根 \(u\) を持つとする。このとき次の \(4\) 個の異なる解が存在すると分かる:

\[ f(n) = s^{n}, \qquad f(n) = t^{n}, \qquad f(n) = u^{n}, \qquad f(n) = nu^{n} \]

そして、これらの線形結合も解である:

\[ f(n) = a \cdot s^{n} + b \cdot t^{n} + c \cdot u^{n} + d \cdot nu^{n} \tag{22.1}\]

後は境界条件を使って定数の値を求めればよい。それぞれの境界条件が定数間の制約を一つ定めるので、全ての境界条件からは線形方程式系が得られる。例えば先ほどの例で境界条件が \(f(0) = 0\), \(f(1) = 1\), \(f(2) = 4\), \(f(3) = 9\) なら、\(4\) 個の変数が含まれる \(4\) 個の線形方程式が成り立つと分かる:

\[ \begin{aligned} f(0) &= 0 \ \ \longrightarrow \ \ a \cdot s^{0} + b \cdot t^{0} + c \cdot u^{0} + d \cdot nu^{0} = 0 \\ f(1) &= 1 \ \ \longrightarrow \ \ a \cdot s^{1} + b \cdot t^{1} + c \cdot u^{1} + d \cdot nu^{1} = 1 \\ f(2) &= 4 \ \ \longrightarrow \ \ a \cdot s^{2} + b \cdot t^{2} + c \cdot u^{2} + d \cdot nu^{2} = 4 \\ f(3) &= 9 \ \ \longrightarrow \ \ a \cdot s^{3} + b \cdot t^{3} + c \cdot u^{3} + d \cdot nu^{3} = 9 \end{aligned} \]

物騒な見た目をしているものの、\(s\), \(t\), \(u\) は単なる定数なので、解くのは面倒なだけで難しくはない。この線形方程式系を解いて \(a\), \(b\), \(c\), \(d\) が求まれば、境界条件を満たす再帰方程式の解が判明する。

22.3.3 一般的な線形方程式の解法

これで全ての斉次線形再帰方程式が解けるようになった。このクラスに属する再帰方程式は次の形をしている:

\[ f(n) = a_{1} f(n - 1) + a_{2} f(n - 2) + \cdots + a_{d} f (n - d) \]

しかし、現実の問題で目にする再帰方程式の多くはこの形をしていない。例えば、前節では Hanoi の塔問題を考えたときに次の再帰方程式が登場した:

\[ \begin{aligned} f(1) &= 1 \\ f(n) &= 2 f(n - 1) + 1 \qquad (n \geq 2) \end{aligned} \]

問題は最後にある \(+ 1\) である。これがあるために、この線形再帰方程式は斉次でなくなっている。一般に、\(f(\cdots)\) の定数倍でない項を持つ線形再帰方程式を非斉次線形再帰方程式 (inhomogeneous linear recurrence) と呼ぶ。つまり、非斉次線形再帰方程式は定数 \(a_{1}\), \(\ldots\), \(a_{d}\), \(d\) と関数 \(g(n)\) を使って次のように書ける:

\[ f(n) = a_{1} f(n - 1) + a_{2} f(n - 2) + \cdots + a_{d} f (n - d) + g(n) \]

この形をした再帰方程式の解法は先ほど見たものと大きく異なるわけではなく、非常に難しいわけでもない。非斉次線形再帰方程式の解法は次の五つのステップからなる:

  1. \(g(n)\) を \(0\) に置き換えて得られる斉次線形再帰方程式の特性方程式の根を求める。

  2. 求めた根を使って斉次線形再帰方程式の解を書く。境界条件を使って係数を決定する必要はない。この解を斉次解 (homogeneous solution) と呼ぶ。

  3. 続いて、\(g(n)\) を除去しない非斉次線形再帰方程式の解を一つ見つける。境界条件は無視してよい。この解を特殊解 (particular solution) と呼ぶ。特殊解を見つける方法については後述する。

  4. 斉次解と特殊解を足して一般解 (general solution) を得る。

  5. 以前と同様に、境界条件を使って一般解から線形方程式系を作成し、それを解くことで定数の値を決定する。

例として、Hanoi の塔問題を次のように改変した問題を考えよう。円盤の移動には円盤の大きさに応じた時間がかかるとする。具体的には、初期状態で最も上にある最も小さな円盤の移動には \(1\) の時間がかかり、次に大きい円盤の移動には \(2\) の時間がかかり、以下同様と定める。例えば最も下にある \(n\) 番目に小さい (最も大きい) 円盤の移動には \(n\) の時間がかかる。このように問題を改変すると、\(n\) 個の円盤全てを移動させるのにかかる時間 \(f(n)\) が満たす再帰方程式は最後の \(+1\) が \(+n\) に置き換わる:

\[ \begin{aligned} f(1) &= 1 \\ f(n) &= 2 f(n - 1) + n \qquad (n \geq 2) \end{aligned} \]

明らかに、このとき \(f(n)\) は元の問題より大きくなる。どれくらい大きくなるだろうか？ 上述の方法で再帰方程式を解いて確認してみよう。

ステップ 1 とステップ 2 では、\(+n\) の部分を無視した斉次再帰方程式 \(f(n) = 2 f(n-1)\) を解く必要がある。対応する特性方程式は \(x = 2\) なので、斉次解は \(f(n) = c 2^{n}\) だと分かる。

ステップ 3 では、完全な再帰方程式 \(f(n) = 2 f(n - 1) + n\) の (境界条件を無視したときの) 解を一つ見つける必要がある。定数 \(a\), \(b\) を使って \(f(n) = an + b\) と書ける解が存在すると仮定してみよう。この推測した解を再帰方程式に代入すると次の等式が分かる:

\[ \begin{aligned} an + b &= 2 (a (n - 1) + b) + n \\ 0 &= (a + 1)n + (b - 2a) \end{aligned} \]

二行目の等式は一行目の等式を整理すると得られる。二行目の等式は \(a + 1 = 0\) かつ \(b - 2a = 0\) なら全ての \(n\) に対して成り立つ。つまり \(a = -1\) かつ \(b = -2\) とした \(f(n) = an + b = -n - 2\) は特殊解である。

ステップ 4 では、斉次解と特殊解を足して一般解を得る。次の関数が一般解である:

\[ f(n) = c 2^{n} - n - 2 \]

最後のステップ 5 では、境界条件 \(f(1) = 1\) を使って定数 \(c\) を決定する:

\[ \begin{aligned} f(1) = 1 &\ \ \longleftrightarrow \ \ c 2^{1} - 1 - 2 = 1 \\ &\ \ \longleftrightarrow \ \ c = 2 \end{aligned} \]

従って、この改変した Hanoi の塔問題の解は \(f(n) = 2 \cdot 2^{n} - n - 2\) である。通常の Hanoi の塔問題の解は \(2^{n} - 1\) なので、円盤の移動にかかる時間が円盤の大きさに比例するとき僧侶がパズルを解く時間は約二倍に増加する。

22.3.4 特殊解を推測する方法

非斉次線形再帰方程式を解くとき最も手間取る可能性が高いのは特殊解を見つけるステップである。このステップでは推測が必要で、推測が間違う可能性もある1。ただ、次の経験則を頭に入れておけば、多くの場合ですぐに特殊解が見つかるだろう:

線形再帰方程式を解くための完全なプロセスを次にまとめる。

線形再帰方程式の簡単求解ガイド

線形再帰方程式 (linear recurrence) は方程式

\[ f(n) = a_{1} f(n - 1) + a_{2} f(n - 2) + \cdots + a_{d} f(n - d) + \underbrace{g(n)}_{\text{非斉次項}} \]

と、\(f(0) = b_{0}\), \(f(1) = b_{1}\) といった境界条件からなる。線形再帰方程式は次の手順に従うと解ける:

  1. 特性方程式

    \[ x^{n} = a_{1} x^{n-1} + a_{2} x^{n-2} + \cdots + a_{d-1} x + a_{d} \]

    の根を見つける。

  2. 斉次解を書く。特性多項式のそれぞれの根に対応する項の和が斉次解となる。重根でない根 \(r\) には項 \(cr^{n}\) が対応する。\(c\) は定数であり、その値はステップ 5 で決定される。重複度 \(k\) の重根 \(r\) には次の \(k\) 個の項が対応する:

    \[ d_{1} r^{n}, \qquad d_{2} n r^{n}, \qquad d_{3} n^{2} r^{n}, \qquad \ldots, \qquad d_{k} n^{k-1} r^{n} \]

    ここでも \(d_{1}\), \(\ldots\), \(d_{k}\) は定数であり、その値はステップ 5 で決定される。

  3. 特殊解を見つける。特殊解とは、非斉次項 \(g(n)\) を含んだ完全な再帰方程式に対する、境界条件を無視したときの解を意味する。このステップでは「推測検証」を使う。もし \(g(n)\) が定数あるいは多項式なら、まず同じ次数の多項式を試し、失敗したら次数を大きくしたものを順に試していく。例えば \(g(n) = n\) なら、最初に \(f(n) = bn + c\) を試し、次に \(f(n) = an^{2} + bn + c\) を試す。\(g(n)\) が \(3^{n}\) などの指数関数なら、最初に \(f(n) = c3^{n}\) を試す。その後は \(f(n) = (bn + c)3^{n}\), \(f(n) = (an^{2} + bn + c)3^{n}\), \(\ldots\) と試していく。

  4. 一般解を書く。一般解は斉次解と特殊解の和であり、典型的には次のような形をしている:

    \[ f(n) = \underbrace{c 2^{n} + d (-1)^{n}}_{\text{斉次解}} + \underbrace{3n + 1}_{\text{特殊解}} \]

  5. 一般解に境界条件を代入する。境界条件ごとに未知の定数に関する線形方程式が得られる。例えば、上記の一般解が境界条件 \(f(1) = 2\) を満たすなら、次の線形方程式が分かる:

    \[ \begin{aligned} 2 &= c \cdot 2^{1} + d \cdot (-1)^{1} + 3 \cdot 1 + 1 \\ \ \ \longleftrightarrow \ \ -2 &= 2c - d \end{aligned} \]

    全ての境界条件から得られた線形方程式系を解くと、ステップ 2 で導入された定数の値が決定する。

  1. 第 16 章では線形再帰方程式を母関数を使って解く方法を説明した ── 複雑ではあるものの、推測は必要ない。 ↩︎

広告