P, Q, D となる整数とし、 を2次方程式 の解とする(D ≠ 0 より この2次方程式は2つの相異なる解をもつ)。 このとき

が成り立つ。 線形回帰数列 で述べたように、数列 について、 漸化式

を満足することと、一般項が

の形に表されることは同値である。

特に、線形回帰数列でも例にあげたフィボナッチ数のように、

により定まる数列 はいずれも上記の漸化式を満足し、初項は

により与えられる。逆に、これらの初項と漸化式で与えられる数列の一般項は (*) であらわされる。

このようにして定まる数列 に関するルーカス数列と呼ぶ。 また、数列 のみを単にルーカス数列といい、同伴ルーカス数列と呼ぶこともある。


フィボナッチ数列   は (1, -1) に関するルーカス数列である。また、この同伴数列は   により定まり、 2, 1, 3, 4, 7, 11, 18, 29, 47, ... で始まる。 そして、これらの数列の一般項は

 

により与えられる。  の要素をフィボナッチ数と呼ぶのに対し、 の要素をルーカス数という。

(2, -1) に関するルーカス数列は 0, 1, 2, 5, 12, 29, 70, ... および 2, 2, 6, 14, 34, 82, 198, ... で始まる。一般項は

 

により与えられる。これらの数列はペル数列と呼ばれる(後に議論するが、ペル方程式と呼ばれる不定方程式の解としてあらわれる)。

基本的な関係式

編集

ルーカス数列には重要な関係式が多数存在するが、証明まで記載すると長大になるので、証明は別に記す

まず、次の関係式が成立する。

関係式 1

 

特に、  のとき、   はペル方程式の解となっていることがわかる。例えばペル数列に対し、  とおくとペル方程式   の解が得られる。

次に、添字の加法に関して、次のような、三角関数の加法定理に類似した関係式が成り立つ。

関係式 2

 

関係式 3

 

次のような関係式も成り立つ。

関係式 4

 

関係式 2, 3 の特殊な場合として、添字を2倍, 3倍したとき、次のような関係が成り立つ。

関係式 5

 

関係式 6

 


より一般的な、添字の乗法について考えたい。そのために、まず、次の等式が成り立つことを見る。 m が偶数のとき

 

m が奇数のとき

 

この等式を使って、次のような関係式が得られる。

関係式 7
m が奇数のとき

 

および

 

関係式 8
m が偶数で k が正の整数のとき

 

および

 

成り立つ。

また、添字を k 倍したときには、次のような関係式が成り立つ。

関係式 9
k が偶数のとき

 

k が奇数のとき

 

および

 

が成り立つ。

このほか、次のような展開もできる。

関係式 10

 
 

関係式 11
m が偶数のとき

 

m が奇数のとき

 


ルーカス数列の合同式

編集

上に挙げた関係式を用いて、ルーカス数列の整除性および合同に関する重要な性質が導かれる。

まず、関係式 9 から次のことがわかる。

定理 1
k が整数のとき、    を割り切る。 また k が奇数のとき、    を割り切る。


また、添字が素数のときは次の合同式が成り立つ。

定理 2
p が素数のとき

 

が成り立ち、さらに p が奇素数のとき

 

特に

 

が成り立つ。

証明
関係式 11 で、特に p が素数のとき

 

が成り立つ。また、p が奇素数のとき関係式 7 より

 

特に k =1 とおくと

 

となる。

このほか、次の合同式も成り立つ。

定理 3

 
 

証明
関係式 11 から   はすぐわかる。 また、関係式 9 で m=1 とおくと

 

が成り立つ。


合同式における位数の類似概念として、 n の倍数となる   が存在するとき、 そのような r の中で最小のものを   とかく。   は合同式における位数と類似した性質をもっている。

定理 4
  かつ n の倍数となる   が存在するとき、   が成り立つ。

証明
定理 1 より r  の倍数ならば n  を割り切る。

 n の倍数と仮定する。   とおくと、関係式 2 より

 

となるが、先の仮定より  n の倍数で、定理 1 より  n の倍数だから右辺は n の倍数、よって  n の倍数である。定理の仮定より   だから  n の倍数。しかし   だから s =0 つまり rm の倍数である。

重要な事実は、特殊な素数を除いて、フェルマーの小定理の類似の定理が成り立つことである。ただしフェルマーの小定理に比べ、幾分状況は複雑である。

定理 5
p を奇素数とする。 pP , Q , D のいずれも割り切らないとき

 

とおくと p  を割り切る。


証明

  のとき関係式 10 から、

 

であるが、

 

より

 

であるが、  とおくと、右辺は

 

となる。   より   となる   が存在する。 フェルマーの小定理より   なので

 

となる。 p は奇素数なので

 

がわかる。

  のとき再び関係式 10 から、

 

であるが、  のとき

 

の分母は p で割り切れないから、結局  p で割り切れなければならない。よって

 

となる。フェルマーの小定理より   で、オイラーの規準より

 

だから

 

である。


  の偶奇は次の定理から導かれる。

定理 6
n ≥ 0 とする。

  • P , Q が共に偶数ならば    を除いてすべて偶数である。
  • P が偶数で Q が奇数ならば   はつねに偶数で、   の偶奇は n の偶奇と一致する。
  • P が奇数で Q が偶数ならば   はつねに奇数である。
  • P , Q が共に奇数ならば  n が 3 の倍数のとき偶数、それ以外のとき奇数である。

証明
P, Q が共に偶数のとき漸化式

 

より   はすべて偶数である。   より   を除いて   はすべて偶数である。

P が偶数で Q が奇数のとき

 

であるが、  より   はつねに偶数で、   の偶奇は n の偶奇と一致する。

P が奇数で Q が偶数のとき

 

であるが、  より   はつねに奇数である。

P , Q が共に奇数のとき

 

であるが、  より   は共に   となる。 つまり  n が 3 の倍数のとき偶数、それ以外のとき奇数である。