フィボナッチ数の性質と計算方法 (2) リュカ数
この連載について
フィボナッチ数、リュカ数、そしてそれらを一般化した数列の基本的な性質と、コンピューターにおける計算方法について記述します。
本文
今回は、フィボナッチ数と対で語られることの多いリュカ数 (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 項間漸化式