\[
\boldsymbol{x}_n=
\left[
\begin{array}{c}
F_{n+1} \\
F_n
\end{array}
\right], \qquad A =
\left[
\begin{array}{cc}
1 & 1 \\
1 & 0
\end{array}
\right]
\]
とおくと，Fibonacci 数列の漸化式から
\[
\boldsymbol{x}_{n+1}=
\left[
\begin{array}{c}
F_{n+2} \\
F_{n+1}
\end{array}
\right]
=
\left[
\begin{array}{c}
F_{n+1}+F_n \\
F_{n+1}
\end{array}
\right]
=
\left[
\begin{array}{cc}
1 & 1 \\
1 & 0
\end{array}
\right]
\left[
\begin{array}{c}
F_{n+1} \\
F_{n}
\end{array}
\right]
=
A\boldsymbol{x}_n
\]
が成り立つから，帰納的に $\boldsymbol{x}_n=A^{n}\boldsymbol{x}_0$ を得る．また
\[
A =
\left[
\begin{array}{cc}
1 & 1 \\
1 & 0
\end{array}
\right]=
[\boldsymbol{x}_1 ~~ \boldsymbol{x}_0]
\]
であるから

\[
\left[
\begin{array}{cc}
F_{n+1} & F_n \\
F_n & F_{n-1}
\end{array}
\right]
=
[\boldsymbol{x}_n ~~ \boldsymbol{x}_{n-1}]
=
A^{n-1}[\boldsymbol{x}_1 ~~ \boldsymbol{x}_0]
=A^n
=
\left[
\begin{array}{cc}
1 & 1 \\
1 & 0
\end{array}
\right]^n
\]

が従う．

$2$ 次方程式 $x^2-x-1=0$ の２つの解を $\alpha, \, \beta \quad (\alpha > \beta)$ とする．
解と係数の関係より，$\alpha + \beta = 1, \quad \alpha \beta = -1$ に注意すれば，漸化式より
\[
\begin{align*}
F_{n+2}-\alpha F_{n+1}
&=(1-\alpha)F_{n+1}+F_n=\beta F_{n+1}-\alpha\beta F_n=\beta(F_{n+1}-\alpha F_n), \\
F_{n+2}-\beta F_{n+1}
&=(1-\beta)F_{n+1}+F_n=\alpha F_{n+1}-\alpha\beta F_n=\alpha(F_{n+1}-\beta F_n) \\
\end{align*}
\]
が成り立つ．$a_n = F_{n+1}-\alpha F_n$ とおけば，第１式は
\[
a_{n+1} = \beta a_n, \quad a_1 = F_{2}-\alpha F_1 = 1-\alpha = \beta
\]
となり，数列 $\{a_n\}$ は初項，公比が $\beta$ の等比数列と判るから
\[
F_{n+1}-\alpha F_n = a_n = \beta^n
\]
を得る．$b_n = F_{n+1}-\beta F_n$ とおけば，第２式から同様の手順で
\[
F_{n+1}-\beta F_n = b_n = \alpha^n
\]
を得る．それぞれの結果の差をとって整理すれば
\[
F_n = \frac{\alpha^n-\beta^n}{\alpha-\beta}=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right\}
\]
が成り立つ（$\alpha-\beta=\sqrt{5}$ は計算した）．また，$\phi$ の定義より $\alpha=\phi$ であるから
\[
F_n = \frac{\alpha^n-\beta^n}{\alpha-\beta} = \frac{\phi^n-(1-\phi)^n}{\sqrt{5}}=\frac{\phi^n-(-\phi)^{-n}}{\sqrt{5}}
\]
が従う．

・ $2$ 次方程式 $x^2-x-1=0$ の２つの解を $\alpha, \, \beta \quad (\alpha > \beta)$ とする．

・ $2$ 次の単位行列を $E$ とすると，いま
\[
A^2=
\left[
\begin{array}{cc}
2 & 1 \\
1 & 0
\end{array}
\right]
=
\left[
\begin{array}{cc}
1 & 1 \\
1 & 0
\end{array}
\right]
+
\left[
\begin{array}{cc}
1 & 0 \\
0 & 1
\end{array}
\right]
=A+E
\]
であるから，$A^2-A-E=0$ が成り立つ（これは Cayley-Hamilton の定理から導いてもよい）．

