0

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

88
0

この記事の内容

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

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

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

Fnをn番目のフィボナッチ数とし、s|tとなる正の偶数s,tに対して

k=0nFskk=0nFtk

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

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

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

数列Gnを次の隣接5項間漸化式で定義する
Gn+4=3Gn+2Gn,
 G0=0, G1=1, G2=1, G3=4

漸化式の形から、偶数番目は偶数番目だけで定義され
奇数番目は奇数番目だけで定義されることがわかる。
また、漸化式の形はフィボナッチ数列、あるいはリュカ数列を定義する
有名な漸化式であるFn+1=Fn+Fn1を2項ごとに
とった数列が満たす漸化式と同じ形となっている。
(ここの詳細は こちらの弊記事 をご参照いただきたい)
 G0=0, G2=1はフィボナッチ数列の0項目と2項目に一致し、
G1=1, G3=4はリュカ数列の1項目、3項目に一致しているので
この数列Gnは偶数番目がフィボナッチ数列F2n
奇数番目がリュカ数列L2n+1と一致していることがわかる。
以下、この数列Gnの性質を見ることで元の定理を証明する。

Gnの満たす漸化式

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

Gn+1=h(n)GnGn1,
h(n)={1n:5n:, G0=0, G1=1

このときG2=h(1)g1g0=110=1
G3=h(2)g2g1=511=4
となり、定義1の2項目、3項目と一致し、また
Gn+1=h(n)GnGn1から
h(n+1)Gn+1=Gn+2+Gn
h(n1)Gn1=Gn+Gn2
をもとの式に代入すると
Gn+2+Gn=h(n+1)h(n)Gn(Gn+Gn2)
Gn+2=(h(n+1)h(n)2GnGn2
を得る。(h(n+1)=h(n1)を用いている)
h(n+1)h(n)=5nによらず成り立つので
Gn+2=3GnGn2となり定義2から
定義1が導ける。よって今後は定義2を用いる。

Gnの性質(1)整除性

Gnは以下の性質を持つ

Gnの項番についての整除性

自然数n,mについてn|mのときGn|Gm

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

k項ごと数列の満たす漸化式

Gn+k=jn,kGnGnk
jn,k+1=h(n+k)jn,kjn,k1 jn,1=h(n),jn,2=3

補題3の証明
補題3の証明
定義2から
Gn+1=h(n)GnGn1なので
k=1 jn,1=h(n)
定義2から定義1を得る計算の際に示した通り
Gn+2=3GnGn2なので
k=2 jn,2=3
k=m1,k=mで成り立つと仮定する。このとき
Gn+m1=jn,m1GnGnm+1(1)
Gn+m=jn,mGnGnm(2)
h(n+m)(2)(1)を計算すると
Gn+m+1=(h(n+m)jn,mjn,m1Gnh(n+m)Gnm+Gnm+1
Gn+m+1=(h(n+m)jn,mjn,m1Gnh(nm+2m)Gnm+Gnm+1
Gn+m+1=(h(n+m)jn,mjn,m1Gnh(nm)Gnm+Gnm+1
Gn+m+1=(h(n+m)jn,mjn,m1GnGnm1
となるのでjn,m+1=h(n+m)jn,mjn,m1とすれば
数学的帰納法より補題3が成り立つことがわかる

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

定理2の証明

任意の自然数kについてGn|Gknを示す
kについての数学的帰納法で示す。
k=1のときあきらか
kmのとき成り立つと仮定すると
Gn|G(m1)n,Gn|Gmnなので
G(m+1)n=jmn,mGnmG(m1)n
よりGn|G(m+1)nk=m+1でも成り立つ。
よって任意の自然数kについてGn|Gknは示された。

jn,kの計算

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

jn,kの計算
この数列はn,kいずれにも依存するがnへの依存は漸化式からわかる通り
h(n+k)の部分に限られ、h(n+k)n+kの偶奇しか影響しないので
nについて考える必要があるのはその偶奇だけということがわかる。
ゆえ、jn,kについて、特にnが偶数の場合をj0,k
nが奇数の場合をj1,kと書くことにする。
nが偶数の場合
h(n+k)=h(k)なので漸化式は
j0,k+1=h(k)j0,kj0,k1, j0,1=h(0)=5,j0,2=3
となる。初項、2項目が違うだけでGnと同じ漸化式であることがわかった。
何項か計算すると
j0,3=h(2)j0,2j0,1=535=10
j0,4=h(3)j0,3j0,2=103=7
j0,1=5,j0,3=10=52
j0,k+1=h(k)j0,kj0,k1なので
j0,2k+1=5F2k+1とわかる。同様に
j0,2=3,j0,4=7なのでj0,2k=L2kとわかる。
概ねGnをひっくり返したような数列になっている。
nが奇数の場合
h(n+k)=h(k+1)なので漸化式は
j1,k+1=h(k+1)j1,kj1,k1, j1,1=h(1)=1,j1,2=3
続く2項は
j1,3=h(3)j1,2j1,1=31=2
j1,4=h(4)j1,3j1,2=523=7
j1,k+1=h(k+1)j1,kj1,k1についても
2項ごとの漸化式に変形するとやはり
j1,k+2=3j1,kj1,k2が得られるので、
j1,2k+1=F2k+1,j1,2k=L2k
以上から
jn,2k+1=h(n)F2k+1,jn,2k=L2k
とまとめられることがわかる。

Gnの性質(2)最大公約数

Gnは以下の性質を持つ

Gnの項間の最大公約数

自然数n,mについてGCD(Gn,Gm)=GGCD(n,m)

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

Gnの加法定理(拡張版)

GsGs(n+m)=h(s(m+1)n+1)GsmGs(n+1)h(sm(n1)+1)Gs(m1)Gsn

係数のhがややこしいことになっているが、要はm,nの偶奇で決まるんだ、ぐらいのことしか言っていない。
証明の方法は数列GnにかえてGn=Gsn/Gsについて考える。
補題3からGnの漸化式がわかる。
jn,kについての計算結果から
sが偶数の時Gnは係数にh(n)などを含まない線形漸化式で
一般リュカ数列Unになるので加法定理の計算は
一般リュカ数列のそれになる。
その場合の証明は こちらの弊記事 参照。
以下ではsが奇数の場合について進める。
このときGnの満たす漸化式は
Gn+1=jns,sGnGn1
jns,s=h(ns)Fs=h(n)Fs s:odd
Gn+1=Fsh(n)GnGn1
とし、以下を示す。
Gn+m=h((m+1)n+1)GmGn+1h(m(n1)+1)Gm1Gn
(両辺にGs2をかけると補題の形に戻る)

補題5の証明
補題5(Gnの拡張加法定理)の証明
数学的帰納法で示す。
m=1のとき
 h(2n+1)G1Gn+1h((n1)+1)G0Gn
=h(1)1Gn+1h(n)0Gn
=Gn+1
より正しい。
m=2のとき
 h(n+1)G2Gn+1h(1)G1Gn
=h(n+1)G2Gn11Gn
=h(n+1)FsGn+1Gn
 Gn+2

より正しい

mkで正しいと仮定する。このとき
Gn+(k1)=h(kn+1)Gk1Gn+1h((k1)(n1)+1)G(k2)Gn(1)
Gn+k=h((k+1)n+1)GkGn+1h(k(n1)+1)Gk1Gn(2)
Fsh(n+k)(2)(1)を計算すると左辺はGn+k+1、右辺は
長くなるのでGnでくくった係数だけ見ると
Fsh(n+k)h(k(n1)+1)Gk1h((k1)(n1)+1)G(k2)
h((k+1)(n1)+1)=h((k1)(n1)+1)をくくりだすと
h((k+1)(n1)+1){Fsh(n+k)h(k(n1)+1)/h((k+1)(n1)+1)Gk1Gk2}
Gk1の係数の因子であるh(n+k)h(k(n1)+1)/h((k+1)(n1)+1)について
nを偶数とすると
 h(n+k)h(k(n1)+1)/h((k+1)(n1)+1)
=h(k)h(k+1)/h(k+1+1)
=h(k+1)
nを奇数とすると
 h(n+k)h(k(n1)+1)/h((k+1)(n1)+1)
=h(1+k)h(1)/h(1)
=h(k+1)
よってnの偶奇によらず
h(n+k)h(k(n1)+1)/h((k+1)(n1)+1)=h(k+1)=h(k1)
ゆえ
 h((k+1)(n1)+1){Fsh(n+k)h(k(n1)+1)/h((k+1)(n1)+1)Gk1G(k2)}
=h((k+1)(n1)+1)(Fsh(k1)Gk1Gk2)
=h((k+1)(n1)+1)Gk

Fsh(n+k)(2)(1)Gn+1でくくった係数を見ると
Fsh(n+k)h((k+1)n+1)Gkh(kn+1)Gk1
h((k+2)n+1)=h(kn+1)をくくりだすと
h(kn+1){Fsh(n+k)h((k+1)n+1)/h(kn+1)GkGk1}
h(n+k)h((k+1)n+1)/h(kn+1)は先ほど同様に
nの偶奇によらずh(k)となることがわかるので
 Fsh(n+k)h((k+1)n+1)Gkh(kn+1)Gk1
=h(kn+1){Fsh(k)GkGk1}
=h(kn+1)Gk+1

以上から
Gn+k+1=h(kn+1)Gk+1Gn+1h((k+1)(n1)+1)GkGn
となりm=k+1の時も成り立ち、任意の自然数mで成り立つことが示せる。

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

定理4
定理4(Gnの最大公約数)の証明
補題3と補題5より一般に自然数x,y(x>y)について
jx,yGxGxy=h((y+1)x+1)GyGx+1h(y(x1)+1)Gy1Gx
ゆえ
Gxy={h(y(x1)+1)Gy1+jx,y}Gxh((y+1)x+1)GyGx+1
が成り立つ。
GCD(n,m)=lと書くことにするとき
ベズーの等式よりan+bm=lとなる整数a,bが存在する。
n,m,l全て正の数でln,lmよりa,bのいずれかは非正。
適当に文字を置きなおしてanbm=l a,b0としてよい。

Ganbm={h((an1)bm+1)Gbm+1+jan,bm}Ganh((bm+1)an+1)Gan+1Gbm
左辺はGlとなる。
右辺についてGn|Gan,Gm|Gbmより
Gan=AGn,GbmBGm,A,Bと書くことにすると
Gl={h((an1)bm+1)Gbm+1+jan,bm}AGnh((bm+1)an+1)Gan+1BGm
と表せるので、ベズーの等式より
GCD(Gn,Gm)|Gl
またGCD(n,m)=lよりl|n,l|mなのでGl|Gn,Gl|Gm
よってGl|GCD(Gn,Gm)
以上から
GCD(Gn,Gm)=GGCD(n,m)

Gnの和の計算

Gnの和の計算のため補題5を利用する。
補題5でm=nとすると
GsG2sn=h(s(n+1)n+1)GsnGs(n+1)h(sn(n1)+1)Gs(n1)Gsn
n(n+1)は偶数なので
GsG2sn=h(1)GsnGs(n+1)h(1)Gs(n1)Gsn
GsG2sn=Gs(n+1)GsnGsnGs(n1)
sは任意の自然数、G2sn=F2snなので
k=0nF2sk=1Gsk=0nGs(k+1)GskGskGs(k1))
k=0nF2sk=Gs(n+1)GsnGs1Gs0Gs=Gs(n+1)GsnGs

k=0nF2skの整除性

k=0nF2sk=Gs(n+1)GsnGs
についてGCD(Gs(n+1),Gsn)=Gsなので
k=0nF2sk=Gs(n+1)GsnGCD(Gs(n+1),Gsn)=LCM(Gs(n+1),Gsn)
ここでLCMは2項の最小公倍数を表す。
これよりs|tなる自然数s,tについて

k=0nF2sk=LCM(Gs(n+1),Gsn), k=0nF2tk=LCM(Gt(n+1),Gtn)
(係数2を外出ししているのでs,t2の倍数である必要はない。)
s|tGnの整除性によりGsn|Gtn , Gs(n+1)|Gt(n+1)であるので
LCM(Gt(n+1),Gtn)Gsn,Gs(n+1)の公倍数であることがわかる。
よって、最小公倍数の性質から
LCM(Gs(n+1),Gsn)|LCM(Gt(n+1),Gtn)
即ち
k=0nF2sk|k=0nF2tk 
が言えた。

投稿日:202389
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

TKSS
TKSS
45
5358

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. この記事の内容
  2. こいつはフィボナッチ数列ではない
  3. $G_n$の満たす漸化式
  4. $G_n$の性質(1)整除性
  5. $G_n$の性質(2)最大公約数
  6. $G_n$の和の計算
  7. $\sum_{k=0}^{n}F_{2sk}$の整除性