フィボナッチ数の性質と計算方法 (3) 定数係数 3 項間漸化式

三項間漸化式,リュカ数列,フィボナッチ数

この連載について

フィボナッチ数、リュカ数、そしてそれらを一般化した数列の基本的な性質と、コンピューターにおける計算方法について記述します。

本文

今回は、フィボナッチ数やリュカ数をさらに一般化し、任意の定数係数 3 項間漸化式により定められる数列について考えます。

漸化式と一般項

定数係数 3 項間漸化式により定められる数列の一般項を求めます。
証明の方針は前回までとほぼ同じです。ただし、 $α = β$ の場合に注意します。

数列 $a_{n}$ を漸化式
$a_{n + 2} - p a_{n + 1} + q a_{n} = 0 (n \geq 0)$
で定義する。 $p, q, a_{0}, a_{1}$ は実数とし、 $q \neq 0$ とする。

この数列の一般項は、2 次方程式 $x^{2} - p x + q = 0$ の 2 解 $α, β$ について、

$α \neq β$ の場合、
$a_{n} = \frac{α^{n} (a_{1} - β a_{0}) - β^{n} (a_{1} - α a_{0})}{α - β}$
$α = β$ (重解) の場合、
$a_{n} = n α^{n - 1} a_{1} - (n - 1) α^{n} a_{0}$

なお、ii の式は i の式に含まれる。

ある実数 $λ$ に対して、数列 $b_{n} := a_{n + 1} - λ a_{n}$ を考える。
元の漸化式において $a_{n + 2}, a_{n + 1}$ を消去して、
$b_{n + 1} - (p - λ) b_{n} + (λ^{2} - p λ + q) a_{n} = 0$