・ ここで，整式 $x^n$ を $2$ 次式 $x^2-x-1=0$ で割った商を $Q(x)$ とすると，余りは $1$ 次式であるから $p_nx+q_n$ とおくことができて

\[
x^n = (x^2-x-1)Q(x)+p_nx+q_n \tag{$\diamondsuit$}
\]

が成り立つ．$x=\alpha, \, \beta$ を代入すれば
\[
\alpha^n=p_n\alpha+q_n, \quad \beta^n=p_n\beta+q_n
\]
であるから
\[
p_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}
\]
を得る．

・ 式 $(\diamondsuit)$ の両辺の行列 $A$ における値を考えれば
\[
A^n=p_nA+q_nE=
\left[
\begin{array}{cc}
p_n+q_n & p_n \\
p_n & q_n
\end{array}
\right]
\]
である．命題 1.3 より，上式の両辺の $(1,2)$ 成分を比較して
\[
F_n = p_n = \frac{\alpha^n-\beta^n}{\alpha-\beta}=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right\}
\]
が成り立つ（$\alpha-\beta=\sqrt{5}$ は計算した）．また，$\phi$ の定義より $\alpha=\phi$ であるから
\[
F_n = \frac{\alpha^n-\beta^n}{\alpha-\beta} = \frac{\phi^n-(1-\phi)^n}{\sqrt{5}}=\frac{\phi^n-(-\phi)^{-n}}{\sqrt{5}}
\]
が従う．

数学的帰納法で説明する．

$n=1$ のとき，$1$ 段の階段を上がる方法は「$1$ 歩で $1$ 段を上がる」の $1$ 通り．
$n=2$ のとき，$2$ 段の階段を上がる方法は「$1$ 歩で $2$ 段を上がる」か「$2$ 歩で $1$ 段ずつ上がる」かの $2$ 通り．
これはそれぞれ $F_2, \, F_3$ の値に等しい．

$n=k, \, k+1$ のときに正しいと仮定する．すなわち，$k$ 段の階段を上がる方法は $F_{k+1}$ 通り，$(k+1)$ 段の階段を上がる方法は $F_{k+2}$ 通りであると仮定する．

$n=k+2$ のとき，$(k+2)$ 段の階段を上がることを考える．最初の $1$ 歩で $1$ 段だけ上がるとき，残る $(k+1)$ 段の上がり方は，仮定より $F_{k+2}$ 通りである．最初の $1$ 歩で $2$ 段上がるとき，残る $k$ 段の上がり方は，仮定より $F_{k+1}$ 通りである．最初の上がり方はこの $2$ 通りしかないから，$(k+2)$ 段の上がり方は
\[
F_{k+2} + F_{k+1} = F_{k+3}
\]
通りである．ゆえに $n=k+2$ のときも正しいことが示されたから，数学的帰納法によって，すべての非負整数 $n$ について題意は成り立つ．

Fibonacci 数列の漸化式より

\[
F_{n+2}F_n=F_{n+1}F_n+F_n^2
\]
が成り立つ．同様に漸化式から得られる関係式 $F_n = F_{n+1}-F_{n-1}$ を右辺第１項の $F_n$ に代入すると
\[
F_{n+2}F_n=F_{n+1}(F_{n+1}-F_{n-1})+F_n^2=F_{n+1}^2-F_{n+1}F_{n-1}+F_n^2
\]
であるから，$a_n=F_{n+1}F_{n-1}-F_n^2$ とおくと
\[
a_{n+1}=F_{n+2}F_{n}-F_{n+1}^2=-(F_{n+1}F_{n-1}-F_n^2)=-a_n, \quad a_1=F_{2}F_{0}-F_1^2=-1
\]
が成り立つ．数列 $\{a_n\}$ は初項 $-1$，公比 $-1$ の等比数列であって
\[
F_{n+1}F_{n-1}-F_n^2 = a_n = (-1)^{n}
\]
を得る．

\[
\textrm{det}\,(A)=
\textrm{det}\,(
\left[
\begin{array}{cc}
1 & 1 \\
1 & 0
\end{array}
\right]
) = -1
\]
であるから
\[
\begin{align*}
F_{n+1}F_{n-1}-F_n^2
&=
\textrm{det}\,(
\left[
\begin{array}{cc}
F_{n+1} & F_n \\
F_n & F_{n-1}
\end{array}
\right]
)\\
&=
\textrm{det}\,(A^n)=\textrm{det}\,(A)^n=(-1)^{n}
\end{align*}
\]
を得る．

