Fibonacci 数列


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

スポンサーリンク

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

1. Fibonacci 数列の定義と基本性質

定義 1.1: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$ と考えることがある.

 

定義 1.2:黄金比

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

 

命題 1.3:行列を用いた表現

\[
\left[
\begin{array}{cc}
F_{n+1} & F_n \\
F_n & F_{n-1}
\end{array}
\right]
=
\left[
\begin{array}{cc}
1 & 1 \\
1 & 0
\end{array}
\right]^n
\]

 
証明(click)

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

が従う.

 

以降,$\displaystyle {A=
\left[\begin{array}{cc}
1 & 1 \\
1 & 0
\end{array}
\right]}$ とする.

定理 1.4:Fibonacci 数列の一般項(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}}
\]
が従う.

 
行列を用いた証明(click)

・ $2$ 次方程式 $x^2-x-1=0$ の2つの解を $\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}}
\]
が従う.

 

補題 1.5:階段の上がり方

$n$ 段からなる階段を,$1$ 歩で $1$ 段,または $1$ 歩で $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$ について題意は成り立つ.

 

命題 1.6:

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

 
行列を用いた証明(click)

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

 

命題 1.7:Fibonacci 数列の加法定理

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

 
補題 1.4 を用いた説明(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*}
\]

を得る.

 
行列を用いた説明(click)

命題 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.8:

次の等式が成り立つ:

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$ 命題 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*}
\]
を得る.ここで,3つ目の等号では $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*}
\]
を得る.

 

2. Fibonacci 数列の和に関する性質

命題 2.1: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*}
\]

 
行列を用いた証明(click)

一般に,正方行列 $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]
\]
であるから,各成分を比較すれば所望の結果が得られる.

 

命題 2.2:奇数項の和

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

 

命題 2.3:偶数項の和

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

 
証明(click)

命題 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 と同じような式変形から導出してもよい.

 

命題 2.4:交代和

\[
\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$ が偶数のときの計算過程を用いた.

 

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

 

命題 2.6: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*}
\]
より結論を得る.ただし,最後の等号では 命題 2.1 の結果を用いた.

 

命題 2.7: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)

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

 

命題 2.8:隣接2項の積の3乗和

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

 

3. 整数論的な性質

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

命題 3.1:隣接項の関係

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

 
命題 1.6 を用いた証明(click)

命題 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$ のみである.

 

補題 3.2:

$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$ の倍数である.命題 3.1 より $F_{n-1}$ は $F_n$ の倍数ではないから,$F_m$ が $F_n$ の倍数である.

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

 

補題 3.3:

\[
\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つ目の等号では 命題 3.1 の結果を用いた.

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

 

補題 3.4:

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

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

 
証明(click)

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

が成り立つ.

 

定理 3.5:

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

・補題 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)}
\]
を得る.

 

 系 3.6:

$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$ で 定理 3.5 を用いた.

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

 

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

定理 4.1: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
\]
が成り立つ.

 

定理 4.2

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

 

20200113 更新
20210103 更新


スポンサーリンク