$α, β$ を 2 次方程式 $x^{2} - p x + q = 0$ の 2 解とすると、 $α + β = p, α β = q$ を満たす。
そこで $λ = α$ と選ぶと、 $b_{n + 1} = β b_{n}$ という形にできる。
このとき $b_{n}$ は等比数列であり、
$b_{n} = β^{n} b_{0} = β^{n} (a_{1} - α a_{0})$
さらに $λ = β$ と選んでも同様だから、
$\begin{array}{r} {\begin{cases} a_{n + 1} - α a_{n} = β^{n} (a_{1} - α a_{0}) \\ a_{n + 1} - β a_{n} = α^{n} (a_{1} - β a_{0}) \end{cases} \end{array}$

$α \neq β$ の場合、
上の 2 式より、
$(α - β) a_{n} = α^{n} (a_{1} - β a_{0}) - β^{n} (a_{1} - α a_{0})$
$α = β$ (重解) の場合、
$a_{n + 1} - α a_{n} = α^{n} (a_{1} - α a_{0})$
$q \neq 0$ により $α \neq 0$ だから、
$\frac{a_{n + 1}}{α^{n}} - \frac{a_{n}}{α^{n - 1}} = a_{1} - α a_{0}$
したがって $\frac{a_{n}}{α^{n - 1}}$ は等差数列であり、
$\frac{a_{n}}{α^{n - 1}} = α a_{0} + n (a_{1} - α a_{0}) = n a_{1} - (n - 1) α a_{0} a_{n} = n α^{n - 1} a_{1} - (n - 1) α^{n} a_{0}$

さらに、i の式を変形すると、
$a_{n} = \frac{α^{n} - β^{n}}{α - β} a_{1} - \frac{α^{n - 1} - β^{n - 1}}{α - β} α β a_{0}$
となり、 $\frac{α^{n} - β^{n}}{α - β} = \sum_{k = 0}^{n - 1} α^{n - 1 - k} β^{k}$ により、ii の式はこれに含まれる。

これで (必ずとは限りませんが) $α = β$ の場合を分ける必要がなくなりました。
次に、添字 $n$ を負数まで拡張します。

公式 1 は、任意の整数 $n$ に対して成り立つ。

$q a_{n} - p a_{n + 1} + a_{n + 2} = 0 (n < 0)$
とし、 $a_{- 1}, a_{- 2}, a_{- 3}, \dots$ と順に値が定まっていくと考え、 $n \geq 0$ のときと同様の解法を用いる。

2 次方程式 $q x^{2} - p x + 1 = 0$ の 2 解は $x = α^{- 1}, β^{- 1}$ だから、 $n \leq 1$ に対し、
$a_{n} = \frac{α^{- (1 - n)} (a_{0} - β^{- 1} a_{1}) - β^{- (1 - n)} (a_{0} - α^{- 1} a_{1})}{α^{- 1} - β^{- 1}} = \frac{- α^{n} (a_{1} - β a_{0}) + β^{n} (a_{1} - α a_{0})}{β - α} = \frac{α^{n} (a_{1} - β a_{0}) - β^{n} (a_{1} - α a_{0})}{α - β}$

$α, β$ が実数かつ $| α | \neq | β |$ の場合は $| α | > | β |$ となるように $α, β$ を決めることにより、
$lim_{n \to \infty} \frac{a_{n + 1}}{a_{n}} = α$
となります。
$α = β$ (重解) の場合は上記の式が成り立ちます。
$α, β$ が実数でない場合は $| α | = | β |$ であり、実際に上記の極限は振動します。

$p, q, a_{0}, a_{1}$ が整数のとき、 $a_{n}$ は整数ですが、 $α$ は無理数である可能性があります。
つまり、無理数となる $α$ に対しても、比がほぼ $α$ になる整数の組が限りなく連なっていることを意味します。

では次に、前回の定理を拡張してみましょう。
$a_{- n} = \pm q^{- n} a_{n}$ が成り立つのはどのような場合かを調べます。

任意の整数 $n$ に対して、数列 $a_{n}$ を漸化式
$a_{n + 2} - p a_{n + 1} + q a_{n} = 0$
で定義する。 $p, q, a_{0}, a_{1}$ は実数とし、 $q \neq 0$ とする。

このとき、任意の整数 $n$ に対して $a_{- n} = - q^{- n} a_{n}$ を満たすのは、 $(a_{0}, a_{1})$ が $(0, 1)$ の定数倍であるときに限られる。
また、任意の整数 $n$ に対して $a_{- n} = q^{- n} a_{n}$ を満たすのは、 $(a_{0}, a_{1})$ が $(2, p)$ の定数倍であるときに限られる。

$α + β = p, α β = q$ を用いる。

$a_{- n} = - q^{- n} a_{n}$ を式変形していくと、
$α^{- n} (a_{1} - β a_{0}) - β^{- n} (a_{1} - α a_{0}) = - q^{- n} (α^{n} (a_{1} - β a_{0}) - β^{n} (a_{1} - α a_{0})) α^{- n} (a_{1} - β a_{0}) - β^{- n} (a_{1} - α a_{0}) = - β^{- n} (a_{1} - β a_{0}) + α^{- n} (a_{1} - α a_{0}) α^{- n} (α - β) a_{0} + β^{- n} (α - β) a_{0} = 0 (α^{- n} + β^{- n}) (α - β) a_{0} = 0$
したがって $a_{0} = 0$ となり、 $(a_{0}, a_{1})$ が $(0, 1)$ の定数倍であるときに限られる。

また、 $a_{- n} = q^{- n} a_{n}$ を式変形していくと、
$α^{- n} (a_{1} - β a_{0}) - β^{- n} (a_{1} - α a_{0}) = q^{- n} (α^{n} (a_{1} - β a_{0}) - β^{n} (a_{1} - α a_{0})) α^{- n} (a_{1} - β a_{0}) - β^{- n} (a_{1} - α a_{0}) = β^{- n} (a_{1} - β a_{0}) - α^{- n} (a_{1} - α a_{0}) α^{- n} (2 a_{1} - (α + β) a_{0}) - β^{- n} (2 a_{1} - (α + β) a_{0}) = 0 (α^{- n} - β^{- n}) (2 a_{1} - p a_{0}) = 0$
したがって $p a_{0} = 2 a_{1}$ となり、 $(a_{0}, a_{1})$ が $(2, p)$ の定数倍であるときに限られる。

なお、 $α = β$ の場合も上の議論に含まれる (一般項の分子が $α - β$ で割り切れることに注意すればよい)。

実際、例えば $(p, q, a_{0}, a_{1}) = (3, 1, 2, 3)$ のときは、
$\dots, 47, 18, 7, 3, 2, 3, 7, 18, 47, \dots$
となります。
ちなみに $\frac{3 \pm \sqrt{5}}{2} = {(\frac{1 \pm \sqrt{5}}{2})}^{2}$ であることから、この数列の第 $n$ 項はリュカ数の第 $2 n$ 項に一致します。

公式 2 において、 $(a_{0}, a_{1}) = (0, 1)$ としたときの一般項は、
$a_{n} = \frac{α^{n} - β^{n}}{α - β}$
また、 $(a_{0}, a_{1}) = (2, p)$ としたときの一般項は、
$a_{n} = α^{n} + β^{n}$

公式 2 に代入すれば得られる。

$p, q$ を整数とし、 $(a_{0}, a_{1}) = (0, 1)$ とした数列 $U_{n}$ と $(a_{0}, a_{1}) = (2, p)$ とした数列 $V_{n}$ の組をリュカ数列 (Lucas sequence) と呼びます。本稿の $p, q$ の符号はこのリンク先の $P, Q$ に合わせています。

$D := p^{2} - 4 q$ とすると、 $α \neq β$ のとき、
$lim_{n \to \infty} \frac{V_{n}}{U_{n}} = α - β = \sqrt{D}$
$U_{n}, V_{n}$ は整数ですが、 $\sqrt{D}$ は無理数である可能性があります。
つまり、無理数となる $\sqrt{D}$ に対しても、比がほぼ $\sqrt{D}$ になる整数の組を規則的にいくらでも見つけられることを意味します。

各項の計算

定数係数 3 項間漸化式により定められる数列の各項をコンピューターで具体的に求める方法をいくつか挙げます。
内容はフィボナッチ数のときとほぼ同様です。
以下、 $p, q, a_{0}, a_{1}$ は整数とし、 $n \geq 0$ とします。

一般項から求める

フィボナッチ数のときは $α, β$ が無理数のため、一般項から値を計算する方法は実用的ではありませんでした。
$α, β$ が整数となる場合においては、一般項から値を計算する方法が最も効率的でしょう。

漸化式から求める

数列の各項を整数のまま計算するには、定義の漸化式を用いて順に求めるのが簡単です。
時間計算量は $O (n)$ です。
空間計算量は、途中の値をキャッシュする場合は $O (n)$ 、キャッシュしない場合は $O (1)$ でできます。

また、再帰関数として実装する方法もありますが、 $n$ が大きくなるとスタックオーバーフローの原因になるため注意が必要です。
今回は、コードは省略します。

行列の漸化式から求める

行列を利用すると、整数のままで、しかも高速に計算できます。

2 次正方行列 $A$ を用いて
$\begin{array}{r} (\begin{array}{c} a_{n + 2} \\ a_{n + 1} \end{array}) = A (\begin{array}{c} a_{n + 1} \\ a_{n} \end{array}) \end{array}$
と表すことを考えると、定義の漸化式から
$\begin{array}{r} A = (\begin{array}{cc} p & - q \\ 1 & 0 \end{array}) \end{array}$
とすればよいです。したがって、
$\begin{array}{r} (\begin{array}{c} a_{n + 1} \\ a_{n} \end{array}) = A^{n} (\begin{array}{c} a_{1} \\ a_{0} \end{array}) \end{array}$