$(m+n-1)$ 段の階段の上がり方は $F_{m+n}$ 通りであり，この上がり方は $m$ 段目を踏む場合と踏まない場合に分けられる．

・$m$ 段目を踏む場合，$m$ 段目までの上がり方が $F_{m+1}$ 通りあり，残る $(n-1)$ 段の上がり方が $F_n$ 通りあるから，組み合わせは $F_{m+1}F_n$ 通りである．

・$m$ 段目を踏まない場合，$(m-1)$ 段目までの上がり方が $F_m$ 通りあり，$m$ 段目を飛ばして $(m+1)$ 段目まで上がる方法が $1$ 通り，残る $(n-2)$ 段の上がり方が $F_{n-1}$ 通りあるから，組み合わせは $F_{m}F_{n-1}$ 通りである．

・したがって，$(m+n-1)$ 段の上がり方は $F_{m+1}F_n+F_{m}F_{n-1}$ 通りであるから，題意は示された．

\[
\begin{align*}
F_{m+n}
&= F_{m+n-1}+F_{m+n-2} \\
&= F_{m+n-2}F_1+F_{m+n-1}F_2 \\
&= F_{m+n-2}(F_3-F_2)+F_{m+n-3}F_2 \\
&= (F_{m+n-1}-F_{m+n-2})F_2+F_{m+n-2}F_3 \\
&= F_{m+n-3}F_2+F_{m+n-2}F_3
\end{align*}
\]

が成り立つ．２つ目，５つ目の等号の部分

\[
F_{m+n-2}F_1+F_{m+n-1}F_2 = F_{m+n-3}F_2+F_{m+n-2}F_3
\]

の添え字の変化に着目して，同様の式変形を繰り返すと

\[
\begin{align*}
F_{m+n}
&= F_{m+n-2}F_1+F_{m+n-1}F_2 \\
&= F_{m+n-3}F_2+F_{m+n-2}F_3 \\
&= F_{m+n-4}F_3+F_{m+n-3}F_4 \\
& \qquad \qquad \qquad \, \vdots \\
&= F_{n-1}F_{m}+F_{n}F_{m+1}
\end{align*}
\]

を得る．

命題 1.3 より
\[
\begin{align*}
\left[
\begin{array}{cc}
F_{m+n+1} & F_{m+n} \\
F_{m+n} & F_{m+n-1}
\end{array}
\right]
&=A^{m+n}\\
&=A^mA^n\\
&=
\left[
\begin{array}{cc}
F_{m+1} & F_{m} \\
F_{m} & F_{m-1}
\end{array}
\right]
\left[
\begin{array}{cc}
F_{n+1} & F_{n} \\
F_{n} & F_{n-1}
\end{array}
\right]
\\
&=\left[
\begin{array}{cc}
F_{m+1}F_{n+1}+F_{m}F_n & F_{m+1}F_n+F_mF_{n-1} \\
F_{m}F_{n+1}+F_{m-1}F_{n} & F_{m}F_{n}+F_{m-1}F_{n-1}
\end{array}
\right]
\end{align*}
\]

であるから，各成分を比較すれば所望の結果が得られる．

1. $\quad$ 命題 1.7 において $m=n$ とすれば
\[
\begin{align*}
F_{2n}
&= F_{n+n} \\
&= F_{n+1}F_n+F_{n}F_{n-1} \\
&= F_{n+1}(F_{n+1}-F_{n-1})+(F_{n+1}-F_{n-1})F_{n-1} \\
&= F_{n+1}^2-F_{n-1}^2
\end{align*}
\]
を得る．ここで，３つ目の等号では $F_n = F_{n+1}-F_{n-1}$ を用いた．

2. $\quad$ 命題 1.7 において $n$ を $n+1$ に，$m$ を $n$ に対応させれば
\[
F_{2n+1} = F_{n+(n+1)} = F_{n+1}F_{n+1}+F_nF_n = F_{n+1}^2+F_{n}^2
\]
を得る．

3. $\quad$ 命題 1.7 および 系 1.8 の 1., 2. を用いて
\[
\begin{align*}
F_{3n}
&= F_{2n+n} \\
&= F_{2n+1}F_{n}+F_{2n}F_{n-1} \\
&= (F_{n+1}^2+F_{n}^2)F_{n}+(F_{n+1}^2-F_{n-1}^2)F_{n-1} \\
&= F_{n+1}^2F_n+F_n^3+F_{n+1}^2F_{n-1}-F_{n-1}^3 \\
&= F_{n+1}^2(F_n+F_{n-1})+F_n^3-F_{n-1}^3 \\
&= F_{n+1}^3+F_n^3-F_{n-1}^3
\end{align*}
\]
を得る．

