Fibonacci数

1：敷き詰め方の数を $c_n$ とし、$c_0=1$（空の敷き詰め 1 通り）とおく。$c_1=1$ である。$n\geq2$ のとき、右端の列が縦置きのドミノ 1 枚で覆われる敷き詰めは、残りの $2\times(n-1)$ の敷き詰めと一対一に対応し、$c_{n-1}$ 通りある。そうでなければ右端の上下のマスは横置きのドミノで覆われ、2 枚の横置きのドミノが右端の 2 列をちょうど覆うので、残りの $2\times(n-2)$ の敷き詰めと一対一に対応し $c_{n-2}$ 通りある。よって $c_n=c_{n-1}+c_{n-2}$ であり、$c_0=1=F_1$、$c_1=1=F_2$ と合わせて、帰納法により $c_n=F_{n+1}$ である。
2：そのような列の個数を $a_n$ とし、$a_0=1$（空の列）とおく。$a_1=2$ である。$n\geq2$ のとき、末尾が $0$ の列は長さ $n-1$ の条件を満たす列の末尾に $0$ を付けたものと一対一に対応し、末尾が $1$ の列は直前が $0$ でなければならないので、長さ $n-2$ の条件を満たす列の末尾に $01$ を付けたものと一対一に対応する。よって $a_n=a_{n-1}+a_{n-2}$ であり、$a_0=1=F_2$、$a_1=2=F_3$ と合わせて $a_n=F_{n+2}$ である。

右辺を $G_n$ とおく。$G_0=0$、$G_1=(\varphi-\psi)/\sqrt5=1$ である。$\varphi^2=\varphi+1$ の両辺に $\varphi^n$ を掛けると $\varphi^{n+2}=\varphi^{n+1}+\varphi^n$ であり、$\psi$ についても同様なので、
$$ G_{n+2}=\frac{\varphi^{n+2}-\psi^{n+2}}{\sqrt5}=\frac{(\varphi^{n+1}-\psi^{n+1})+(\varphi^n-\psi^n)}{\sqrt5}=G_{n+1}+G_n $$
である。$(G_n)$ と $(F_n)$ は同じ初期値と同じ漸化式をもつので、$n$ に関する数学的帰納法（$n$ と $n+1$ で一致すれば $n+2$ でも一致する）によりすべての $n$ で一致する。

thm-fib-binet より $\bigl|F_n-\varphi^n/\sqrt5\bigr|=|\psi|^n/\sqrt5\leq1/\sqrt5<1/2$ である（$|\psi|<1$、$\sqrt5>2$）。距離が $1/2$ 未満の整数はただ一つなので、$F_n$ が最も近い整数である。

$n=1$ では $\varphi^{-1}<1=F_1=\varphi^0$、$n=2$ では $\varphi^0=1=F_2<\varphi$ である。$n\geq1$ で $n$ と $n+1$ について成り立つとすると、$\varphi^2=\varphi+1$ から
$$ F_{n+2}=F_{n+1}+F_n\leq\varphi^n+\varphi^{n-1}=\varphi^{n-1}(\varphi+1)=\varphi^{n+1} $$
であり、同様に $F_{n+2}\geq\varphi^{n-1}+\varphi^{n-2}=\varphi^{n}$ である。

$n\geq1$ で $F_n\geq1$ である。thm-fib-binet の分子・分母を $\varphi^n$ で割り、$r=\psi/\varphi$ とおくと
$$ \frac{F_{n+1}}{F_n}=\frac{\varphi^{n+1}-\psi^{n+1}}{\varphi^n-\psi^n}=\frac{\varphi-\psi r^n}{1-r^n} $$
である。$|r|=|\psi|/\varphi<1$ なので $r^n\to0$ であり（数列の極限）、右辺は $\varphi$ に収束する。

$n=1$ では $F_2=F_1=1$、$F_0=0$ なので正しい。$n$ で正しいとすると
$$ Q^{n+1}=Q^nQ=\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}\begin{pmatrix}1&1\\1&0\end{pmatrix}=\begin{pmatrix}F_{n+1}+F_n&F_{n+1}\\F_n+F_{n-1}&F_n\end{pmatrix}=\begin{pmatrix}F_{n+2}&F_{n+1}\\F_{n+1}&F_n\end{pmatrix} $$
であり、$n+1$ でも正しい。

1：$Q^{m+n}=Q^mQ^n$ の右上の成分を比べる。左辺は $F_{m+n}$、右辺は $Q^m$ の 1 行目 $(F_{m+1},F_m)$ と $Q^n$ の 2 列目 $(F_n,F_{n-1})$ の積の和 $F_{m+1}F_n+F_mF_{n-1}$ である。
2：行列式は積を保つので $\det(Q^n)=(\det Q)^n=(-1)^n$ である。一方 prop-fib-matrix より $\det(Q^n)=F_{n+1}F_{n-1}-F_n^2$ である。
3：$n=0$ では $F_0=0$、$F_1=1$ なので $\gcd(F_0,F_1)=1$ である。$n\geq1$ なら、$F_n$ と $F_{n+1}$ の公約数 $d>0$ は 2 の左辺 $F_{n+1}F_{n-1}-F_n^2$ を割り切るので $d\mid1$、すなわち $d=1$ である。

