リュカ数列

フィボナッチ数列と1/89からの続き

ときどきネット上のフリーの教科書で掘り出し物があって楽しい。昨日散歩していた犬棒は，Sheldon Axler の Linear Algebra Done Right という線形代数のpdf教科書に当たった。Springerからも紙版が出版されている。その pdf ファイルの，クリエイティブコモンズ  表示-非営利 4.0 国際ライセンスのトップページには，次の式がでかでかと護符のように貼り付けられていた。

$\displaystyle F_n = \dfrac{1}{\sqrt{5}} \Bigl\{ \Bigl( \dfrac{1+\sqrt{5}}{2} \Bigr)^n - \Bigl( \dfrac{1-\sqrt{5}}{2} \Bigr)^n \Bigr\}$

この式がフィボナッチ数列を表しているというのを知ったのは，ずいぶん遅くて大学4年生のころだ。自宅で塾を開いて，中学生や高校生に数学を教えていたきのこと。大学進学のためのマイナーで難しそうな問題集を解かせていた北野高校の生徒が，フィボナッチ数列の問題を上記の式を使って一発で解いてきた。田舎の高校生時代に，近所に住んでいた数学乙の西野先生にしこまれた数列の漸化式の標準解法しか知らなかった物理学科の学生は見たこともない式にどぎまぎしてしまったのだった。確かに答えはあっていた。

その思い出の式を眺めていたら，$\sqrt{5}$の中を変えたらどうなるのかが初めて気になってきた。早速試してみよう。ということで，Mathematicaで答えを当たってみると，ルートの中身が4の倍数+1の場合に整数の数列が得られることがわかった。

そこで，軟弱なGさんは，久々にOpenAI o1-previewを取り出してその理由を聞いてみた。

Ｑ（koshix）：

数列 a_n = f[n_, m_] :=  1/Sqrt[m] (((1 + Sqrt[m])/2)^n - ((1 - Sqrt[m])/2)^n) // Expand がすべて整数の項からなる数列になるのは，n がどのような値をとる場合かを説明してください。

Ａ（o1-preview）：

（日本語による不十分で誤った説明→略）

Answer: Because all terms a_n  are integers if and only if n is the square of an odd integer—that is, when m =k^2 with odd k.

Ｑ（koshix）：

あなたのおっしゃる条件からはずれる場合，例えばn=5を確かめてみてください。この場合も全て整数の項からなる数列になりますよね。

Ａ（o1-preview）：

（日本語によるやや不十分でも正しい結果→略）

Answer: Because all terms a_n are integers if and only if n leaves a remainder of 1 when divided by 4 —that is, when m≡1 mod 4.

すっきりしないので，しぶしぶ人間の脳で考えることにしてみた。

$\alpha_m = \dfrac{1+\sqrt{m}}{2}, \ \beta_m = \dfrac{1-\sqrt{m}}{2}$と置いて，$\displaystyle F(m)_{n}=\dfrac{1}{\sqrt{m}}\Bigl( {\alpha_m}^n - {\beta_m}^n \Bigr)$である。

そこで，$F(m)_{0} = 0, \quad F(m)_{1} = \dfrac{1}{\sqrt{m}}\Bigl( {\alpha_m} - {\beta_m} \Bigr) = 1$

さて，${\alpha_m}^n - {\beta_m}^n = (\alpha_m + \beta_m) \Bigl( {\alpha_m}^{n-1} - {\beta_m}^{n-1} \Bigr)  - \alpha_m \cdot \beta_m \Bigl({\alpha_m}^{n-2} - {\beta_m}^{n-2} \Bigr)$ 

いいかえれば，$F(m)_n = F(m)_{n-1} - \dfrac{1-m}{4} F(m)_{n-2} $

したがって，$m=4k+1$であれば，$F(m)_n = F(m)_{n-1} + k F(m)_{n-2} $が成り立つので，初期値からすべての$F(m)_n$は整数となる。

これはどうやら，リュカ数列という，整係数の２次方程式の２つの解から定義される漸化式による二階線形回帰数列の一種だということだ。フィボナッチ数，リュカ数，ペル数，フェルマー数，メルセンヌ数など数論に現れる重要な数列がこれに属するとWikipediaには書いてあった。