\[
\begin{align*}
\sum_{k=1}^{n}F_k
&= \sum_{k=1}^{n}(F_{k+2}-F_{k+1})
= \sum_{k=1}^{n}F_{k+2}-\sum_{k=1}^{n}F_{k+1} \\
&= \sum_{k=2}^{n+1}F_{k+1}-\sum_{k=1}^{n}F_{k+1}
= F_{n+2}-F_2
= F_{n+2}-1
\end{align*}
\]

一般に，正方行列 $X$ の幾何級数に関して，行列 $(E-X)$ が正則であれば
\[
E+X+X^2+\cdots+X^n=(E-X)^{-1}(E-X^{n+1})
\]
が成り立つ．いま $(E-A)^{-1}=-A$ であるから行列 $(E-A)$ は正則であって
\[
E+A+A^2+\cdots+A^n=(E-A)^{-1}(E-A^{n+1})
\]
が成立する．左辺の各成分は
\[
\left[
\begin{array}{cc}
1+F_2+F_3+\cdots+F_{n+1} & F_1+F_2+\cdots+F_n \\
F_1+F_2+\cdots+F_n & 1+F_0+\cdots+F_{n-1}
\end{array}
\right]
\]
であり，右辺を計算すると
\[
(E-X)^{-1}(E-X^{n+1}) = \left[
\begin{array}{cc}
-1+F_{n+3} & -1+F_{n+2} \\
-1+F_{n+2} & F_{n+1}
\end{array}
\right]
\]
であるから，各成分を比較すれば所望の結果が得られる．

\[
\begin{align*}
\sum_{k=1}^{n}F_{2k-1}
&= \sum_{k=1}^{n}(F_{2k}-F_{2k-2})
= \sum_{k=1}^{n}F_{2k}-\sum_{k=1}^{n}F_{2k-2} \\
&= \sum_{k=2}^{n+1}F_{2k-2}-\sum_{k=1}^{n}F_{2k-2}
= F_{2n}-F_0
= F_{2n}
\end{align*}
\]

命題 2.1, 2.2 の結果を用いて

\[
\sum_{k=1}^{n}F_{2k}
= \sum_{k=1}^{2n}F_{k}-\sum_{k=1}^{n}F_{2k-1}
= F_{2n+2}-1-F_{2n}
= F_{2n+1}-1
\]

※ 命題 2.2 と同じような式変形から導出してもよい．

$n$ が非負の偶数のとき，非負整数 $m$ を用いて $n=2m$ とできて
\[
\begin{align*}
\sum_{k=1}^{n}(-1)^{k-1}F_k
&= \sum_{k=1}^{2m}(-1)^{k-1}F_k \\
&= \sum_{k=1}^{2m}F_k-2\sum_{k=1}^{m}F_{2k} \\
&= F_{2m+2}-1-2(F_{2m+1}-1) \\
&= (F_{2m+2}-F_{2m+1})-F_{2m+1}+1 \\
&= F_{2m}-F_{2m+1}+1 \\
&= -F_{2m-1}+1 \\
&= -F_{n-1}+1
\end{align*}
\]
が成り立つ．$n$ が奇数のとき，整数 $m$ を用いて $n=2m-1$ とできて
\[
\begin{align*}
\sum_{k=1}^{n}(-1)^{k-1}F_k
&= \sum_{k=1}^{2m-1}(-1)^{k-1}F_k \\
&= \sum_{k=1}^{2m}(-1)^{k-1}F_k+F_{2m} \\
&= -F_{2m-1}+1+F_{2m} \\
&= F_{2m-2}+1 \\
&= F_{n-1}+1
\end{align*}
\]
が成り立つ．ただし，３つ目の等号では $n$ が偶数のときの計算過程を用いた．

