フィボナッチ数列などの一般リュカ数列の整除性
リュカ数列の定義
はリンク先のwikipedia記事に従うこととする。
$$
U_{n}(P,Q)=\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta},V_{n}(P,Q)=\alpha^{n}+\beta^{n},\alpha=\frac{P+\sqrt{D}}{2},\alpha=\frac{P-\sqrt{D}}{2},D=P^2
$$
以下(P,Q)の記載は省略する。これらU_n,V_nはいずれも同じ漸化式を満たす。すなわち
$$
U_{n+1}-PU_{n}+QU_{n-1}=0,V_{n+1}-PV_{n}+QV_{n-1}=0
$$
n=0,1の場合について、定義のnに代入することでU_0=0,u_1=1,V_0=2,V_1=Pとなる。
以下ではもともとの定義式よりもここで確認した漸化式と第1,2項をもとに
U_nの整除性について考える。（P,Qは整数とする。）
$$ 自然数m,nについて m|nならばU_m|U_n $$
これはとくにフィボナッチ数列
$$
F_{n+1}=F_{n}+F_{n-1},F_0=0,F_1=1
$$
についての系である
フィボナッチ数列の整除性
$$自然数m,nについて m|nならばF_m|F_n$$
の形でよく知られている。
定理1を示すために次の補題を示す。
$$
U_{n+1}-PU_{n}+QU_{n-1}=0
$$
を満たす数列U_nについて、この数列をk個毎に取った数列は
$$
U_{n+k}-V_kU_{n}+Q^{k}U_{n-k}=0
$$
を満たす。
kについての数学的帰納法で示す。
$$
k=1の場合、V_1=P、Q^1＝Qより成り立つ。また
$$
$$PU_{n}=U_{n+1}+QU_{n-1}より、$$
$$
PU_{n+1}-P^2U_{n}+PQU_{n-1}=P\cdot0=0
$$
$$
(U_{n+2}+QU_{n})-P^2U_{n}+Q(U_{n}+QU_{n-2})=0
$$
$$
U_{n+2}-（P^2-2Q)U_{n}+Q^2U_{n-2}=0
$$
となり$$V_2=PV_1-QV_0=P\cdot P-Q\cdot2=P^2-2Q$$
よりk=2でも成り立つ。
kがm,m+1の場合も成り立つと仮定すると
$$
U_{n+m}-V_{m}U_{n}+Q^{m}U_{n-m}=0 (1)
$$
$$
U_{n+m+1}-V_{m+1}U_{n}+Q^{m+1}U_{n-m-1}=0 (2)
$$
$$
が成り立つ。P\cdot(2)-Q(1)を計算すると
$$
$$
(PU_{n+m+1}-QU_{n+m})-(PV_{m+1}-QV_{m})U_n+Q^{m+1}(PU_{n-m-1}-U_{n-m})=0
$$
$$
U_{n+m+2}-V_{m+2}U_n+Q^{m+1}(QU_{n-m-2})=0
$$
$$
U_{n+m+2}-V_{m+2}U_n+Q^{m+2}U_{n-m-2}=0
$$
となりk=m+2でも成り立つことがわかるため
任意のkで成り立つ。
この補題をフィボナッチ数で書き下すと
$$
F_{n+k}=L_kF_n+(-1)^{k-1}F_{n-k}
$$
となる。ここでL_kは一般化でないいわゆるリュカ数。
さて、補題を用いれば定理1の証明は直ちに終わる。
$$
整数k\geq 0についてU_m|U_{mk}を示せばよい。数学的帰納法で示す。
$$
$$
k=0,1のときについてU_{m\cdot 0}=U_0=0、U_{m\cdot 1}=U_m より成り立つ。
$$
$$
k=i-1,iで成り立つ、
つまりU_m|U_{(i-1)},U_m|U_{mi}が成り立つと仮定する。
$$
$$
このとき補題より
$$
$$
U_{mi+m}-V_mU_{mi}+Q^{m}U_{mi-m}=0 となるので
$$
$$
U_{m(i+1)}=V_mU_{mi}-Q^{m}U_{m(i-1)}
$$
$$
U_m|U_{m(i-1)},U_m|U_{mi}よりU_m|U_{m(i+1)}がわかり、よって任意のkで成り立つ。
$$
$$ これはnの倍数は0からn個ごとにあるという整数の性質の一般化。 $$
記事書いてるだけでいつまでたっても終わる気がしないのでとりあえず一旦投稿
→思ったより長いので次の投稿にする。
次の記事はこちら
この記事を高評価した人
この記事に送られたバッジ
投稿者
