Fibonacci 数列


漸化式
\[
F_{n+2}=F_{n+1}+F_n , \quad F_1=F_2=1
\]
で定まる数列を Fibonacci 数列という.今回はこの数列の性質をまとめる.

スポンサーリンク

以下,$m, \, n$ は非負整数として,必要に応じて $m \geqq n$ を満たすとする.

定義と基本性質

Define 1-a(Fibonacci 数列)

漸化式
\[
F_{n+2}=F_{n+1}+F_n, \quad F_1=F_2=1
\]
で定まる数列 $\{F_n\} \ (n=1,2,3,\dots)$ を Fibonacci 数列 という.

 

$n$ を非負整数に限って定義しているが,漸化式より
\[
F_0=F_2-F_1=0
\]
とできるから,以下では $F_0$ は便宜的に $0$ と考えることがある.

Define 1-b(黄金比)

\[
\phi = \frac{1+\sqrt{5}}{2}
\]
を黄金数といい,比 $1 : \phi$ を 黄金比という.

 

$\phi$ は $2$ 次方程式 $x^2-x-1 = 0$ の正の解であり,以下の等式を満たす:
\[
\phi^2 = \phi + 1, \qquad \frac{1}{\phi} = \phi-1
\]

 
Theorem 1-c(Binet の公式)

\[
F_n = \frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right\} = \frac{\phi^n-(-\phi)^{-n}}{\sqrt{5}}
\]

 
証明(click)

$2$ 次方程式 $x^2-x-1=0$ の2つの解を $\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$ とおけば,第1式は
\[
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$ とおけば,第2式から同様の手順で
\[
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}}
\]
が従う.

 
Lemma 2

$n$ 段からなる階段を,$1$ 歩で $1$ 段,または $2$ 歩で $2$ 段のどちらかの方法を組み合わせて一番上まで上がる.このとき,階段の上がり方は全部で $F_{n+1}$ 通りである.

 
説明(click)

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

$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$ について題意は成り立つ.

 
Proposition 3-a

\[
F_{n+1}F_{n-1}-F_{n}^2=(-1)^n
\]

 
証明(click)

Fibonacci 数列の漸化式より

\[
F_{n+2}F_n=F_{n+1}F_n+F_n^2
\]
が成り立つ.同様に漸化式から得られる関係式 $F_n = F_{n+1}-F_{n-1}$ を右辺第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}
\]
を得る.

 
Proposition 3-b(Fibonacci数列の加法定理)

\[
F_{m+n} = F_{m+1}F_n+F_{m}F_{n-1}
\]

 
Lemma 2 を用いた説明(click)

$(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}$ 通りであるから,題意は示された.

 
式変形による証明(click)

\[
\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*}
\]

が成り立つ.2つ目,5つ目の等号の部分

\[
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*}
\]

を得る.

 
 
Corollary 3-c

次の等式が成り立つ:

1. $\quad F_{2n} = F_{n+1}^2-F_{n-1}^2$

1. $\quad F_{2n+1} = F_{n+1}^2+F_{n}^2$

1. $\quad F_{3n} = F_{n+1}^3+F_{n}^3-F_{n-1}^3$

 
証明(click)

1. $\quad$ Proposition 3-b において $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*}
\]
を得る.ここで,3つ目の等号では $F_n = F_{n+1}-F_{n-1}$ を用いた.

2. $\quad$ Proposition 3-b において $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$ Proposition 3-b および Corollary 3-c の 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*}
\]
を得る.

 

和に関する性質

Proposition 4-a(Fibonacci 数列の和)

\[
\sum_{k=1}^{n}F_k = F_1 + F_2 + F_3 + \cdots + F_n = F_{n+2}-1
\]

 
証明(click)

\[
\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*}
\]

//
 
Proposition 4-b(奇数項の和)

\[
\sum_{k=1}^{n}F_{2k-1} = F_1 +F_3 +F_5 + \cdots + F_{2n-1} = F_{2n}
\]

 
証明(click)

\[
\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*}
\]

//
 
Proposition 4-c(偶数項の和)

\[
\sum_{k=1}^{n}F_{2k} = F_2 + F_4 + F_6 + \cdots + F_{2n} = F_{2n+1}-1
\]

 
証明(click)

4-b,4-cの結果を用いて

\[
\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
\]

//

※ 定理3と同じような式変形から導出してもよい.

 
Proposition 4-d(交代和)

\[
\sum_{k=1}^{n}(-1)^{k-1}F_k = F_1 – F_2 + F_3 – \cdots + (-1)^{n-1}F_n = (-1)^{n-1}F_{n-1}+1
\]

 
証明(click)

$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*}
\]
が成り立つ.ただし,3つ目の等号では $n$ が偶数のときの計算過程を用いた.

 
Proposition 4-e(2乗和)