Fibonacci 数列の定義式より
\[
F_{n+2}F_{n+1} = F_{n+1}^2 + F_{n+1}F_n
\]
が成り立つ．$a_n = F_{n+1}F_n$ とおくと
\[
a_{n+1}-a_n=F_{n+1}^2, \quad a_1 = F_2F_1 = 1
\]
である．ゆえに階差数列の考え方から，$n \geqq 2$ のとき
\[
F_{n+1}F_n = a_n = a_1 + \sum_{k=1}^{n-1}F_{k+1}^2 = 1 + \sum_{k=2}^{n}F_k^2 = \sum_{k=1}^{n}F_k^2
\]
を得る．これは $n=1$ のときも成り立つ．

\[
\begin{align*}
\sum_{k=1}^{n}F_{3k}
&= \sum_{k=1}^{3n}F_k-\sum_{k=1}^{n}F_{3k-1}-\sum_{k-1}^{n}F_{3k-2} \\
&= \sum_{k=1}^{3n}F_k-\sum_{k=1}^{n}F_{3k-1}-\sum_{k=1}^{n}(F_{3k}-F_{3k-1}) \\
&= \sum_{k=1}^{3n}F_k-\sum_{k=1}^{n}F_{3k} \\
2\sum_{k=1}^{n}F_{3k}
&= \sum_{k-1}^{3n}F_k \\
\sum_{k=1}^{n}F_{3k}
&= \frac{1}{2}\sum_{k=1}^{n}F_{3k} =\frac{F_{3n+2}-1}{2}
\end{align*}
\]
より結論を得る．ただし，最後の等号では 命題 2.1 の結果を用いた．

系 1.8 の 3. を用いれば
\[
\begin{align*}
\sum_{k-1}^{n}F_{3k}
&= \sum_{k=1}^{n}F_{k+1}^3+\sum_{k=1}^{n}F_{k}^3-\sum_{k=1}^{n}F_{k-1}^3 \\
&= \left(\sum_{k=1}^{n}F_k^3+F_{n+1}^3-F_1^3\right)+\sum_{k=1}^{n}F_k^3-\left(\sum_{k=1}^{n}F_k^3+F_n^3-F_0^3\right) \\
&= \sum_{k=1}^{n}F_{k}^3+F_n^3+F_{n+1}^3-1
\end{align*}
\]
より
\[
\sum_{k=1}^{n+1}F_{k}^3 = \sum_{k=1}^{n}F_{k}^3+F_{n+1}^3=\sum_{k=1}^{n}F_{3k}-F_n^3+1=\frac{F_{3n+2}-2F_n^3+1}{2}
\]
が成り立つ．ただし最後の等号は 命題 2.5 の結果を用いた．したがって
\[
\sum_{k=1}^{n}F_k^3 = \frac{F_{3n-1}-2F_{n-1}^3+1}{2}
\]
を得る．

\[
\begin{align*}
& (F_{n+2}F_{n+1}F_n)^2-(F_{n+1}F_nF_{n-1})^2 \\
= \ & \left(F_nF_{n+1}(F_{n+2}+F_{n-1})\right)\left(F_nF_{n+1}(F_{n+2}-F_{n-1})\right) \\
= \ & F_n^2F_{n+1}^2(F_{n+2}+F_{n-1})(F_{n+2}-F_{n-1}) \\
= \ & F_n^2F_{n+1}^2(F_{n+2}+F_{n+1}-F_n)(F_{n+1}+F_n-F_{n-1}) \\
= \ & F_n^2F_{n+1}^2 \cdot 2F_{n+1} \cdot 2 F_n \\
= \ & 4F_n^3F_{n+1}^3
\end{align*}
\]

であるから

\[
\begin{align*}
4\sum_{k=1}^{n}F_k^3F_{k+1}^3
&= \sum_{k=1}^{n}(F_{k+2}F_{k+1}F_k)^2-\sum_{k=1}^{n}(F_{k+1}F_kF_{k-1})^2 \\
&= \sum_{k=2}^{n+1}(F_{k+1}F_kF_{k-1})^2-\sum_{k=1}^{n}(F_{k+1}F_kF_{k-1})^2 \\
&= (F_{n+2}F_{n+1}F_n)^2-(F_2F_1F_0)^2 \\
&= (F_{n+2}F_{n+1}F_n)^2
\end{align*}
\]

が成り立つ．両辺を $1/4$ 倍して結論を得る．

