あるフィボナッチ数の和の整除性

この記事の内容

kzaukzau様のこちらの記事 Fibonacci数の和の整除性についてのある予想(解決?) について、
大変興味深かったためしばらく考えていたがある程度形になったので記事にしたい。

まず問題は以下の通りのものとなる。

証明自体は 引用した記事 ですでにつけられており、
本記事をご覧の方はぜひそちらも一読をお勧めする。

こいつはフィボナッチ数列ではない

結論を述べると、この問題を考えるに適切な数列はフィボナッチ数列ではない。
定理1では$s,t$に偶数の条件が課せられているので
和に現れる項はすべてフィボナッチ数列の偶数番目の項$F_{2k}$だが
奇数番目は$F_{2k+1}$ではないとした方がうまくいく。
では奇数番目にいるのは何なのか。奇数番目のフィボナッチ数の代わりに
奇数番目のリュカ数$L_{2k+1}$が代わりにいる。
次のような数列を定義する。

漸化式の形から、偶数番目は偶数番目だけで定義され
奇数番目は奇数番目だけで定義されることがわかる。
また、漸化式の形はフィボナッチ数列、あるいはリュカ数列を定義する
有名な漸化式である$F_{n+1}=F_{n}+F_{n-1}$を２項ごとに
とった数列が満たす漸化式と同じ形となっている。
（ここの詳細は こちらの弊記事 をご参照いただきたい）
$\ G_0=0,\ G_2=1$はフィボナッチ数列の0項目と2項目に一致し、
$G_1=1,\ G_3=4$はリュカ数列の1項目、3項目に一致しているので
この数列$G_n$は偶数番目がフィボナッチ数列$F_{2n}$と
奇数番目がリュカ数列$L_{2n+1}$と一致していることがわかる。
以下、この数列$G_n$の性質を見ることで元の定理を証明する。

$G_n$の満たす漸化式

さて、$G_n$を上のように定義しておいてなんだが、流石に5項間漸化式は面倒くさい。
もうちょっとまからんか、ということで
フィボナッチ数列とリュカ数列の相互関係から次のような関係が言える。

