フィボナッチ数の性質と計算方法 (4) ほとんど整数

リュカ数列,フィボナッチ数,ほとんど整数

141

この連載について

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

本文

今回は、おまけとしてほとんど整数 (almost integer) を扱います。
今回登場する公式は、前回までに登場した公式からすぐに導けます。
最後に、一般の定数係数 3 項間漸化式に対して、ほとんど整数が出現する条件を調べます。

フィボナッチ数

フィボナッチ数の一般項$a_n$において、$|\beta|<1$ であることから、次が成り立ちます。
ここでは、$\varphi:=\dfrac{1+\sqrt{5}}{2}$ (黄金数) とします。

フィボナッチ数の近似

十分大きな$n$に対して、
$$ ~~ a_n \approx \dfrac{\varphi^n}{\sqrt{5}} $$
より厳密には、$ \displaystyle \lim_{n \to \infty} \left| a_n - \dfrac{\varphi^n}{\sqrt{5}} \right| = 0 $ と表せる。

この式の左辺$a_n$は整数であることから、右辺のような数はほとんど整数 (almost integer) と呼ばれます。
比の極限である$\displaystyle \lim_{n \to \infty} \frac{a_{n+1}}{a_n}$とは異なることに注意します。

実際に値を計算してみると、
$$ ~~ a_{20} = 6765 ~\fallingdotseq~ \dfrac{\varphi^{20}}{\sqrt{5}} = 6765.0000295639 \cdots \\ ~~ a_{21} = 10946 ~\fallingdotseq~ \dfrac{\varphi^{21}}{\sqrt{5}} = 10945.999981728 \cdots $$
となり、$n$が大きくなるほどより整数に近くなります。

十分大きな$n$に対して、フィボナッチ数の第$n$項に近い「ほとんど整数」を、$\varphi^n$ を用いて規則的に構築できることを意味します。
フィボナッチ数の一般項が $\sqrt{5}$ を含んだ式で表されるという事実もさることながら、この結論も人間の直感に反するのではないでしょうか。

リュカ数

リュカ数の一般項$a_n$に対しても、同様に次が成り立ちます。

リュカ数の近似

十分大きな$n$に対して、
$$ ~~ a_n \approx \varphi^n $$

実際、
$$ ~~ a_{20} = 15127 ~\fallingdotseq~ \varphi^{20} = 15126.999933893 \cdots \\ ~~ a_{21} = 24476 ~\fallingdotseq~ \varphi^{21} = 24476.000040856 \cdots $$
であり、右辺はほとんど整数です。

次に、フィボナッチ数やリュカ数において初項を一般化します。

数列$a_n$を漸化式
$$ ~~ a_{n+2}-a_{n+1}-a_n=0 $$
で定義する。$a_0, a_1$は整数とする。

このとき、十分大きな$n$に対して、
$$ ~~ a_n \approx \frac{2a_1-a_0 + a_0 \sqrt{5}}{2 \sqrt{5}} \varphi^n $$

任意の整数$a_0, a_1$に対して、右辺はほとんど整数となることを意味します。
例えば$(a_0, a_1) = (7, 2)$のときは $a_n \approx \dfrac{7 \sqrt{5} - 3}{2 \sqrt{5}} \varphi^n$ であり、
$$ ~~ a_{20} = 42797 ~\fallingdotseq~ \dfrac{7 \sqrt{5} - 3}{2 \sqrt{5}} \varphi^{20} = 42796.999724279 \cdots \\ ~~ a_{21} = 69247 ~\fallingdotseq~ \dfrac{7 \sqrt{5} - 3}{2 \sqrt{5}} \varphi^{21} = 69247.000170404 \cdots $$

定数係数 3 項間漸化式

さらに、任意の定数係数 3 項間漸化式に一般化し、ほとんど整数が出現する条件を調べます。

数列$a_n$を漸化式
$$ ~~ a_{n+2} - pa_{n+1} + qa_n = 0 $$
で定義する。$p, q, a_0, a_1$は整数とし、$q \neq 0$とする。
2 次方程式 $x^2 - px + q = 0$ の 2 解$\alpha, \beta$を、$|\alpha| \geq |\beta|$となるように決める。

このとき、もし $|\beta|<1$ ならば、十分大きな$n$に対して、
$$ ~~ a_n \approx \frac{a_1 - \beta a_0}{\alpha - \beta} \alpha^n$$

公式 4 における十分条件 $|\beta|<1$ は、
$$ ~~ (1+p+q)(1-p+q) < 0 $$
と同値である。
なお、$p, q$は整数、かつ$q \neq 0$であることに注意する。

まず$q \neq 0$より、$\beta \neq 0$である。
$\alpha = \beta$ (重解) のとき、この値は整数になるため、条件を満たさない。

これを図示すると、下図のような格子点になります。
また、$q = \alpha \beta > 0$であることと$\alpha, \beta$が同符号であることは同値です。
!FORMULA[54][638421426][0] (by GeoGebra) $(1+p+q)(1-p+q) < 0$ (by GeoGebra)

$p>0, q=-1$のとき、$\alpha$は貴金属数となります。
第$n$貴金属数は$(p,q) = (n,-1)$としたとき、つまり$x^2 - nx -1 = 0$の解です。

実際、例えば$(p, q, a_0, a_1) = (2, -1, 2, 2)$のときは $a_n \approx (1+\sqrt{2})^n$ と白銀数 (silver number) が現れ、
$$ ~~ a_{10} = 6726 ~\fallingdotseq~ (1+\sqrt{2})^{10} = 6725.9998513232 \cdots \\ ~~ a_{11} = 16238 ~\fallingdotseq~ (1+\sqrt{2})^{11} = 16238.000061583 \cdots $$
となります。

また、貴金属数以外の例として、$(p, q, a_0, a_1) = (5, 2, 0, 1)$のときは $a_n \approx \dfrac{1}{\sqrt{17}} \left( \dfrac{5+ \sqrt{17}}{2} \right)^n$ であり、
$$ ~~ a_{10} = 946025 ~\fallingdotseq~ \dfrac{1}{\sqrt{17}} \left( \dfrac{5+ \sqrt{17}}{2} \right)^{10} = 946025.00006367 \cdots \\ ~~ a_{11} = 4315343 ~\fallingdotseq~ \dfrac{1}{\sqrt{17}} \left( \dfrac{5+ \sqrt{17}}{2} \right)^{11} = 4315343.0000279 \cdots $$

おわりに

フィボナッチ数周辺の特殊な現象 (整数の比が特定の無理数に近くなることや、無理数の累乗からほとんど整数が得られること) を何かに応用できないかと考え、基本的な性質を調べてみました。
添字$n$を負に拡張するところからリュカ数列にたどり着いたことや、ほとんど整数が得られる条件については当初の予定外であり、執筆を進めながら検証しました。
$k$ 項間漸化式に拡張することでまた何か発見できるのかもしれません。

前回: (3) 定数係数 3 項間漸化式