$n=0$ では $0=F_2-1$ である。$n$ で成り立つとすると、$F_0+\cdots+F_{n+1}=F_{n+2}-1+F_{n+1}=F_{n+3}-1$ である。

$m+n$ に関する強い帰納法で示す。$m=0$ なら左辺は $\gcd(0,F_n)=F_n$、右辺は $F_{\gcd(0,n)}=F_n$ である。$n=0$ も同様である。$m=n$ なら両辺とも $F_m$ である。$m,n\geq1$、$m\neq n$ のときは対称性から $m>n$ としてよい。cor-fib-identities の 1 を $m-n\geq1$ と $n\geq1$ に使うと
$$ F_m=F_{(m-n)+n}=F_{m-n+1}F_n+F_{m-n}F_{n-1} $$
である。$F_n$ の倍数を除いても最大公約数は変わらないので $\gcd(F_m,F_n)=\gcd(F_{m-n}F_{n-1},F_n)$ であり、$F_{n-1}$ と $F_n$ は互いに素（cor-fib-identities の 3）なので、これは $\gcd(F_{m-n},F_n)$ に等しい。$(m-n)+n< m+n$ なので帰納法の仮定から $\gcd(F_{m-n},F_n)=F_{\gcd(m-n,n)}$ であり、$\gcd(m-n,n)=\gcd(m,n)$ なので主張を得る。

$m\mid n$ なら $\gcd(m,n)=m$ なので、thm-fib-gcd より $\gcd(F_m,F_n)=F_m$、すなわち $F_m\mid F_n$ である。逆に $m\geq3$ で $F_m\mid F_n$ とすると $F_{\gcd(m,n)}=\gcd(F_m,F_n)=F_m$ である。$n=0$ なら $m\mid n$ は明らかなので $n\geq1$ とし、$d=\gcd(m,n)$ とおくと $1\leq d\leq m$ である。$F_m\geq F_3=2$ なので $F_d\geq2$、したがって $d\geq3$ である。添字 $2$ 以上で $F$ は狭義単調増加なので、$F_d=F_m$ と $d\leq m$ から $d=m$、すなわち $m\mid n$ である。

$n\geq5$ が合成数だとすると、$n=ab$、$2\leq a\leq b< n$ と書ける。$b=2$ なら $a=2$、$n=4$ となって $n\geq5$ に反するので $b\geq3$ である。cor-fib-divisibility より $F_b\mid F_n$ であり、$3\leq b< n$ から $2\leq F_b< F_n$ である。よって $F_n$ は $1$ と自身以外の約数 $F_b$ をもち、素数でない。

$r=1$ では $k_1\geq2$ から $F_{k_1}< F_{k_1+1}$ である。$r\geq2$ とし、$r-1$ 項で正しいとする。$k_2,\dots,k_r$ に帰納法の仮定を使うと $F_{k_2}+\cdots+F_{k_r}< F_{k_2+1}\leq F_{k_1-1}$ である（$k_2+1\leq k_1-1$ で、$F$ は添字 $1$ 以上で単調非減少）。よって和は $F_{k_1}+F_{k_1-1}=F_{k_1+1}$ より小さい。

存在：$N$ に関する強い帰納法で示す。$F_2=1\leq N$ であり $F_n\to\infty$ なので、$F_k\leq N$ となる最大の $k\geq2$ がある。$N=F_k$ ならそれが表示である。そうでなければ $N'=N-F_k$ は $0< N'< F_{k+1}-F_k=F_{k-1}$ を満たす（$k$ の最大性から $N< F_{k+1}$）。$N'< N$ なので帰納法の仮定から $N'$ は表示をもち、その最大の添字 $j$ は $F_j\leq N'< F_{k-1}$ を満たす。$F$ は単調非減少なので $j< k-1$、すなわち $k-j\geq2$ であり、$N'$ の表示に $F_k$ を加えれば $N$ の表示が得られる。
一意性：同じ $N$ の表示が 2 つあり、使う添字の集合 $S,T$ が異なるとする。共通の添字を両方から除いた集合 $S',T'$ は交わらず、対応する和は等しく、どちらも隣り合う添字を含まない。一方が空なら和は $0$ なので他方も空となり $S=T$ に反するので、どちらも空でない。$S'$ の最大元を $s$、$T'$ の最大元を $t$ とすると $s\neq t$ であり、$s>t$ としてよい。lem-fib-zeckendorf-bound より $T'$ の和は $F_{t+1}$ より小さく、$t+1\leq s$ から $F_{t+1}\leq F_s$ であり、$F_s$ は $S'$ の和以下である。これは 2 つの和が等しいことに反する。