P, Q, D を
となる整数とし、
を2次方程式
の解とする(D ≠ 0 より この2次方程式は2つの相異なる解をもつ)。
このとき
![{\displaystyle P=\alpha +\beta ,Q=\alpha \beta ,D=(\alpha -\beta )^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f76007750f75ded36fc23d8bebcbc7931342df4b)
が成り立つ。
線形回帰数列 で述べたように、数列
について、
漸化式
![{\displaystyle a_{n+2}=Pa_{n+1}-Qa_{n}(n=0,1,\ldots )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/483706072f48fb1c1919006ddcba5df6260e7a88)
を満足することと、一般項が
![{\displaystyle a_{n}=\zeta \alpha ^{n}+\eta \beta ^{n}(n=0,1,\ldots )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/548a2d94a61ab14f8d1b3034739afba53b4393a5)
の形に表されることは同値である。
特に、線形回帰数列でも例にあげたフィボナッチ数のように、
![{\displaystyle U_{n}={\frac {\alpha ^{n}-\beta ^{n}}{\alpha -\beta }},V_{n}=\alpha ^{n}+\beta ^{n}(n=0,1,\ldots )\cdots (*)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae8d0f97f0dca678f2dc163db1a7093188dc3cd8)
により定まる数列
はいずれも上記の漸化式を満足し、初項は
![{\displaystyle U_{0}=0,U_{1}=1,V_{0}=2,V_{1}=\alpha +\beta =P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7c0b621f4248fa4f69591116e00726502047efd)
により与えられる。逆に、これらの初項と漸化式で与えられる数列の一般項は (*) であらわされる。
このようにして定まる数列
を
に関するルーカス数列と呼ぶ。
また、数列
のみを単にルーカス数列といい、
を同伴ルーカス数列と呼ぶこともある。
フィボナッチ数列
は
(1, -1) に関するルーカス数列である。また、この同伴数列は
により定まり、
2, 1, 3, 4, 7, 11, 18, 29, 47, ... で始まる。
そして、これらの数列の一般項は
![{\displaystyle F_{n}={\frac {\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}}{\sqrt {5}}},L_{n}=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}+\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/783c2fbccb00be6a822fe4a38f1a3e5c9d5412be)
により与えられる。
の要素をフィボナッチ数と呼ぶのに対し、
の要素をルーカス数という。
(2, -1) に関するルーカス数列は 0, 1, 2, 5, 12, 29, 70, ... および 2, 2, 6, 14, 34, 82, 198, ... で始まる。一般項は
![{\displaystyle U_{n}={\frac {(1+{\sqrt {2}})^{n}-(1-{\sqrt {2}})^{n}}{2{\sqrt {2}}}},V_{n}=(1+{\sqrt {2}})^{n}+(1-{\sqrt {2}})^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b371843c4909eea80d9667ad14609bb851c82ca0)
により与えられる。これらの数列はペル数列と呼ばれる(後に議論するが、ペル方程式と呼ばれる不定方程式の解としてあらわれる)。
ルーカス数列には重要な関係式が多数存在するが、証明まで記載すると長大になるので、証明は別に記す。
まず、次の関係式が成立する。
関係式 1
![{\displaystyle {\begin{aligned}V_{n}^{2}-DU_{n}^{2}=&4Q^{n},\\U_{n}^{2}-U_{n-1}U_{n+1}=&-Q^{n-1}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/86de69f52d8ab1d32bea65b6d5e8f3485a1f674a)
特に、
のとき、
はペル方程式の解となっていることがわかる。例えばペル数列に対し、
とおくとペル方程式
の解が得られる。
次に、添字の加法に関して、次のような、三角関数の加法定理に類似した関係式が成り立つ。
関係式 2
![{\displaystyle {\begin{aligned}2U_{m+n}=&U_{m}V_{n}+U_{n}V_{m},\\2Q^{n}U_{m-n}=&U_{m}V_{n}-U_{n}V_{m},\\U_{m+n}=&U_{m}U_{n+1}-QU_{m-1}U_{n},\\2V_{m+n}=&V_{m}V_{n}+DU_{m}U_{n}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25fd62e997314152fbc1e3901bebc789315c4611)
関係式 3
![{\displaystyle {\begin{aligned}U_{m+n}=&U_{m}V_{n}-Q^{n}U_{m-n},\\V_{m+n}=&V_{m}V_{n}-Q^{n}V_{m-n}=DU_{m}U_{n}+Q^{n}V_{m-n}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/30c7479b24c338e60d8165c673a0b9c5b56ed127)
次のような関係式も成り立つ。
関係式 4
![{\displaystyle {\begin{aligned}DU_{n}=&V_{n+1}-QV_{n-1},\\V_{n}=&U_{n+1}-QU_{n-1}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02223f3e45f0ebdcb69b5531fd513d6827cf06bc)
関係式 2, 3 の特殊な場合として、添字を2倍, 3倍したとき、次のような関係が成り立つ。
関係式 5
![{\displaystyle {\begin{aligned}U_{2n}=&U_{n}V_{n},\\V_{2n}=&V_{n}^{2}-2Q^{n}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/72234f22c829d03ec00def49b87dd9e2b0870065)
関係式 6
![{\displaystyle {\begin{aligned}U_{3n}=&U_{n}(V_{n}^{2}-Q^{n})=U_{n}(DU_{n}^{2}+3Q^{n}),\\V_{3n}=&V_{n}(V_{n}^{2}-3Q^{n}).\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02c5b56769bf07144a53bbf8ded71d9a1dfaf5c4)
より一般的な、添字の乗法について考えたい。そのために、まず、次の等式が成り立つことを見る。
m が偶数のとき
![{\displaystyle {\begin{aligned}(X+Y)^{m}=&\sum _{r=0}^{m}{\binom {m}{r}}X^{r}Y^{m-r}\\=&\sum _{r=0}^{{\frac {m}{2}}-1}{\binom {m}{r}}(X^{r}Y^{m-r}+X^{m-r}Y^{r})+{\binom {m}{m/2}}(XY)^{\frac {m}{2}}\\=&\sum _{r=0}^{{\frac {m}{2}}-1}{\binom {m}{r}}(XY)^{r}(X^{m-2r}+Y^{m-2r})+{\binom {m}{m/2}}(XY)^{\frac {m}{2}},\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aad4c8f603767d389b1ebb790f3c02f85f0f3e70)
m が奇数のとき
![{\displaystyle {\begin{aligned}(X+Y)^{m}=&\sum _{r=0}^{m}{\binom {m}{r}}X^{r}Y^{m-r}\\=&\sum _{r=0}^{\frac {m-1}{2}}{\binom {m}{r}}(X^{r}Y^{m-r}+X^{m-r}Y^{r})\\=&\sum _{r=0}^{\frac {m-1}{2}}{\binom {m}{r}}(XY)^{r}(X^{m-2r}+Y^{m-2r}).\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3e1777a6770287e37953d31910c9bb05d82d9d8)
この等式を使って、次のような関係式が得られる。
関係式 7
m が奇数のとき
![{\displaystyle {\begin{aligned}D^{\frac {m-1}{2}}U_{k}^{m}=&\sum _{r=0}^{\frac {m-1}{2}}{\binom {m}{r}}(-1)^{r}Q^{kr}U_{k(m-2r)}\\=&U_{km}-{\binom {m}{1}}Q^{k}U_{k(m-2)}+{\binom {m}{2}}Q^{2k}U_{k(m-4)}-\cdots +(-1)^{\frac {m-1}{2}}{\binom {m}{(m-1)/2}}Q^{{\frac {m-1}{2}}k}U_{k}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ef22686ba05f12e912f564612b26c06a7efb918)
および
![{\displaystyle {\begin{aligned}V_{k}^{m}=&\sum _{r=0}^{\frac {m-1}{2}}{\binom {m}{r}}Q^{kr}V_{k(m-2r)}\\=&U_{km}+{\binom {m}{1}}Q^{k}V_{k(m-2)}+{\binom {m}{2}}Q^{2k}V_{k(m-4)}+\cdots +{\binom {m}{(m-1)/2}}Q^{{\frac {m-1}{2}}k}V_{k}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/64090bef498015c2bb39c26de9412b1d4fca2c9d)
関係式 8
m が偶数で k が正の整数のとき
![{\displaystyle {\begin{aligned}D^{\frac {m}{2}}U_{k}^{m}=&\sum _{r=0}^{{\frac {m}{2}}-1}{\binom {m}{r}}(-1)^{r}Q^{kr}V_{k(m-2r)}+(-1)^{\frac {m}{2}}{\binom {m}{m/2}}Q^{\frac {mk}{2}}\\=&V_{km}-{\binom {m}{1}}Q^{k}V_{k(m-2)}+{\binom {m}{2}}Q^{2k}V_{k(m-4)}-\cdots +(-1)^{{\frac {m}{2}}-1}{\binom {m}{m/2-1}}Q^{\left({\frac {m}{2}}-1\right)k}V_{2k}+(-1)^{\frac {m}{2}}{\binom {m}{m/2}}Q^{\frac {mk}{2}},\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a161274917a4dea278c28e10644e9c27656309d)
および
![{\displaystyle {\begin{aligned}V_{k}^{m}=&\sum _{r=0}^{{\frac {m}{2}}-1}{\binom {m}{r}}Q^{kr}V_{k(m-2r)}+{\binom {m}{m/2}}Q^{\frac {mk}{2}}\\=&V_{km}+{\binom {m}{1}}Q^{k}V_{k(m-2)}+{\binom {m}{2}}Q^{2k}V_{k(m-4)}+\cdots +{\binom {m}{m/2-1}}Q^{\left({\frac {m}{2}}-1\right)k}V_{2k}+{\binom {m}{m/2}}Q^{\frac {mk}{2}}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/846ba21078faddf4430eceaa48e5a333b2d041f5)
成り立つ。
また、添字を k 倍したときには、次のような関係式が成り立つ。
関係式 9
k が偶数のとき
![{\displaystyle U_{km}=U_{m}\sum _{r=0}^{{\frac {k}{2}}-1}Q^{mr}V_{m(k-1-2r)}=U_{m}(V_{m(k-1)}+Q^{m}V_{m(k-3)}+\cdots ),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f0774a754fe52c5dfa2bacf58541d59bfb3c7ed7)
k が奇数のとき
![{\displaystyle U_{km}=U_{m}\left(Q^{\frac {m(k-1)}{2}}+\sum _{r=0}^{\frac {k-3}{2}}Q^{mr}V_{m(k-1-2r)}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d52df410cf72d4440c9912392f0a502912f219ac)
および
![{\displaystyle V_{km}=V_{m}\left((-1)^{\frac {k-1}{2}}Q^{\frac {m(k-1)}{2}}+\sum _{r=0}^{\frac {k-3}{2}}(-1)^{r}Q^{mr}V_{m(k-1-2r)}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c8ec3b256e39975cc35144a899cf1245adaad1b9)
が成り立つ。
このほか、次のような展開もできる。
関係式 10
![{\displaystyle 2^{n-1}U_{n}={\binom {n}{1}}P^{n-1}+{\binom {n}{3}}P^{n-3}D+\cdots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/60b5c2a62bb726d2c7619d6dfb75507782db2131)
![{\displaystyle 2^{n-1}V_{n}=P^{n}+{\binom {n}{2}}P^{n-2}D+{\binom {n}{4}}P^{n-4}D^{2}+\cdots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d9920348b0dbcfd31e155c14a6091132cc82444)
関係式 11
m が偶数のとき
![{\displaystyle P^{m}=\sum _{r=0}^{{\frac {m}{2}}-1}{\binom {m}{r}}Q^{r}V_{m-2r}+{\binom {m}{m/2}}Q^{\frac {m}{2}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df29ab7a789b641db05130f764ecd622371e6dc6)
m が奇数のとき
![{\displaystyle P^{m}=\sum _{r=0}^{\frac {m-1}{2}}{\binom {m}{r}}Q^{r}V_{m-2r}=V_{m}+mQV_{m-2}+{\binom {m}{2}}Q^{2}V_{m-4}+\cdots .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7e1769fda1caa41f98ca343a1a45d6e0dd0afca)
上に挙げた関係式を用いて、ルーカス数列の整除性および合同に関する重要な性質が導かれる。
まず、関係式 9 から次のことがわかる。
定理 1
k が整数のとき、
は
を割り切る。
また k が奇数のとき、
は
を割り切る。
また、添字が素数のときは次の合同式が成り立つ。
定理 2
p が素数のとき
![{\displaystyle V_{p}\equiv P{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c8404b8324b43d2e0a923289155cbaf0bfa76a4)
が成り立ち、さらに p が奇素数のとき
![{\displaystyle U_{kp}\equiv \left({\frac {D}{p}}\right)U_{k}{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/796939a7448ead4a4a891c43f26391e4839d29f4)
特に
![{\displaystyle U_{p}\equiv \left({\frac {D}{p}}\right){\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0256a2eeeb67e41f4ebad45bd8c703560797fa67)
が成り立つ。
証明
関係式 11 で、特に p が素数のとき
![{\displaystyle V_{p}\equiv P^{p}\equiv P{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c636901f57763f925ee4c3f0dff3a4ea154c567)
が成り立つ。また、p が奇素数のとき関係式 7 より
![{\displaystyle U_{kp}\equiv D^{\frac {p-1}{2}}U_{k}^{p}\equiv \left({\frac {D}{p}}\right)U_{k}{\pmod {p}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f1e2083ea69d00a15eb05ef1a519fe758ab89b57)
特に k =1 とおくと
![{\displaystyle U_{p}\equiv \left({\frac {D}{p}}\right){\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0256a2eeeb67e41f4ebad45bd8c703560797fa67)
となる。
このほか、次の合同式も成り立つ。
定理 3
![{\displaystyle V_{k}\equiv P^{k}{\pmod {Q}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f30c9d26d946c4715b48bd4497d409b936fd02f)
![{\displaystyle U_{k}\equiv V_{k-1}{\pmod {Q}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e6e141cf0b7fe02ac68b6be542b4fa83991edb4)
証明
関係式 11 から
はすぐわかる。
また、関係式 9 で m=1 とおくと
![{\displaystyle U_{k}=V_{k-1}+QV_{k-3}+\cdots \equiv V_{k-1}{\pmod {Q}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5d79f418ebdc6ae9599470b565fc2d0c46c9a8bd)
が成り立つ。
合同式における位数の類似概念として、 n の倍数となる
が存在するとき、
そのような r の中で最小のものを
とかく。
は合同式における位数と類似した性質をもっている。
定理 4
かつ n の倍数となる
が存在するとき、
が成り立つ。
証明
定理 1 より r が
の倍数ならば n は
を割り切る。
が n の倍数と仮定する。
とおくと、関係式 2 より
![{\displaystyle 2Q^{n}U_{s}=2Q^{n}U_{r-qm}=U_{r}V_{qm}-U_{qm}V_{r}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/abfd7c93c581bed6a0016e4ff539b98e4e14aded)
となるが、先の仮定より
が n の倍数で、定理 1 より
も n の倍数だから右辺は
n の倍数、よって
も n の倍数である。定理の仮定より
だから
も n の倍数。しかし
だから s =0 つまり r は m の倍数である。
重要な事実は、特殊な素数を除いて、フェルマーの小定理の類似の定理が成り立つことである。ただしフェルマーの小定理に比べ、幾分状況は複雑である。
定理 5
p を奇素数とする。
p が P , Q , D のいずれも割り切らないとき
![{\displaystyle \psi (p)=p-\left({\frac {D}{p}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b348d9d6d3bde83e0fc49f9f81c6302d58672ec4)
とおくと p は
を割り切る。
証明
のとき関係式 10 から、
![{\displaystyle 2^{p-2}U_{p-1}={\binom {p-1}{1}}P^{p-2}+{\binom {p-1}{3}}P^{p-4}D+\cdots +{\binom {p-1}{p-2}}PD^{\frac {p-3}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8dd8ee40927aaac7ad0b6ad8e3cfe2adc0a6f84c)
であるが、
![{\displaystyle {\binom {p-1}{k}}={\frac {(p-1)(p-2)\cdots (p-k)}{1\cdot 2\cdots k}}\equiv (-1)^{k}{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef28393b5b2d6850c951f3ce7e863a238e241f45)
より
![{\displaystyle 2^{p-2}U_{p}\equiv -(P^{p-2}+P^{p-4}D+\cdots +PD^{\frac {p-3}{2}}){\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6bf50a7e9a40459bcbfe96aea80ebc34e08e145a)
であるが、
とおくと、右辺は
![{\displaystyle -PG_{(p-1)/2}(P^{2},D)=-P\cdot {\frac {P^{p-1}-D^{\frac {p-1}{2}}}{P^{2}-D}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a822c7efef0b81f8d2cd15d3ecf1d9bcb709d7b7)
となる。
より
となる
が存在する。
フェルマーの小定理より
なので
![{\displaystyle 2^{p-2}U_{p-1}\equiv -P\cdot {\frac {P^{p-1}-C^{p-1}}{P^{2}-C^{2}}}\equiv 0{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0694062fa27359ee7b86d3e539d0dcabe814df9d)
となる。 p は奇素数なので
![{\displaystyle U_{p-1}\equiv 0{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6fc8ebce6f16c043b33abd4ef08c99959e15711c)
がわかる。
のとき再び関係式 10 から、
![{\displaystyle 2^{p}U_{p+1}={\binom {p+1}{1}}P^{p}+{\binom {p+1}{3}}P^{p-2}D+\cdots +{\binom {p+1}{p}}PD^{\frac {p-1}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd46b175926c9dd22bab16b1f748e11ef965723f)
であるが、
のとき
![{\displaystyle {\binom {p+1}{k}}={\frac {(p+1)!}{k!(p+1-k)!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/715cca2e8cecf899372f1344038f97d3a2157533)
の分母は p で割り切れないから、結局
は p で割り切れなければならない。よって
![{\displaystyle 2^{p}U_{p+1}\equiv (p+1)(P^{p}+PD^{\frac {p-1}{2}})\equiv P^{p}+PD^{\frac {p-1}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e2f2a1d5bdd135ea1d0cd54db906f5f431c49e4b)
となる。フェルマーの小定理より
で、オイラーの規準より
![{\displaystyle D^{\frac {p-1}{2}}\equiv \left({\frac {D}{p}}\right)=-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5937c50916902c72365fa4025c013968b28f6fc1)
だから
![{\displaystyle 2^{p}U_{p+1}\equiv P(1+D^{\frac {p-1}{2}})\equiv 0{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce696fa1badab9fadd8cdfb1a3518773c13e197c)
である。
の偶奇は次の定理から導かれる。
定理 6
n ≥ 0 とする。
- P , Q が共に偶数ならば
は
を除いてすべて偶数である。
- P が偶数で Q が奇数ならば
はつねに偶数で、
の偶奇は n の偶奇と一致する。
- P が奇数で Q が偶数ならば
はつねに奇数である。
- P , Q が共に奇数ならば
は n が 3 の倍数のとき偶数、それ以外のとき奇数である。
証明
P, Q が共に偶数のとき漸化式
![{\displaystyle U_{n+2}=PU_{n+1}-QU_{n},V_{n+2}=PV_{n+1}-QV_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/67aceef0f0b04a631511c682ef48f87119fdb3c1)
より
はすべて偶数である。
より
を除いて
はすべて偶数である。
P が偶数で Q が奇数のとき
![{\displaystyle U_{n+2}=PU_{n+1}-QU_{n}\equiv U_{n},V_{n+2}=PV_{n+1}-QV_{n}\equiv V_{n}{\pmod {2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ae55a080e78495e299a2a172d18968570f60146)
であるが、
より
はつねに偶数で、
の偶奇は n の偶奇と一致する。
P が奇数で Q が偶数のとき
![{\displaystyle U_{n+2}=PU_{n+1}-QU_{n}\equiv U_{n+1},V_{n+2}=PV_{n+1}-QV_{n}\equiv V_{n+1}{\pmod {2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/077055269c29ba424c4ef20b9c12eea0c91bf195)
であるが、
より
はつねに奇数である。
P , Q が共に奇数のとき
![{\displaystyle U_{n+2}=PU_{n+1}-QU_{n}\equiv U_{n+1}+U_{n},V_{n+2}=PV_{n+1}-QV_{n}\equiv V_{n+1}+V_{n}{\pmod {2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/707da0a5fc2666ef77abca47f9efbbd18b56d29a)
であるが、
より
は共に
となる。
つまり
は n が 3 の倍数のとき偶数、それ以外のとき奇数である。