14

自己紹介/フィボナッチ数列について

1151
0

はじめまして. りぼーすと申します.
今回は自己紹介と僕が好きなフィボナッチ数列について少し書いていきます.

Mathlogを書くのは初めてですので拙い点も多いとは思いますがぜひ最後まで読んでくれると嬉しいです.

自己紹介

情報はすべて2022年1月時点でのものです.

  • 競技数学, 大学数学をしている高一
  • 整数が好き
  • 最近は幾何も好き
  • 関数方程式も好き
  • 組み合わせはできない

更新頻度は遅いと思いますがよろしくお願いします!
ここから本題(?)に入ります.


前提知識
  • 数2Bまでの基礎知識がある
  • 集合, 写像についての記法, 用語が一通りわかる

フィボナッチ数列の定義

初めに定義です. よくあるやつですが, ここでは必要に応じて負の項も考えます.

フィボナッチ数列

数列{Fn}n=F0=0,F1=1,Fn+2=Fn+1+Fn(nZ)で定め, フィボナッチ数列と呼ぶ. この集合に登場する整数をフィボナッチ数と呼ぶ.

文脈によって誤解を招かない範囲で正のフィボナッチ数のことを単にフィボナッチ数と呼びます.
このFという記法, 下で定義する記号は今後ずっと用います.

フィボナッチ数の集合について
  • 正のフィボナッチ数全体の集合をFとあらわす
  • フィボナッチ数全体の集合をFとあらわす

ここからはその色々な性質を少しだけ探っていきます.

色々な公式

まず一般項です. 有名なやつです.

Binetの公式

任意のnZに対し, Fn=15(ϕnψn)が成立する. ここで, ϕ=1+52,ψ=152であり, これらはx2x12解である.

証明は普通の三項間漸化式なので割愛します. 次に定理を二つほど.

加法定理

任意のn,mZに対しFn+m+1=FnFm+Fn+1Fm+1が成立する.

乗法定理

任意のn,mZに対しFn+mFnm=Fn2(1)n+mFm2

定理の名前は一般的ではないです. 加法定理のほうはそこそこ知名度があるかもしれませんが, 乗法定理は中学生のころ某教室で発見されたものなので知っている人はほとんどいないのではないでしょうか(いたらDMください). 証明していきます.

加法定理

帰納法で示す. n=0のとき明らか. n=kのとき任意のmに対して成り立っているとすると,
Fk+1+m+1=FkFm+1+Fk+1Fm+2=FkFm+1+Fk+1Fm+Fk+1Fm+1=Fk+1Fm+Fk+2Fm+1Fk1+m+1=FkFm1+Fk+1Fm=FkFm1+FkFm+Fk1Fm=Fk1Fm+FkFm+1
となるのですべての整数に対して成立する.

乗法定理

ϕψ=1に留意してBinetの公式を用いると
Fn+mFnm=15(ϕn+mψn+m)(ϕnmψnm)=15(ϕ2n+ψ2nϕn+mψnmϕnmψn+m)=15(ϕ2n+ψ2n(1)nϕmψm(1)nϕmψm)=15(ϕ2n+ψ2n(1)nmϕ2m(1)nmψ2m)=15(ϕ2n+ψ2n(1)n+mϕ2m(1)n+mψ2m)Fn2(1)n+mFm2=15((ϕ2n+ψ2n2ϕnψn)(1)n+m(ϕ2m+ψ2m2ϕmψm))=15((ϕ2n+ψ2n2(1)n)(1)n+m(ϕ2m+ψ2m2(1)m))=15(ϕ2n+ψ2n(1)n+mϕ2m(1)n+mψ2m)
となるので示された.

Fn=(1)nFn

乗法定理のn0を代入することで, FmFm=F02(1)mFm2=(1)mFm2. Fm0の場合両辺をFmで割ることで示される. 一方, Binetの公式よりFn=0n=0が分かるので, 題意は示された.

判定法について

次に, フィボナッチ数かどうかの判定法についてです. 判定法がわかれば, ある条件を満たすフィボナッチ数といったものも探しやすくなります.

フィボナッチ数

全てのフィボナッチ数に共通する分かりやすい性質を見つけていきます.

判定法1

任意のnZ>0に対してあるmZが存在し, 5Fn2+4(1)n=m2

乗法定理のm1を代入すると
Fn+1Fn1=Fn2(1)n+1F12FnFn1+Fn12=Fn2+(1)nFn12+FnFn1Fn2(1)n=0
今,Fn1,FnZなのでFn1についての判別式5Fn2+(1)n4は平方数になり, 示された.

余談ですがmはリュカ数という数になります. 今回はリュカ数についてはあまり触れずに行こうと思います.

  • フィボナッチ数8について, 5×82+4=182
  • フィボナッチ数1について, 5×12+4=32, 5×124=12
    (これは12回出てくることと関連していますね)

しかしこれだけわかってもあまり嬉しくないです. 逆も示したいのです. というわけで逆を示していきます. 逆の示し方はいくつかありますが, 次回以降を考えて若干回りくどい方法で示します.

