フィボナッチ数列の恒等式
カッシーニの公式
定理《カッシーニの公式, $1680$ 年》
すべての非負整数 $n$ に対して,
\[ F_nF_{n+2}-F_{n+1}{}^2 = (-1)^{n+1}\]
が成り立つ.
証明
- (i)
- $F_0F_2-F_1 = 0\cdot 1-1 = -1 = (-1)^2$ から, $n = 0$ のとき等式が成り立つ.
- (ii)
- $n = k$ ($k$: 非負整数) のとき等式が成り立つとすると, \[\begin{aligned} &F_{k+1}F_{k+3}-F_{k+2}{}^2 \\ &= (F_{k+2}-F_k)(F_{k+1}+F_{k+2})-F_{k+2}{}^2 \\ &= F_{k+2}F_{k+1}-F_kF_{k+1}-F_kF_{k+2} \\ &= F_{k+2}F_{k+1}-F_kF_{k+1}-F_{k+1}{}^2-(-1)^{k+1} \\ &= F_{k+2}F_{k+1}-(F_k+F_{k+1})F_{k+1}-(-1)^{k+1} \\ &= F_{k+2}F_{k+1}-F_{k+2}F_{k+1}+(-1)^{k+2} \\ &= (-1)^{k+2} \end{aligned}\] となり, $n = k+1$ のとき等式が成り立つ.
シューブの公式とフィボナッチ数の判定法
定理《シューブの公式, $1950$ 年》
すべての非負整数 $n$ に対して,
が成り立つ.
| $L_n{}^2-5F_n{}^2 = 4(-1)^n$ つまり $5F_n{}^2+4(-1)^n = L_n{}^2$ |
証明
ビネの公式により
\[\begin{aligned}
&\frac{L_n{}^2-5F_n{}^2}{4} = \frac{L_n+\sqrt 5F_n}{2}\cdot\frac{L_n-\sqrt 5F_n}{2} \\
&= \frac{\varphi ^n+(-\varphi )^{-n}+\varphi ^n-(-\varphi )^{-n}}{2}\cdot\frac{\varphi ^n+(-\varphi )^{-n}-\varphi ^n+(-\varphi )^{-n}}{2} \\
&= \varphi ^n(-\varphi )^{-n} = (-\varphi\varphi ^{-1})^n = (-1)^n
\end{aligned}\]
であるから, 両辺に $4$ を掛けると $L_n{}^2-5F_n{}^2 = 4(-1)^n$ が得られる.
別証明
- (i)
- $5F_0{}^2+4 = 4 = L_0{}^2$ から, $n = 0$ のとき等式が成り立つ.
- (ii)
- $n > 0$ のとき. フィボナッチ数列とリュカ数列の相互関係, カッシーニの公式により, \[\begin{aligned} L_n{}^2-4\{ F_n{}^2+(-1)^n\} &= (F_{n+1}+F_{n-1})^2-4F_{n+1}F_{n-1} \\ &= (F_{n+1}-F_{n-1})^2 = F_n{}^2 \end{aligned}\] となるから, $5F_n{}^2+4(-1)^n = L_n{}^2$ が成り立つ.
定理《フィボナッチ数の判定法, ゲッセル, $1972$ 年》
すべての非負整数 $\nu$ に対して,
$\nu$ はフィボナッチ数 $\iff$ $5\nu ^2+4$ または $5\nu ^2-4$ は平方数
が成り立つ.
証明: $(\Longleftarrow )$ の証明は $2$ 次体の整数論を用いると簡潔に記述できる (高校数学の範囲で証明できる, 後述).
$(\Longrightarrow )$ は, シューブの公式から従う.
$(\Longleftarrow )$ を示す. $5\cdot 0+4 = 2^2$ は平方数であり, $0 = F_0$ はフィボナッチ数であるから, $\nu > 0$ とする. $5\nu ^2\pm 4$ が平方数であるとする. このとき, ある非負整数 $\mu$ を用いて \[ 5\nu ^2\pm 4 = \mu ^2 \quad \cdots [1]\] と書ける. $\mu ^2-5\nu ^2 = \pm 4$ であるから, \[\frac{\mu +\nu\sqrt 5}{2}\cdot\frac{\mu -\nu\sqrt 5}{2} = \pm 1 \quad \cdots [2]\] が成り立つ. $[1]$ から $\mu ^2 \equiv \nu ^2 \pmod 2$ であるので, $\mu$ と $\nu$ の偶奇は一致する. よって, $\varepsilon = \dfrac{\mu +\nu\sqrt 5}{2}$ は $2$ 次体 $K = \mathbb Q(\sqrt 5)$ の整数環 $O_K$ に属する. さらに, $[2]$ から $\varepsilon$ のノルムは $\pm 1$ であるので, $\varepsilon$ は $O_K$ の単数である. $\varphi = \dfrac{1+\sqrt 5}{2},$ $\tilde\varphi = \dfrac{1-\sqrt 5}{2}$ とおく. $O_K$ の単数は $\pm\varphi ^n$ ($n$: 整数) の形に表されるが, $\nu > 0$ から $\varepsilon > 1$ であり, $\varphi > 1$ であるので, ある正の整数 $n$ について $\varepsilon = \varphi ^n$ となる. よって, ビネの公式により, \[\varepsilon = \frac{(\varphi ^n+\tilde\varphi ^n)+(\varphi ^n-\tilde\varphi ^n)}{2} = \frac{L_n+F_n\sqrt 5}{2}\] が成り立つ. $1,$ $\sqrt 5$ は $\mathbb Q$ 上線形独立であるから, 両辺の $\sqrt 5$ の係数を比較すると, $\nu = F_n$ が得られる.
$(\Longleftarrow )$ を示す. $5\cdot 0+4 = 2^2$ は平方数であり, $0 = F_0$ はフィボナッチ数であるから, $\nu > 0$ とする. $5\nu ^2\pm 4$ が平方数であるとする. このとき, ある非負整数 $\mu$ を用いて \[ 5\nu ^2\pm 4 = \mu ^2 \quad \cdots [1]\] と書ける. $\mu ^2-5\nu ^2 = \pm 4$ であるから, \[\frac{\mu +\nu\sqrt 5}{2}\cdot\frac{\mu -\nu\sqrt 5}{2} = \pm 1 \quad \cdots [2]\] が成り立つ. $[1]$ から $\mu ^2 \equiv \nu ^2 \pmod 2$ であるので, $\mu$ と $\nu$ の偶奇は一致する. よって, $\varepsilon = \dfrac{\mu +\nu\sqrt 5}{2}$ は $2$ 次体 $K = \mathbb Q(\sqrt 5)$ の整数環 $O_K$ に属する. さらに, $[2]$ から $\varepsilon$ のノルムは $\pm 1$ であるので, $\varepsilon$ は $O_K$ の単数である. $\varphi = \dfrac{1+\sqrt 5}{2},$ $\tilde\varphi = \dfrac{1-\sqrt 5}{2}$ とおく. $O_K$ の単数は $\pm\varphi ^n$ ($n$: 整数) の形に表されるが, $\nu > 0$ から $\varepsilon > 1$ であり, $\varphi > 1$ であるので, ある正の整数 $n$ について $\varepsilon = \varphi ^n$ となる. よって, ビネの公式により, \[\varepsilon = \frac{(\varphi ^n+\tilde\varphi ^n)+(\varphi ^n-\tilde\varphi ^n)}{2} = \frac{L_n+F_n\sqrt 5}{2}\] が成り立つ. $1,$ $\sqrt 5$ は $\mathbb Q$ 上線形独立であるから, 両辺の $\sqrt 5$ の係数を比較すると, $\nu = F_n$ が得られる.
補足
上記の証明で使った $2$ 次体の整数論の定理を高校数学の言葉で書くと, 次のようになる (証明はこちらを参照, かっこ内に専門用語を付記した).
$d$ を平方数でない正の整数とし, 有理数 $a_1,$ $a_2$ を用いて \[\alpha = a_1+a_2\sqrt d\] の形に表される実数 $\alpha$ 全体の集合を $K$ とおき ($K$ を $2$ 次体 (quadratic field) と呼ぶ), この $\alpha$ に対して \[ N(\alpha ) = a_1{}^2-da_2{}^2\] と定める ($K$ を定義域とする有理数値関数 $N$ を $K$ のノルム写像 (norm map) と呼ぶ).
$d$ を平方数でない正の整数とし, 有理数 $a_1,$ $a_2$ を用いて \[\alpha = a_1+a_2\sqrt d\] の形に表される実数 $\alpha$ 全体の集合を $K$ とおき ($K$ を $2$ 次体 (quadratic field) と呼ぶ), この $\alpha$ に対して \[ N(\alpha ) = a_1{}^2-da_2{}^2\] と定める ($K$ を定義域とする有理数値関数 $N$ を $K$ のノルム写像 (norm map) と呼ぶ).
- $d$ を $4$ で割った余りが $1$ であるとし, 偶奇の等しい整数 $a_1,$ $a_2$ を用いて $\dfrac{a_1+a_2\sqrt d}{2}$ の形に表される実数全体の集合を $O_K$ とおく ($K$ の整数環 (ring of integers) と呼ぶ). このとき, $O_K$ のすべての要素 $\varepsilon$ に対して, \[\varepsilon ^{-1} \in O_K \iff N(\varepsilon ) = \pm 1\] が成り立つ (この条件を満たす $O_K$ の要素 $\varepsilon$ を $K$ の単数 (unit), その全体を $K$ の単数群 (unit group) と呼ぶ). さらに, $\varepsilon _0{}^{-1} \in O_K,$ $\varepsilon _0 > 1$ を満たす $O_K$ の要素 $\varepsilon _0$ で, 次の条件を満たすものが存在する ($\varepsilon _0$ を $K$ の基本単数 (fundamental unit) と呼ぶ): $\varepsilon ^{-1} \in O_K$ を満たす $O_K$ のすべての要素 $\varepsilon$ は $\varepsilon = \pm\varepsilon _0{}^n$ ($n$: 整数) の形に表される. $d = 5$ のとき, $\varepsilon _0 = \dfrac{1+\sqrt 5}{2}$ である.
- 有理数 $a_1,$ $a_2,$ $b_1,$ $b_2$ に対して, \[ a_1+a_2\sqrt d = b_1+b_2\sqrt d \Longrightarrow (a_1,a_2) = (b_1,b_2)\] が成り立つ ($1,$ $\sqrt d$ は有理数体 $\mathbb Q$ 上線形独立 (linearly independent) であるという).
和の公式
定理《フィボナッチ数列の和, リュカ, $1876$ 年》
すべての正の整数 $n$ に対して,
- (1)
- $\displaystyle\sum _{k = 1}^nF_k = F_{n+2}-1$
- (2)
- $\displaystyle\sum _{k = 1}^nF_{2k-1} = F_{2n}$
- (3)
- $\displaystyle\sum _{k = 1}^nF_{2k} = F_{2n+1}-1$
証明
- (1)
- $F_k+F_{k+1} = F_{k+2}$ $(1 \leqq k \leqq n)$ の辺々を加えると \[\sum _{k = 1}^nF_k+\sum _{k = 1}^nF_{k+1} = \sum _{k = 1}^nF_{k+2}\] となるから, \[\sum _{k = 1}^nF_k+\sum _{k = 2}^{n+1}F_k = \sum _{k = 3}^{n+2}F_k = F_{n+2}+\sum _{k = 2}^{n+1}F_k-F_2\] が成り立つ. 両辺から $\displaystyle\sum _{k = 2}^{n+1}F_k$ を引くと, 求める等式が得られる.
- (2)
- (i)
- $F_1 = F_2 = 1$ から, $n = 1$ のとき等式が成り立つ.
- (ii)
- $n = m$ ($m$: 正の整数) のとき等式が成り立つとすると, \[\begin{aligned}\sum _{k = 1}^mF_{2k-1}+F_{2m+1} &= F_{2m}+F_{2m+1} \\ &= F_{2m+2} = F_{2(m+1)} \end{aligned}\] となり, $n = m+1$ のとき等式が成り立つ.
- (3)
- (i)
- $F_2 = F_3-1 = 1$ から, $n = 1$ のとき等式が成り立つ.
- (ii)
- $n = m$ ($m$: 正の整数) のとき等式が成り立つとすると, \[\begin{aligned} \sum _{k = 1}^mF_{2k}+F_{2m+2} &= F_{2m+1}-1+F_{2m+2} \\ &= F_{2m+3}-1 = F_{2(m+1)+1}-1 \end{aligned}\] となり, $n = m+1$ のとき等式が成り立つ.
ゼッケンドルフの定理
定理《ゼッケンドルフの定理, ゼッケンドルフ, $1939$ 年》
すべての正の整数はフィボナッチ数列の隣り合わない項 (第 $2$ 項以降) の和としてただ $1$ 通りに表される.
定義《ゼッケンドルフ表現》
正の整数をフィボナッチ数列の隣り合わない項 (第 $2$ 項以降) の和として表す式をゼッケンドルフ表現 (Zeckendorf representation) と呼ぶ.
定理の証明
存在については, こちらを参照.
一意性を示すため, 正の整数 $n$ のゼッケンドルフ表現の個数を $R(n)$ とおき, $R(n) = 1$ であることを示す. 明らかに, $R(1) = 1$ である. $n$ を $2$ 以上の整数として, \[ n = F_{i_1}+\cdots +F_{i_l} \quad (2 \leqq i_1 < \cdots < i_l)\] をそのゼッケンドルフ表現とすると, これから次のように $n-1$ のゼッケンドルフ表現が作れるから, $R(n) \leqq R(n-1)$ が成り立つ.
一意性を示すため, 正の整数 $n$ のゼッケンドルフ表現の個数を $R(n)$ とおき, $R(n) = 1$ であることを示す. 明らかに, $R(1) = 1$ である. $n$ を $2$ 以上の整数として, \[ n = F_{i_1}+\cdots +F_{i_l} \quad (2 \leqq i_1 < \cdots < i_l)\] をそのゼッケンドルフ表現とすると, これから次のように $n-1$ のゼッケンドルフ表現が作れるから, $R(n) \leqq R(n-1)$ が成り立つ.
- $i_1 = 2$ のとき. \[ n-1 = F_{i_2}+\cdots +F_{i_l}\] は $n-1$ のゼッケンドルフ表現である.
- $i_1 > 2,$ $i_1$ が奇数のとき. $F_{i_1}-1 = F_2+\cdots +F_{i_1-1}$ であるから, \[ n-1 = F_2+\cdots +F_{i_1-1}+F_{i_2}+\cdots +F_{i_l}\] であり, これは $n-1$ のゼッケンドルフ表現である.
- $i_1 > 2,$ $i_1$ が偶数のとき. $F_{i_1}-1 = F_3+\cdots +F_{i_1-1}$ であるから, \[ n-1 = F_2+\cdots +F_{i_1-1}+F_{i_2}+\cdots +F_{i_l}\] であり, これは $n-1$ のゼッケンドルフ表現である.
例《ゼッケンドルフ表現》
$1$ から $12$ までの整数は,
\[\begin{aligned}
1 &= F_2, & 7 &= F_5+F_3, \\
2 &= F_3, & 8 &= F_6, \\
3 &= F_4, & 9 &= F_6+F_2, \\
4 &= F_4+F_2, & 10 &= F_6+F_3, \\
5 &= F_5, & 11 &= F_6+F_4, \\
6 &= F_5+F_2, & 12 &= F_6+F_4+F_2
\end{aligned}\]
と表される.
高校数学の問題
数と式
問題《$2$ 次体のノルムと単数》
有理数 $a_1,$ $a_2$ を用いて
\[\alpha = a_1+a_2\sqrt 5\]
の形に表される実数 $\alpha$ について, その全体の集合を $K$ とおき,
\[\tilde\alpha = a_1-a_2\sqrt 5, \quad N(\alpha ) = \alpha\tilde\alpha = a_1{}^2-5a_2{}^2\]
と定める.
さらに, 偶奇が等しい整数 $a_1,$ $a_2$ を用いて
\[\alpha = \dfrac{a_1+a_2\sqrt 5}{2}\]
の形に表される実数 $\alpha$ 全体の集合を $O$ とおく.
- (1)
- $K$ の要素 $\alpha,$ $\beta$ に対して, \[ N(\alpha\beta ) = N(\alpha )N(\beta )\] が成り立つことを示せ.
- (2)
- $O$ の要素 $\alpha,$ $\beta$ に対して, $\alpha\beta$ もまた $O$ の要素であることを示せ.
- (3)
- $O$ の要素 $\alpha$ に対して, $N(\alpha )$ は整数であることを示せ.
- (4)
- $O$ の要素 $\varepsilon$ に対して, \[\varepsilon ^{-1} \in O \iff N(\varepsilon ) = \pm 1\] であることを示せ.
- (5)
- $\varepsilon _0,$ $\varepsilon _0{}^{-1} \in O,$ $\varepsilon _0 > 1$ を満たす最小の正の数は $\varepsilon _0 = \dfrac{1+\sqrt 5}{2}$ であることが知られている. $\varepsilon ^{-1} \in O$ を満たす $O$ の要素 $\varepsilon$ は, この $\varepsilon _0$ を用いて $\varepsilon = \pm\varepsilon _0{}^n$ ($n$: 整数) の形に表されることを示せ.
解答例
こちらを参照.
式と証明
問題《奇数番目のフィボナッチ数からなる数列の漸化式》
$\varphi$ を $x^2-x-1 = 0$ の正の実数解とし, $F_n$ $(n \geqq 1)$ を
\[ F_n = \frac{\varphi ^n-\varphi ^{-n}}{\sqrt 5}\]
で定める.
- (1)
- $\varphi ^2,$ $\varphi ^4$ を $\varphi$ の $1$ 次式で表せ.
- (2)
- $F_{2n+3} = 3F_{2n+1}-F_{2n-1}$ が成り立つことを示せ.
解答例
こちらを参照.
数列
問題《ゼッケンドルフの定理》
$F_1 = F_2 = 1,$ $F_{n+2} = F_n+F_{n+1}$ で定まる数列 $\{ F_n\}$ を「フィボナッチ数列」と呼ぶ.
すべての正の整数 $n$ に対して,
- $[*]$
- $n$ は「フィボナッチ数列」の隣り合わない項の和として表せる
(参考: $2017$ 九州大)
解答例
こちらを参照.
問題《カッシーニの公式》
数列 $\{ F_n\}$ について, 初期条件 $F_1 = F_2 = 1$ のもとで,
- $[1]$
- $F_{n+2} = F_n+F_{n+1}$
- $[2]$
- $F_{n+1}{}^2-F_nF_{n+2} = (-1)^n$
(参考: $2001$ 横浜国立大)
解答例
こちらを参照.