このとき$G_2=h(1)g_1-g_0=1\cdot1-0=1$
$G_3=h(2)g_2-g_1=5\cdot1-1=4$
となり、定義1の2項目、3項目と一致し、また
$G_{n+1}=h(n)G_{n}-G_{n-1}$から
$h(n+1)G_{n+1}=G_{n+2}+G_{n}$
$h(n-1)G_{n-1}=G_{n}+G_{n-2}$
をもとの式に代入すると
$G_{n+2}+G_{n}=h(n+1)h(n)G_{n}-(G_{n}+G_{n-2})$
$G_{n+2}=(h(n+1)h(n)-2）G_{n}-G_{n-2}$
を得る。（$h(n+1)=h(n-1)$を用いている）
$h(n+1)h(n)=5$が$n$によらず成り立つので
$G_{n+2}=3G_{n}-G_{n-2}$となり定義2から
定義1が導ける。よって今後は定義2を用いる。

$G_n$の性質（1）整除性

$G_n$は以下の性質を持つ

偶数番目はフィボナッチ数列だし、リュカ数にしても奇数番目同士なら整除性はある。
偶奇が混ざっても$F_{2n}=F_{n}L_{n}$なので割れるように出来ているのであるが
他でも使うあてがあるので、次の式の成立をもって整除性を示す。

この補題から整除性は直ちに従う

$j_{n,k}$の計算

定理2の証明では用いなかったが、あとで使うことになるため
補題3の$j_{n,k}$が何者であるかを明らかにしておく。

$G_n$の性質（2）最大公約数

$G_n$は以下の性質を持つ

フィボナッチ数でよく見るやつである。
これについても偶数番目はフィボナッチ数列だし、リュカ数にしても奇数番目同士なら成り立っている。
偶奇が混ざると整除性よりはおそらく若干面倒になる。
（$F_{2n}=F_{n}L_{n}$で行けそうだけど、$F_{n}とL_{n}$は$3|n$で共通因数$2$を持つので考えることがある）
こちらも他のついでがあるので、まず次の補題を示す。

係数の$h$がややこしいことになっているが、要は$m,n$の偶奇で決まるんだ、ぐらいのことしか言っていない。
証明の方法は数列$G_n$にかえて$G'_n=G_{sn}/G_s$について考える。
補題3から$G'_n$の漸化式がわかる。
$j_{n,k}$についての計算結果から
$s$が偶数の時$G'_n$は係数に$h(n)$などを含まない線形漸化式で
一般リュカ数列$U_n$になるので加法定理の計算は
一般リュカ数列のそれになる。
その場合の証明は こちらの弊記事 参照。
以下では$s$が奇数の場合について進める。
このとき$G'_n$の満たす漸化式は
$G'_{n+1}=j_{ns,s}G'_{n}-G'_{n-1}$
$j_{ns,s}=h(ns)F_s=h(n)F_s　\because s:odd$
$G'_{n+1}=F_sh(n)G'_{n}-G'_{n-1}$
とし、以下を示す。
$$ G'_{n+m}=h((m+1)n+1)G'_{m}G'_{n+1}-h(m(n-1)+1)G'_{m-1}G'_{n} $$
(両辺に$G_s^2$をかけると補題の形に戻る)

準備が整ったので本題の定理４の証明に進む

$G_n$の和の計算

$G_n$の和の計算のため補題5を利用する。
補題5で$m=n$とすると
$ G_sG_{2sn}=h(s(n+1)n+1)G_{sn}G_{s(n+1)}-h(sn(n-1)+1)G_{s(n-1)}G_{sn} $
$n(n+1)$は偶数なので
$ G_sG_{2sn}=h(1)G_{sn}G_{s(n+1)}-h(1)G_{s(n-1)}G_{sn} $
$ G_sG_{2sn}=G_{s(n+1)}G_{sn}-G_{sn}G_{s(n-1)} $
$s$は任意の自然数、$G_{2sn}=F_{2sn}$なので
$$ \sum_{k=0}^{n}F_{2sk}=\frac{1}{G_s}\sum_{k=0}^{n}（G_{s(k+1)}G_{sk}-G_{sk}G_{s(k-1)}) $$
$$ \sum_{k=0}^{n}F_{2sk}=\frac{G_{s(n+1)}G_{sn}-G_{s\cdot 1}G_{s\cdot 0}}{G_s}=\frac{G_{s(n+1)}G_{sn}}{G_s} $$

$\sum_{k=0}^{n}F_{2sk}$の整除性

$$ \sum_{k=0}^{n}F_{2sk}=\frac{G_{s(n+1)}G_{sn}}{G_s} $$
について$\operatorname{GCD}(G_{s(n+1)},G_{sn})=G_s$なので
$$ \sum_{k=0}^{n} F_{2sk}=\frac{G_{s(n+1)}G_{sn}}{\operatorname{GCD}(G_{s(n+1)},G_{sn})}=\operatorname{LCM}(G_{s(n+1)},G_{sn}) $$
ここで$\operatorname{LCM}$は2項の最小公倍数を表す。
これより$s|t$なる自然数$s,t$について

$$ \sum_{k=0}^{n} F_{2sk}=\operatorname{LCM}(G_{s(n+1)},G_{sn}) ,\ \sum_{k=0}^{n} F_{2tk}=\operatorname{LCM}(G_{t(n+1)},G_{tn}) $$
（係数$2$を外出ししているので$s,t$が$2$の倍数である必要はない。）
$s|t$と$G_n$の整除性により$G_{sn}|G_{tn}\ ,\ G_{s(n+1)}|G_{t(n+1)}$であるので
$\operatorname{LCM}(G_{t(n+1)},G_{tn})$は$G_{sn},G_{s(n+1)}$の公倍数であることがわかる。
よって、最小公倍数の性質から
$\operatorname{LCM}(G_{s(n+1)},G_{sn})|\operatorname{LCM}(G_{t(n+1)},G_{tn})$
即ち
$$ \sum_{k=0}^{n} F_{2sk}\big|\sum_{k=0}^{n} F_{2tk}　 $$
が言えた。