この記事の内容
kzaukzau様のこちらの記事
Fibonacci数の和の整除性についてのある予想(解決?)
について、
大変興味深かったためしばらく考えていたがある程度形になったので記事にしたい。
まず問題は以下の通りのものとなる。
フィボナッチ数の和の整除性
をn番目のフィボナッチ数とし、となる正の偶数に対して
証明自体は
引用した記事
ですでにつけられており、
本記事をご覧の方はぜひそちらも一読をお勧めする。
こいつはフィボナッチ数列ではない
結論を述べると、この問題を考えるに適切な数列はフィボナッチ数列ではない。
定理1ではに偶数の条件が課せられているので
和に現れる項はすべてフィボナッチ数列の偶数番目の項だが
奇数番目はではないとした方がうまくいく。
では奇数番目にいるのは何なのか。奇数番目のフィボナッチ数の代わりに
奇数番目のリュカ数が代わりにいる。
次のような数列を定義する。
漸化式の形から、偶数番目は偶数番目だけで定義され
奇数番目は奇数番目だけで定義されることがわかる。
また、漸化式の形はフィボナッチ数列、あるいはリュカ数列を定義する
有名な漸化式であるを2項ごとに
とった数列が満たす漸化式と同じ形となっている。
(ここの詳細は
こちらの弊記事
をご参照いただきたい)
はフィボナッチ数列の0項目と2項目に一致し、
はリュカ数列の1項目、3項目に一致しているので
この数列は偶数番目がフィボナッチ数列と
奇数番目がリュカ数列と一致していることがわかる。
以下、この数列の性質を見ることで元の定理を証明する。
の満たす漸化式
さて、を上のように定義しておいてなんだが、流石に5項間漸化式は面倒くさい。
もうちょっとまからんか、ということで
フィボナッチ数列とリュカ数列の相互関係から次のような関係が言える。
このとき
となり、定義1の2項目、3項目と一致し、また
から
をもとの式に代入すると
を得る。(を用いている)
がによらず成り立つので
となり定義2から
定義1が導ける。よって今後は定義2を用いる。
の性質(1)整除性
は以下の性質を持つ
偶数番目はフィボナッチ数列だし、リュカ数にしても奇数番目同士なら整除性はある。
偶奇が混ざってもなので割れるように出来ているのであるが
他でも使うあてがあるので、次の式の成立をもって整除性を示す。
補題3の証明
補題3の証明
定義2から
なので
定義2から定義1を得る計算の際に示した通り
なので
で成り立つと仮定する。このとき
を計算すると
となるのでとすれば
数学的帰納法より補題3が成り立つことがわかる
この補題から整除性は直ちに従う
定理2の証明
任意の自然数kについてを示す
についての数学的帰納法で示す。
のときあきらか
のとき成り立つと仮定すると
なので
よりででも成り立つ。
よって任意の自然数kについては示された。
の計算
定理2の証明では用いなかったが、あとで使うことになるため
補題3のが何者であるかを明らかにしておく。
の計算
この数列はいずれにも依存するがへの依存は漸化式からわかる通り
の部分に限られ、はの偶奇しか影響しないので
について考える必要があるのはその偶奇だけということがわかる。
ゆえ、について、特にが偶数の場合を、
が奇数の場合をと書くことにする。
が偶数の場合
なので漸化式は
となる。初項、2項目が違うだけでと同じ漸化式であることがわかった。
何項か計算すると
で
なので
とわかる。同様に
なのでとわかる。
概ねをひっくり返したような数列になっている。
が奇数の場合
なので漸化式は
続く2項は
についても
2項ごとの漸化式に変形するとやはり
が得られるので、
以上から
とまとめられることがわかる。
の性質(2)最大公約数
は以下の性質を持つ
フィボナッチ数でよく見るやつである。
これについても偶数番目はフィボナッチ数列だし、リュカ数にしても奇数番目同士なら成り立っている。
偶奇が混ざると整除性よりはおそらく若干面倒になる。
(で行けそうだけど、はで共通因数を持つので考えることがある)
こちらも他のついでがあるので、まず次の補題を示す。
係数のがややこしいことになっているが、要はの偶奇で決まるんだ、ぐらいのことしか言っていない。
証明の方法は数列にかえてについて考える。
補題3からの漸化式がわかる。
についての計算結果から
が偶数の時は係数になどを含まない線形漸化式で
一般リュカ数列になるので加法定理の計算は
一般リュカ数列のそれになる。
その場合の証明は
こちらの弊記事
参照。
以下ではが奇数の場合について進める。
このときの満たす漸化式は
とし、以下を示す。
(両辺にをかけると補題の形に戻る)
補題5の証明
補題5(の拡張加法定理)の証明
数学的帰納法で示す。
のとき
より正しい。
のとき
より正しい
で正しいと仮定する。このとき
を計算すると左辺は、右辺は
長くなるのででくくった係数だけ見ると
をくくりだすと
の係数の因子であるについて
を偶数とすると
を奇数とすると
よっての偶奇によらず
ゆえ
のでくくった係数を見ると
をくくりだすと
は先ほど同様に
の偶奇によらずとなることがわかるので
以上から
となりの時も成り立ち、任意の自然数で成り立つことが示せる。
準備が整ったので本題の定理4の証明に進む
定理4
定理4(の最大公約数)の証明
補題3と補題5より一般に自然数について
ゆえ
が成り立つ。
と書くことにするとき
ベズーの等式よりとなる整数が存在する。
全て正の数でよりのいずれかは非正。
適当に文字を置きなおしてとしてよい。
左辺はとなる。
右辺についてより
と書くことにすると
と表せるので、ベズーの等式より
またよりなので
よって
以上から
の和の計算
の和の計算のため補題5を利用する。
補題5でとすると
は偶数なので
は任意の自然数、なので
の整除性
についてなので
ここでは2項の最小公倍数を表す。
これよりなる自然数について
(係数を外出ししているのでがの倍数である必要はない。)
との整除性によりであるので
はの公倍数であることがわかる。
よって、最小公倍数の性質から
即ち
が言えた。