自己紹介/フィボナッチ数列について
はじめまして. りぼーすと申します.
今回は自己紹介と僕が好きなフィボナッチ数列について少し書いていきます.
Mathlogを書くのは初めてですので拙い点も多いとは思いますがぜひ最後まで読んでくれると嬉しいです.
自己紹介
情報はすべて2022年1月時点でのものです.
- 競技数学, 大学数学をしている高一
- 整数が好き
- 最近は幾何も好き
- 関数方程式も好き
- 組み合わせはできない
更新頻度は遅いと思いますがよろしくお願いします！
ここから本題(?)に入ります.
- 数2Bまでの基礎知識がある
- 集合, 写像についての記法, 用語が一通りわかる
フィボナッチ数列の定義
初めに定義です. よくあるやつですが, ここでは必要に応じて負の項も考えます.
数列$\{F_n\}^\infty_{n=-\infty}$ を$F_0=0,F_1=1,F_{n+2}=F_{n+1}+F_n$$(n\in\Z)$で定め, フィボナッチ数列と呼ぶ. この集合に登場する整数をフィボナッチ数と呼ぶ.
文脈によって誤解を招かない範囲で正のフィボナッチ数のことを単にフィボナッチ数と呼びます.
この$F_○$という記法, 下で定義する記号は今後ずっと用います.
- 正のフィボナッチ数全体の集合を$\fib$とあらわす
- フィボナッチ数全体の集合を$\Fib$とあらわす
ここからはその色々な性質を少しだけ探っていきます.
色々な公式
まず一般項です. 有名なやつです.
任意の$n\in\Z$に対し, $F_n=\dfrac1{\sqrt5}(\phi^n-\psi^n)$が成立する. ここで, $\phi=\dfrac{1+\sqrt5}2,\psi=\dfrac{1-\sqrt5}2$であり, これらは$x^2-x-1$の$2$解である.
証明は普通の三項間漸化式なので割愛します. 次に定理を二つほど.
任意の$n,m\in\Z$に対し$F_{n+m+1}=F_nF_m+F_{n+1}F_{m+1}$が成立する.
任意の$n,m\in\Z$に対し$F_{n+m}F_{n-m}=F_n^2-(-1)^{n+m}F_m^2$
定理の名前は一般的ではないです. 加法定理のほうはそこそこ知名度があるかもしれませんが, 乗法定理は中学生のころ某教室で発見されたものなので知っている人はほとんどいないのではないでしょうか(いたらDMください). 証明していきます.
帰納法で示す. $n=0$のとき明らか. $n=k$のとき任意の$m$に対して成り立っているとすると,
\begin{align*}
F_{k+1+m+1}&=F_kF_{m+1}+F_{k+1}F_{m+2}\\
&=F_kF_{m+1}+F_{k+1}F_m+F_{k+1}F_{m+1}\\
&=F_{k+1}F_m+F_{k+2}F_{m+1}\\
F_{k-1+m+1}&=F_kF_{m-1}+F_{k+1}F_m\\
&=F_kF_{m-1}+F_kF_m+F_{k-1}F_m\\
&=F_{k-1}F_m+F_kF_{m+1}\\
\end{align*}
となるのですべての整数に対して成立する.
$\phi\psi=-1$に留意してBinetの公式を用いると
\begin{align*}
F_{n+m}F_{n-m}&=\frac15(\phi^{n+m}-\psi^{n+m})(\phi^{n-m}-\psi^{n-m})\\
&=\frac15(\phi^{2n}+\psi^{2n}-\phi^{n+m}\psi^{n-m}-\phi^{n-m}\psi^{n+m})\\
&=\frac15(\phi^{2n}+\psi^{2n}-(-1)^n\phi^m\psi^{-m}-(-1)^n\phi^{-m}\psi^m)\\
&=\frac15(\phi^{2n}+\psi^{2n}-(-1)^{n-m}\phi^{2m}-(-1)^{n-m}\psi^{2m})\\
&=\frac15(\phi^{2n}+\psi^{2n}-(-1)^{n+m}\phi^{2m}-(-1)^{n+m}\psi^{2m})\\
F_n^2-(-1)^{n+m}F_m^2&=\frac15((\phi^{2n}+\psi^{2n}-2\phi^n\psi^n)-(-1)^{n+m}(\phi^{2m}+\psi^{2m}-2\phi^m\psi^m))\\
&=\frac15((\phi^{2n}+\psi^{2n}-2(-1)^n)-(-1)^{n+m}(\phi^{2m}+\psi^{2m}-2(-1)^m))\\
&=\frac15(\phi^{2n}+\psi^{2n}-(-1)^{n+m}\phi^{2m}-(-1)^{n+m}\psi^{2m})\\
\end{align*}
となるので示された.
$F_{-n}=-(-1)^nF_n$
乗法定理の$n$に$0$を代入することで, $F_mF_{-m}=F_0^2-(-1)^mF_m^2=-(-1)^mF_m^2$. $F_m\neq0$の場合両辺を$F_m$で割ることで示される. 一方, Binetの公式より$F_n=0\Leftrightarrow n=0$が分かるので, 題意は示された.
判定法について
次に, フィボナッチ数かどうかの判定法についてです. 判定法がわかれば, ある条件を満たすフィボナッチ数といったものも探しやすくなります.
フィボナッチ数$\Rightarrow○○$
全てのフィボナッチ数に共通する分かりやすい性質を見つけていきます.
任意の$n\in\Z_{>0}$に対してある$m\in\Z$が存在し, $5F_n^2+4(-1)^n=m^2$
乗法定理の$m$に$1$を代入すると
\begin{align*}
F_{n+1}F_{n-1}&=F_n^2-(-1)^{n+1}F_1^2\\
F_nF_{n-1}+F_{n-1}^2&=F_n^2+(-1)^{n}\\
F_{n-1}^2+F_nF_{n-1}-F_n^2-(-1)^{n}&=0
\end{align*}
今,$F_{n-1},F_n\in\Z$なので$F_{n-1}$についての判別式$5F_n^2+(-1)^n\cdot4$は平方数になり, 示された.
余談ですが$m$はリュカ数という数になります. 今回はリュカ数についてはあまり触れずに行こうと思います.
- フィボナッチ数$8$について, $5\times8^2+4=18^2$
- フィボナッチ数$1$について, $5\times1^2+4=3^2$, $5\times1^2-4=1^2$
(これは$1$が$2$回出てくることと関連していますね)
しかしこれだけわかってもあまり嬉しくないです. 逆も示したいのです. というわけで逆を示していきます. 逆の示し方はいくつかありますが, 次回以降を考えて若干回りくどい方法で示します.
前者関数, 後者関数
判別式について考えたので, 実際に上の二次方程式を解いてみます.
すると,
$$F_n=\frac{F_{n-1}\pm\sqrt{5F_{n-1}^2+4\cdot(-1)^{n-1}}}{2},F_{n-1}=\frac{-F_{n}\pm\sqrt{5F_{n}^2+4\cdot(-1)^n}}{2}$$
となります. 見た目がごついですが, これを用いて前者関数, 後者関数という関数を定義します.
集合$M$を$M=\{n\in\Z_{>0}|\;\exists m\in\Z \text{ s.t. } 5n^2+4=m^2 \text{ or }5n^2-4=m^2\}$で定める.
$M\rightarrow\Z_{>0},M\backslash\{1\}\rightarrow\Z_{>0}$への関数をそれぞれ
$$n\mapsto\frac{n+\sqrt{5n^2\pm4}}{2},n\mapsto\frac{-n+\sqrt{5n^2\pm4}}{2}$$
で定め, 全射となるよう終域を制限したものをそれぞれ$\suc$, $\pre$とする.
- 存在について
$M$の定義と偶奇の議論から定義式の$\pm$をうまく選べば整数値をとることが分かります. また, $\suc$については明らかに正の値を取り, $\pre$については$n\ge2$のとき$n\lt\sqrt{5n^2-4}\lt\sqrt{5n^2+4}$が成り立つことから存在が示せます. - 一意性について
$5n^2+4=m^2,5n^2-4=k^2$を満たす$m,k\in\Z$が存在するような$n\in\Z_{>0}$は$1$しかありませんので,それ以外については$\suc,\pre$は高々一意に定まります.$\suc(1)$については$\suc(1):=2$とします.
- $5\times3^2+4=7^2,5\times5^2-4=11^2$より$3,5\in M$. 実際は, 定理3より一般に$\fib\subset M$が成立します.
- $\pre(3)=\dfrac{-3+7}2=2, \suc(5)=\dfrac{5+11}2=8$のように前者関数, 後者関数はフィボナッチ数に対してはそれぞれ前後のフィボナッチ数を表します.(実際これは関数の作り方から明らかです)
赤字にあるような性質が見つかれば, 実際に逆関数になっていることを示したくなるのが人間というものです. 示していきましょう. といってもほとんど代入作業だけで書くのも読むのも面倒くさいので概略のみここでは書きます.
$\pre$と$\suc$はそれぞれ逆関数である. 特に, $\suc, \pre$の像はそれぞれ$M\backslash\{1\}, M$である.
$\begin{align*}
5\suc(n)^2\mp4
&=\frac{5(6n^2\pm4+2n\sqrt{5n^2\pm4})}{4}\mp4\\
&=\frac{30n^2\pm20+10n\sqrt{5n^2\pm4}}{4}\mp4\\
&=\frac{30n^2\pm4+10n\sqrt{5n^2\pm4}}{4}
\end{align*}$
$5n^2\pm4=m^2$を用いて変形すると
$$\frac{30n^2\pm4+10n\sqrt{5n^2\pm4}}{4}=\frac{25n^2+m^2+10nm}{4}=\left(\frac{m+5n}{2}\right)^2$$
偶奇に注意すれば括弧内は正整数である.よって$\suc(n)\in M$である.$\pre$についても同様にして示される. (ここまでで後半の主張は示された)
このことから$\suc(\pre(n)),\pre(\suc(n))$が定義でき,$1$のコーナーケースに注意すれば計算により$\suc$と$\pre$は互いに逆関数であることが分かる.
逆関数が存在するということは特に全単射です.
$○○\Rightarrow$フィボナッチ数
ここまでくればあと一息です. 一気に逆を示していきます.
$M\subset\fib$である.
$M\not\subset\fib$と仮定し, $M\backslash\fib$の元の中で最小のものを$k$とおく. $k\neq1$と補題4より$\pre(k)\in M$であり,$\pre$の単射性と$\pre(\fib\backslash\{1\})=\fib$であることから
$\pre(k)\in M\backslash\fib$である.しかし,$k>\pre(k)$なので$\cdots\star$これは$k$の最小性に反する.よって$M\subset\fib$.
$\star$の証明)
$\dfrac{-k+\sqrt{5k^2+4}}{2}>\dfrac{-k+\sqrt{5k^2-4}}{2}$なので$k>\dfrac{-k+\sqrt{5k^2+4}}{2}$を示せば十分. $k>0$に留意すると
$\begin{align*}
&k>\dfrac{-k+\sqrt{5k^2+4}}{2}\\
\Leftrightarrow&3k>\sqrt{5k^2+4}\\
\Leftrightarrow&9k^2>5k^2+4\\
\Leftrightarrow&k>1
\end{align*}$
今, $k$の定義より$k>1$なので示された.
というわけで$M=\fib$が示されました. めでたしめでたし.
問題
これを使って$1$問解いてみます.
$F_n=2^r$を満たす正整数$n$, 非負整数$r$の組を全て求めよ.
判定法より$5\cdot2^{2r}=m^2\pm4$なる$m\in\Z$が存在することと同値.
$5\cdot2^{2r}=m^2+4$の場合,$\bmod16$で考える.
$r\ge2$のとき, $5\cdot2^{2r}\equiv0$となり$m^2\equiv12$となるが,$\mod16$での平方剰余は$0, 1, 4, 9$のみなので不適.
$r=0, 1$で$r=0$のとき$m=1$, $r=1$のとき$m=4$となりいずれも適する.
このとき$2^{r}$の値はそれぞれ$1,2$になる.
$5\cdot2^{2r}=m^2-4$の場合, $5\cdot2^{2r}=(m+2)(m-2)$となる. $m+2$と$m-2$の最大公約数は$1$, $2$または$4$で, $m+2\equiv m-2\mod4$なので,
$\min\{v_{2}(m+2),v_{2}(m-2)\}=2$または$v_{2}(m+2)=v_{2}(m-2)=0,1$である. よって,
$r\ge2$のとき
$$m+2=5\cdot4,m-2=2^{2r-2}\cdots A, m+2=2^{2r-2},m-2=5\cdot4\cdots B$$
$$m+2=5\cdot2^{2r-2},m-2=4\cdots C, m+2=4,m-2=5\cdot2^{2r-2}\cdots D$$
$r=1$のとき
$$m+2=5\cdot2,m-2=2\cdots E, m+2=2,m-2=5\cdot2\cdots F$$
$r=0$のとき
$$m+2=5\cdot1,m-2=1\cdots G, m+2=1,m-2=5\cdot1\cdots H$$
のいずれかのパターンになる.
$A\cdots r=3$のとき$m=18, 2^{r}=8$となり満たされ,
$G\cdots r=0$であり$m=3, 2^{r}=1$となり満たされる. それ以外で満たすものがないことは容易に確認できる.
よって, $(n,r)=(1,0),(2,0),(3,1),(6,3)$.
おわりに
読みづらい点も多かったかと思いますが最後まで読んでいただきありがとうございます. 次回は(やる気があれば)前者関数, 後者関数についてさらに考察したことをまとめる予定です. 不備等ございましたらご指摘いただけると幸いです.
この記事を高評価した人
この記事に送られたバッジ
投稿者