Fibonacci 数列を定義する漸化式
\[
F_{n+2} = F_{n+1} + F_n
\]
は，$F_{n+2}$ を $F_{n+1}$ で整数の範囲で割った商が $1$，余りが $F_n$ であることを表す．非負整数 $a$ と $b$ の最大公約数を $\textrm{gcd}(a,b)$ で表すと，Euclid の互除法より
\[
\textrm{gcd}(F_{n+2}, F_{n+1}) = \textrm{gcd}(F_{n+1},F_n)
\]
が成り立つから，これを繰り返して
\[
\textrm{gcd}(F_{n+1}, F_{n}) = \textrm{gcd}(F_{n}, F_{n-1}) = \cdots = \textrm{gcd}(F_{2}, F_1) = 1
\]
である．したがって $F_{n+1}$ と $F_n$ の最大公約数は $1$ であるから，これらは互いに素である．

命題 1.6 の両辺の絶対値を考えると

\[
|F_{n+1}F_{n-1}-F_n^2| = 1
\]

が成り立つ．$F_n, \, F_{n+1}$ がどちらも整数 $d \neq 0$ の倍数であるとすると，左辺は $d$ の倍数である．したがって右辺も $d$ の倍数であるから，$d$ が取り得る値は $d=1$ のみである．

Fibonacci 数列の加法定理より
\[
F_{m+n} = F_{m+1}F_n+F_{m}F_{n-1}
\]
が成り立つ．

・$F_{m+n}$ が $F_n$ の倍数であるとき，
\[
F_{m+n}-F_{m+1}F_n
\]
も $F_n$ の倍数であるから，右辺第２項の $F_mF_{n-1}$ も $F_n$ の倍数である．命題 3.1 より $F_{n-1}$ は $F_n$ の倍数ではないから，$F_m$ が $F_n$ の倍数である．

・$F_m$ が $F_n$ の倍数であるとき，加法定理の右辺は $F_n$ の倍数である．したがって左辺 $F_{m+n}$ も $F_n$ の倍数である．

Fibonacci 数列の加法定理より
\[
\begin{align*}
\textrm{gcd}\,(F_{m+n},F_n)
&= \textrm{gcd}\,(F_{m+1}F_n+F_{m}F_{n-1},F_n) \\
&= \textrm{gcd}\,(F_{m}F_{n-1},F_n) \\
&= \textrm{gcd}\,(F_m,F_n)
\end{align*}
\]

が成り立つ．ただし，２つ目の等号では
\[
\textrm{gcd}\,(a,b+ac) = \textrm{gcd}\,(a,b)
\]
であること，３つ目の等号では 命題 3.1 の結果を用いた．

※この結果は $m \leqq n$ であっても成り立つ．

$m$ を $n$ で割った商を $q$ とおくと，$m = nq + r$ と表せる．

補題 3.3 を $q$ 回繰り返し用いれば

\[
\begin{align*}
\textrm{gcd}\,(F_{m},F_n)
&= \textrm{gcd}\,(F_{nq+r},F_n) \\
&= \textrm{gcd}\,(F_{n(q-1)+r+n},F_n) \\
&= \textrm{gcd}\,(F_{n(q-1)+r},F_n) \\
& \qquad \vdots \\
&= \textrm{gcd}\,(F_{n+r},F_n) \\
&= \textrm{gcd}\,(F_r,F_n)
\end{align*}
\]

が成り立つ．

・$\textrm{gcd}\,(m,n)$ を Euclid の互除法で求める手順は以下のとおりである：

$m$ を $n$ で割った余りを $r_1$ とすると，Euclid の互除法より
\[
\textrm{gcd}\,(m,n) = \textrm{gcd}\,(n,r_1)
\]
が成り立つ．$n$ を $r_1$ で割った余りを $r_2$ とすると，同様にして
\[
\textrm{gcd}\,(n,r_1) = \textrm{gcd}\,(r_1,r_2)
\]
である．$r_{k-2}$　を $r_{k-1}$ で割った余りを $r_{k}$ とすると，$r_{k} \neq 0$ であれば
\[
\textrm{gcd}\,(r_{k-2},r_{k-1}) = \textrm{gcd}\,(r_{k-1},r_{k})
\]
が成り立ち，$r_{k}=0$ となるような最小の $k$ を $j$ とおくと，$\textrm{gcd}\,(m,n) = r_{j-1}$ である．

