17

フィボナッチの母関数っぽいのを用いた合同式

892
2

はじめまして。
みなともと申します。
初めて記事を書きますので慣れないことが多いですが是非最後まで読んで貰えると嬉しいです。
初回はフィボナッチ数列に関する合同式です!

綺麗な合同式

合同式
2n(Fn1+Fn+1)1(mod5)

ここで使っているフィボナッチ数は
F0=F1=1,Fn+2=Fn+1+Fn(n0)という風に、1ずらして定義します
(そっちの方が結果綺麗)

S=k=0nFkxkとすると
S=F0+F1x+F2x2++Fn2xn2+Fn1xn1+Fnxn
xS=F0x+F1x2+F2x3++Fn2xn1+Fn1xn+Fnxn+1
x2S=F0x2+F1x3+F2x4++Fn2xn+Fn1xn+1+Fnxn+2
を用いて等比数列の和の公式と同様にしてSを求めることができます。
①-②-③を考えます。するとx²~xⁿまでは前述したフィボナッチ数列の漸化式より係数が0になります。すると、
(1xx2)S=(F0+F1xF0xFnxn+1Fn1xn+1Fnxn+2)
整理して
(1xx2)S=1Fnxn+1Fn1xn+1Fnxn+2
 =1(Fn+Fn1)xn+1Fnxn+2
 =1Fn+1xn+1Fnxn+2
 =1xn+1(Fn+1+Fnx)
   S=xn+1(Fnx+Fn+1)1x2+x1

これでSを得られました!
ここで、x=2を代入してみましょう。

S=2n+1(2Fn+Fn+1)15
おっ?近づいて来ましたね!!
Fn+2=Fn+1+Fn
ですから、巧みに変形して
S=2n+1(2Fn+(Fn+2Fn))15
=2n+1(Fn+Fn+2)15
あとはもう簡単!!
Sはxが整数だと、整数値になるので
得られた式の分子は5の倍数。つまり
2n+1(Fn+Fn+2)1(mod5)
nがズレることで影響はでないので
nを1だけずらしてやると……
2n(Fn1+Fn+1)1(mod5)
うおおおおぉぉぉ!!!
出た!出た!
ふぅ…()

さいごに

お疲れ様でした!!
いやぁ大変でしたね。
数式を入力するのはなかなか手間のかかるもので、3時間ぐらい格闘しましたw これからも色々書いて練習して行きますので、次も是非読んでください!!では!

投稿日:202354
OptHub AI Competition

この記事を高評価した人

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

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

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

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

投稿者

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中