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

帰納法で示す. $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*}
となるので示された.

乗法定理の$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$が分かるので, 題意は示された.

乗法定理の$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$は平方数になり, 示された.

$\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$は互いに逆関数であることが分かる.

$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$なので示された.