前者関数, 後者関数

判別式について考えたので, 実際に上の二次方程式を解いてみます.
すると,
Fn=Fn1±5Fn12+4(1)n12,Fn1=Fn±5Fn2+4(1)n2
となります. 見た目がごついですが, これを用いて前者関数, 後者関数という関数を定義します.

前者関数, 後者関数

集合MM={nZ>0|mZ s.t. 5n2+4=m2 or 5n24=m2}で定める.
MZ>0,M{1}Z>0への関数をそれぞれ
nn+5n2±42,nn+5n2±42
で定め, 全射となるよう終域を制限したものをそれぞれsuc, preとする.

前者関数, 後者関数のwell-defined性について
  • 存在について
    Mの定義と偶奇の議論から定義式の±をうまく選べば整数値をとることが分かります. また, sucについては明らかに正の値を取り, preについてはn2のときn<5n24<5n2+4が成り立つことから存在が示せます.
  • 一意性について
    5n2+4=m2,5n24=k2を満たすm,kZが存在するようなnZ>01しかありませんので,それ以外についてはsuc,preは高々一意に定まります.suc(1)についてはsuc(1):=2とします.
  • 5×32+4=72,5×524=112より3,5M. 実際は, 定理3より一般にFMが成立します.
  • pre(3)=3+72=2,suc(5)=5+112=8のように前者関数, 後者関数はフィボナッチ数に対してはそれぞれ前後のフィボナッチ数を表します.(実際これは関数の作り方から明らかです)

赤字にあるような性質が見つかれば, 実際に逆関数になっていることを示したくなるのが人間というものです. 示していきましょう. といってもほとんど代入作業だけで書くのも読むのも面倒くさいので概略のみここでは書きます.

presucはそれぞれ逆関数である. 特に, suc,preの像はそれぞれM{1},Mである.

概略

5suc(n)24=5(6n2±4+2n5n2±4)44=30n2±20+10n5n2±444=30n2±4+10n5n2±44
5n2±4=m2を用いて変形すると
30n2±4+10n5n2±44=25n2+m2+10nm4=(m+5n2)2
偶奇に注意すれば括弧内は正整数である.よってsuc(n)Mである.preについても同様にして示される. (ここまでで後半の主張は示された)
このことからsuc(pre(n)),pre(suc(n))が定義でき,1のコーナーケースに注意すれば計算によりsucpreは互いに逆関数であることが分かる.

逆関数が存在するということは特に全単射です.

フィボナッチ数

ここまでくればあと一息です. 一気に逆を示していきます.

判定法2

MFである.

MFと仮定し, MFの元の中で最小のものをkとおく. k1と補題4よりpre(k)Mであり,preの単射性とpre(F{1})=Fであることから
pre(k)MFである.しかし,k>pre(k)なのでこれはkの最小性に反する.よってMF.

の証明)
k+5k2+42>k+5k242なのでk>k+5k2+42を示せば十分. k>0に留意すると
k>k+5k2+423k>5k2+49k2>5k2+4k>1
今, kの定義よりk>1なので示された.

というわけでM=Fが示されました. めでたしめでたし.

問題

これを使って1問解いてみます.

Fn=2rを満たす正整数n, 非負整数rの組を全て求めよ.

判定法より522r=m2±4なるmZが存在することと同値.

522r=m2+4の場合,mod16で考える.
r2のとき, 522r0となりm212となるが,mod16での平方剰余は0,1,4,9のみなので不適.
r=0,1r=0のときm=1, r=1のときm=4となりいずれも適する.
このとき2rの値はそれぞれ1,2になる.

522r=m24の場合, 522r=(m+2)(m2)となる. m+2m2の最大公約数は1, 2または4で, m+2m2mod4なので,
min{v2(m+2),v2(m2)}=2またはv2(m+2)=v2(m2)=0,1である. よって,
r2のとき
m+2=54,m2=22r2A,m+2=22r2,m2=54B
m+2=522r2,m2=4C,m+2=4,m2=522r2D
r=1のとき
m+2=52,m2=2E,m+2=2,m2=52F
r=0のとき
m+2=51,m2=1G,m+2=1,m2=51H
のいずれかのパターンになる.
Ar=3のときm=18,2r=8となり満たされ,
Gr=0でありm=3,2r=1となり満たされる. それ以外で満たすものがないことは容易に確認できる.
よって, (n,r)=(1,0),(2,0),(3,1),(6,3).

おわりに

読みづらい点も多かったかと思いますが最後まで読んでいただきありがとうございます. 次回は(やる気があれば)前者関数, 後者関数についてさらに考察したことをまとめる予定です. 不備等ございましたらご指摘いただけると幸いです.

投稿日:2022131
OptHub AI Competition

この記事を高評価した人

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

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

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

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

投稿者

りぼーす
りぼーす
139
29758

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 自己紹介
  2. フィボナッチ数列の定義
  3. 色々な公式
  4. 判定法について
  5. 問題
  6. おわりに