\[
\sum_{k=1}^{n}F_k^2 = F_1^2 + F_2^2 + F_3^2 + \cdots + F_n^2 = F_{n+1}F_n
\]

 
証明(click)

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$ のときも成り立つ.

 
Proposition 4-f(3の倍数の項の和)

\[
\sum_{k=1}^{n}F_{3k} = F_3 + F_6 + F_9 + \cdots + F_{3n} = \frac{F_{3n+2}-1}{2}
\]

 
証明(click)

\[
\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*}
\]
より結論を得る.ただし,最後の等号では Proposition 4-a の結果を用いた.

 
Proposition 4-g(3乗和)

\[
\sum_{k=1}^{n}F_k^3 = F_1^3 + F_2^3 + F_3^3 + \cdots + F_n^3 = \frac{F_{3n-1}-2F_{n-1}^3+1}{2}
\]

 
証明(click)

Corollary 3-c の 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}
\]
が成り立つ.ただし最後の等号は Proposition 4-f の結果を用いた.したがって
\[
\sum_{k=1}^{n}F_k^3 = \frac{F_{3n-1}-2F_{n-1}^3+1}{2}
\]
を得る.

 
Proposition 4-h(隣接2項の3乗和,Ohtsuka.H)

\[
\sum_{k=1}^{n}F_k^3F_{k+1}^3 = F_1^3F_2^3 + F_2^3F_3^3 + F_3^3F_4^3 + \cdots + F_n^3F_{n+1}^3 = \left(\frac{F_{n+2}F_{n+1}F_n}{2}\right)^2
\]

 
証明(click)

\[
\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$ 倍して結論を得る.

 

整数論的な性質

非負整数 $a, \, b$ に対して $\textrm{gcd}\,(a,b)$ は $a$ と $b$ の最大公約数を表すとする.

Proposition 5-a(隣接項の関係)

$F_n$ と $F_{n+1}$ は互いに素である.

 
Euclidの互除法を用いた証明(click)

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$ であるから,これらは互いに素である.

 
Proposition 3-aを用いた証明(click)

Proposition 3-a の両辺の絶対値を考えると

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

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

 
Lemma 5-b

$F_{m+n}$ が $F_n$ の倍数 $\iff$ $F_m$ が $F_n$ の倍数

 
証明(click)

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$ の倍数であるから,右辺第2項の $F_mF_{n-1}$ も $F_n$ の倍数である.Proposition 5-a より $F_{n-1}$ は $F_n$ の倍数ではないから,$F_m$ が $F_n$ の倍数である.

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

 
Lemma 5-c

\[
\textrm{gcd}\,(F_{m+n},F_n) = \textrm{gcd}\,(F_m,F_n)
\]

 
証明(click)

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*}
\]

が成り立つ.ただし,2つ目の等号では
\[
\textrm{gcd}\,(a,b+ac) = \textrm{gcd}\,(a,b)
\]
であること,3つ目の等号では Proposition 5-a の結果を用いた.

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

 
Lemma 5-d

$m$ を $n$ で割った余りを $r$ とするとき

\[
\textrm{gcd}\,(F_m,F_n) = \textrm{gcd}\,(F_n,F_r)
\]

 
証明(click)

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

Lemma 5-c を $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*}
\]

が成り立つ.

 
Theorem 5-e

\[
\textrm{gcd}(F_m,F_n) = F_{\textrm{gcd}(m,n)}
\]

 
証明(click)

・$\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}$ である.

・Theorem 5-d を繰り返し用いると
\[
\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)}
\]
を得る.

 
Corollary 5-f

$m$ が $n$ の倍数 $\iff$ $F_m$ が $F_n$ の倍数

 
証明(click)

\[
\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*}
\]

より題意が示される.ここで,2つ目の $\iff$ で Theorem 5-e を用いた.

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

 

比,極限,無限級数に関する性質

Theorem 6(Fibonacci数列の比)

\[
\lim_{n \to \infty}\frac{F_{n+1}}{F_n} = \phi
\]

 
証明(click)

$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
\]
が成り立つ.

//
 
Theorem 7

\[
\sum_{n=1}^{\infty}\frac{F_n}{a^n} = \frac{a}{a^2-a-1} \qquad (a > \phi)
\]

 
証明(click)

$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*}
\]
を得る.

//
 

特に
\[
\sum_{n=1}^{\infty}\frac{F_n}{10^{n+1}} = \frac{1}{10} \cdot \frac{10}{100-10-1}=\frac{1}{89}
\]
が成り立つ.

 

線形代数(行列)を用いたFibonacci数列の表現などは以下のノートにまとめた:

Fibonacci2 に何も見つかりません
http://sigmagic.net/fibonacci2

 

20200113 更新


スポンサーリンク