・補題 3.4 を繰り返し用いると
\[
\textrm{gcd}\,(F_m,F_n) = \textrm{gcd}\,(F_n,F_{r_1}) = \textrm{gcd}\,(F_{r_1},F_{r_2}) = \cdots = \textrm{gcd}\,(F_{r_{j-2}}, F_{r_{j-1}})
\]
が成り立ち，また，$r_j = 0$ であるから $F_{r_j} = 0$ である．したがって
\[
\textrm{gcd}\,(F_m,F_n) = F_{r_{j-1}} = F_{\textrm{gcd}\,(m,n)}
\]
を得る．

\[
\begin{align*}
\text{$F_m$ が $F_n$ の倍数}
& \iff \textrm{gcd}\,(F_m,F_n) = F_n \\
& \iff F_{\textrm{gcd}\,(m,n)} = F_n \\
& \iff \textrm{gcd}\,(m,n) = n \\
& \iff \text{$m$ が $n$ の倍数}
\end{align*}
\]

より題意が示される．ここで，２つ目の $\iff$ で 定理 3.5 を用いた．

また，３つ目の $\iff$ では $k, \, \ell \geqq 3$ であれば $F_{k} = F_{\ell} \iff k = \ell$ であることに注意した．

$a_n = F_{n+1}/F_n$ とおく．Fibonacci 数列の定義式より
\[
a_{n+1} = \frac{F_{n+2}}{F_{n+1}} = \frac{F_{n+1}+F_{n}}{F_{n+1}} = 1 + \frac{F_n}{F_{n+1}} = 1 + \frac{1}{a_n}
\]
が成り立つ．この数列が $\phi$ に収束することを示す．$\phi \neq 0$ は黄金数であるから $\phi^2-\phi-1=0$ を満たす．この式の両辺を $1/\phi$ 倍して整理すれば
\[
\frac{1}{\phi} = \phi-1
\]
が成り立つことに注意して

\[
\begin{align*}
a_{n+1}-\phi
&= 1+\frac{1}{a_n}-\phi \\
&= \frac{1}{a_n}-\frac{1}{\phi} \\
&= -\frac{1}{a_n\phi}(a_n-\phi)
\end{align*}
\]

を得る．ゆえに
\[
|a_{n+1}-\phi| = \frac{1}{a_n \phi}|a_n-\phi|
\]
が成り立つが，$F_{n+1} \geqq F_n$ より $a_{n} \geqq 1$ であることに注意すれば
\[
|a_{n+1}-\phi| \leqq \frac{1}{\phi}|a_n-\phi|
\]
より
\[
|a_n-\phi| \leqq \frac{1}{\phi}|a_{n-1}-\phi| \leqq \frac{1}{\phi^2}|a_{n-1}-\phi| \leqq \cdots \leqq \frac{1}{\phi^{n-1}}|a_1-\phi|
\]
が従う．$n \to \infty$ で $\phi^{n-1} \to \infty$ であるから，はさみうちの原理より
\[
\lim_{n \to \infty}\frac{F_{n+1}}{F_n} = \lim_{n \to \infty}a_n = \phi
\]
が成り立つ．

$a > \phi$ より

\[
\left|\frac{\phi}{a}\right| < 1 , \qquad \left|\frac{-1}{a\phi}\right|<1
\]
が成り立つことに注意する．Binet の公式より

\[
\begin{align*}
\sum_{n=1}^{\infty}\frac{F_n}{a^n}
&= \sum_{n=1}^{\infty}\frac{1}{\sqrt{5}} \left(\left(\frac{\phi}{a}\right)^n-\left(\frac{-1}{a\phi}\right)^n\right) \\
&= \frac{1}{\sqrt{5}}\left(\frac{\phi/a}{1-\phi/a}-\frac{-1/(a\phi)}{1+1/(a\phi)}\right) \\
&= \frac{1}{\sqrt{5}}\left(\frac{\phi}{a-\phi}+\frac{1}{a\phi+1}\right) \\
&= \frac{1}{\sqrt{5}} \cdot \frac{a(\phi^2+1)}{(a-\phi)(a\phi+1)} \\
&= \frac{1}{\sqrt{5}} \cdot \frac{a(\phi+2)}{(a^2-a-1)\phi} \\
&= \frac{1}{\sqrt{5}} \cdot \frac{a}{a^2-a-1} \cdot \left(1 + \frac{2}{\phi}\right) \\
&= \frac{1}{\sqrt{5}} \cdot \frac{a}{a^2-a-1} \cdot (2\phi-1) \\
&= \frac{a}{a^2-a-1}
\end{align*}
\]
を得る．