0
大学数学基礎解説
文献あり

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

60
0
$$$$

この連載について

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

  1. フィボナッチ数
  2. リュカ数
  3. 定数係数 3 項間漸化式 (本稿)
  4. ほとんど整数 (おまけ)

本文

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

漸化式と一般項

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

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

この数列の一般項は、2 次方程式 $ x^2 - px + q = 0$ の 2 解$\alpha, \beta$について、

  1. $\alpha \neq \beta$の場合、
    $$ a_n = \frac{\alpha^n (a_1 - \beta a_0) - \beta^n (a_1 - \alpha a_0)}{\alpha - \beta} $$

  2. $\alpha = \beta$ (重解) の場合、
    $$ a_n = n \alpha^{n-1} a_1 - (n-1) \alpha^n a_0 $$

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

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

$\alpha, \beta$を 2 次方程式 $x^2 - px + q = 0$ の 2 解とすると、$\alpha + \beta = p, ~ \alpha \beta = q$ を満たす。
そこで$\lambda = \alpha$と選ぶと、$b_{n+1} = \beta \, b_n$ という形にできる。
このとき$b_n$は等比数列であり、
$$ ~~ b_n = \beta^n \, b_0 = \beta^n (a_1 - \alpha a_0)$$
さらに$\lambda = \beta$と選んでも同様だから、
$$ \begin{eqnarray} \left\{ \begin{array}{l} a_{n+1} - \alpha \, a_n = \beta^n (a_1 - \alpha a_0) \\ a_{n+1} - \beta \, a_n = \alpha^n (a_1 - \beta a_0) \end{array} \right. \end{eqnarray} $$

  1. $\alpha \neq \beta$の場合、
    上の 2 式より、
    $$ (\alpha - \beta) \, a_n = \alpha^n (a_1 - \beta a_0) - \beta^n (a_1 - \alpha a_0) $$

  2. $\alpha = \beta$ (重解) の場合、
    $$ a_{n+1} - \alpha \, a_n = \alpha^n (a_1 - \alpha a_0) $$
    $q \neq 0$により$\alpha \neq 0$だから、
    $$ \frac{a_{n+1}}{\alpha^n} - \frac{a_n}{\alpha^{n-1}} = a_1 - \alpha a_0 $$
    したがって $\dfrac{a_n}{\alpha^{n-1}}$ は等差数列であり、
    $$ \frac{a_n}{\alpha^{n-1}} = \alpha a_0 + n(a_1 - \alpha a_0) = n a_1 - (n-1) \alpha a_0 \\ a_n = n \alpha^{n-1} a_1 - (n-1) \alpha^n a_0 $$

さらに、i の式を変形すると、
$$ ~~ a_n = \frac{\alpha^n - \beta^n}{\alpha - \beta} a_1 - \frac{\alpha^{n-1} - \beta^{n-1}}{\alpha - \beta} \alpha \beta a_0 $$
となり、$\displaystyle \frac{\alpha^n - \beta^n}{\alpha - \beta} = \sum_{k=0}^{n-1} \alpha^{n-1-k} \beta^k$ により、ii の式はこれに含まれる。

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

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

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

2 次方程式 $qx^2-px+1 = 0$ の 2 解は$x=\alpha^{-1}, \beta^{-1}$だから、$n \leq 1$に対し、
$$ ~~ a_n = \dfrac{\alpha^{-(1-n)} (a_0 - \beta^{-1} a_1) - \beta^{-(1-n)} (a_0 - \alpha^{-1} a_1)}{\alpha^{-1}-\beta^{-1}} \\ ~~~~~~~ = \dfrac{-\alpha^{n} (a_1 - \beta a_0) + \beta^{n} (a_1 - \alpha a_0)}{\beta-\alpha} \\ ~~~~~~~ = \dfrac{\alpha^{n} (a_1 - \beta a_0) - \beta^{n} (a_1 - \alpha a_0)}{\alpha-\beta} $$

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

$p, q, a_0, a_1$が整数のとき、$a_n$は整数ですが、$\alpha$は無理数である可能性があります。
つまり、無理数となる$\alpha$に対しても、比がほぼ$\alpha$になる整数の組が限りなく連なっていることを意味します。

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

任意の整数$n$に対して、数列$a_n$を漸化式
$$ ~~ a_{n+2} - pa_{n+1} + qa_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)$の定数倍であるときに限られる。

$\alpha + \beta = p, ~ \alpha \beta = q$ を用いる。

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

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

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

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

公式 2 において、$(a_0, a_1)=(0, 1)$としたときの一般項は、
$$ ~~ a_n = \frac{\alpha^n - \beta^n}{\alpha - \beta} $$
また、$(a_0, a_1)=(2, p)$としたときの一般項は、
$$ ~~ a_n = \alpha^n + \beta^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-4q$とすると、$\alpha \neq \beta$のとき、
$$ ~~ \lim_{n \to \infty} \frac{V_n}{U_n} = \alpha-\beta = \sqrt{D} $$
$U_n, V_n$は整数ですが、$\sqrt{D}$は無理数である可能性があります。
つまり、無理数となる$\sqrt{D}$に対しても、比がほぼ$\sqrt{D}$になる整数の組を規則的にいくらでも見つけられることを意味します。

各項の計算

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

一般項から求める

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

漸化式から求める

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

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

行列の漸化式から求める

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

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

これで$A^n$を計算すると$a_n$を求めることができ、繰り返し二乗法により、時間計算量は $O(\log n)$ です。
値の桁が大きくなることを無視すれば (例えば、値を剰余群で考える場合)、$n$が 64 ビット整数の最大値であったとしても一瞬で計算できます。

同様に、定数係数 $k$ 項間漸化式 $(k>1)$ に拡張しても、$k-1$ 次正方行列を用いて各項を計算できます。ただし、$k$ が大きくなれば計算量も大きくなっていきます。
こちらは定数係数 4 項間漸化式の例です:

作成したサンプル コード

前回: (2) リュカ数
次回: (4) ほとんど整数 (おまけ)

参考文献

投稿日:2021619

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

Researcher and Developer for Algorithms, using C# (.NET). 数検1級金賞 (2002).

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中