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

フィボナッチ数の性質と計算方法 (2) リュカ数

152
0
$$$$

この連載について

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

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

本文

今回は、フィボナッチ数と対で語られることの多いリュカ数 (Lucas numbers) を扱います。
さらに、初項$a_0, a_1$や添字$n$の拡張について考察します。

定義

リュカ数

漸化式
$$ ~~ a_0=2, a_1=1, \\ ~~ a_{n+2}-a_{n+1}-a_n=0 ~~ (n \geq 0) $$
で定義される数列に現れる数をリュカ数 (Lucas number) と呼ぶ。

リュカ数の定義は、フィボナッチ数の初項$a_0$のみを変更したものです。

なお、添字$n$を負数まで拡張すると、この数列は
$$ \cdots , 18, -11, 7, -4, 3, -1, 2, 1, 3, 4, 7, 11, 18, \cdots $$
となります。

また、リュカ数列が別の意味を持つ用語として定義されていることから、リュカ数 (Lucas numbers; 複数形) が上記の数列を表すようです。
cf. Lucas sequence - Wikipedia

一般項

リュカ数の一般項を求めます。
証明方法はフィボナッチ数とほぼ同じのため省略します。

リュカ数の一般項

$$ ~~ a_n = \alpha^n+\beta^n = \alpha^n+(-\alpha)^{-n} $$
ただし、$\alpha=\dfrac{1+\sqrt{5}}{2}, \beta=\dfrac{1-\sqrt{5}}{2}.$

$n$番目のフィボナッチ数およびリュカ数をそれぞれ$F_n, L_n$とすると、
$$ ~~ \lim_{n \to \infty} \frac{L_n}{F_n} = \sqrt{5} $$
となります。
比がほぼ$\sqrt{5}$になる整数の組を、規則的にいくらでも見つけられるというのは面白い現象です。

次に、初項を一般化してみます。

数列$a_n$を漸化式
$$ ~~ a_{n+2}-a_{n+1}-a_n=0 ~~ (n \geq 0) $$
で定義する。$a_0, a_1$は任意の実数とする。

この数列の一般項は、
$$ ~~ a_n = \dfrac{\alpha^n (a_1 - \beta a_0) - \beta^n (a_1 - \alpha a_0)}{\alpha-\beta} = \dfrac{\alpha^n (2a_1 - a_0 + a_0 \sqrt{5}) - \beta^n (2a_1 - a_0 - a_0 \sqrt{5})}{2 \sqrt{5}} $$
ただし、$\alpha=\dfrac{1+\sqrt{5}}{2}, \beta=\dfrac{1-\sqrt{5}}{2}.$

フィボナッチ数のときの解法と同様にして、
$$ \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} $$
となることから得られる。

次に、添字$n$を負数まで拡張します。

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

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

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

ところで、フィボナッチ数やリュカ数では、$a_{-n} = \pm a_n$が成り立っていました。
このような性質を持つ数列はどれだけあるのでしょうか。

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

このとき、任意の整数$n$に対して $a_{-n} = (-1)^{n+1} a_n$ を満たす$a_n$は、フィボナッチ数の定数倍に限られる。
また、任意の整数$n$に対して $a_{-n} = (-1)^{n} a_n$ を満たす$a_n$は、リュカ数の定数倍に限られる。

$\alpha + \beta = 1, ~ \alpha \beta = -1$ を用いる。

$a_{-n} = (-1)^{n+1} a_n$ を式変形していくと、
$$ ~~ \alpha^{-n} (a_1 - \beta a_0) - \beta^{-n} (a_1 - \alpha a_0) = (-1)^{n+1} (\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_{-n} = (-1)^{n} a_n$ を式変形していくと、
$$ ~~ \alpha^{-n} (a_1 - \beta a_0) - \beta^{-n} (a_1 - \alpha a_0) = (-1)^{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 - a_0) = 0 $$
したがって $a_0 = 2a_1$ となり、これはリュカ数の定数倍を意味する。

リュカ数の計算

リュカ数をコンピューターで具体的に求める方法をいくつか挙げます。
内容は前回の フィボナッチ数 とほぼ同様で、とくに新しい説明はありません。一般項から求める方法は省略します。
以下、$a_0, a_1$は整数とし、$n \geq 0$ とします。

漸化式から求める

リュカ数を整数のまま計算するには、定義の漸化式を用いて順に求めるのが簡単です。
時間計算量は $O(n)$ です。
空間計算量は、途中の値をキャッシュする場合は $O(n)$、キャッシュしない場合は $O(1)$ でできます。
任意の$a_0, a_1$に対しても同様です。

C# では次のようなコードでリュカ数を作れます。
なお、$a_n$の値を符号付き 64 ビット整数で表せる範囲は $n \leq 90$ しかありません。

          public static long[] CreateSeq(int nLast = 90)
    {
        var a = new long[nLast + 1];
        a[0] = 2;
        a[1] = 1;
        for (int i = 2; i <= nLast; i++)
            a[i] = a[i - 1] + a[i - 2];
        return a;
    }
    

また、再帰関数として実装する方法もありますが、$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} 1 & 1 \\ 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) = A^n \left( \begin{array}{c} 1 \\ 2 \end{array} \right) \end{eqnarray} $$

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

作成したサンプル コード

前回: (1) フィボナッチ数
次回: (3) 定数係数 3 項間漸化式

参考文献

投稿日:2021616

この記事を高評価した人

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

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

バッジはありません。

投稿者

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

コメント

他の人のコメント

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