有名問題・定理から学ぶ数学

Well-Known Problems and Theorems in Mathematics

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください.

フィボナッチ数列の等式

和の公式

定理《フィボナッチ数列の和, リュカ, $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$ のとき等式が成り立つ.
(i), (ii) から, すべての正の整数 $n$ に対して, 等式が成り立つ.
(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$ のとき等式が成り立つ.
(i), (ii) から, すべての正の整数 $n$ に対して, 等式が成り立つ.

ゼッケンドルフの定理

定理《ゼッケンドルフの定理, ゼッケンドルフ, $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)$ が成り立つ.
  • $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$ のゼッケンドルフ表現である.
$n \geqq 2$ のとき $n \leqq F_{n+1}$ であるから, \[ 1 = R(F_{n+1}) \leqq \cdots \leqq R(n) \leqq \cdots \leqq R(1) = 1\] が成り立つ. ゆえに, すべての正の整数 $n$ に対して $R(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}\] と表される.

カッシーニの公式・シューブの公式

定理《カッシーニの公式, $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$ のとき等式が成り立つ.
(i), (ii) から, すべての非負整数 $n$ に対して等式が成り立つ.

定理《シューブの公式, $1950$ 年》

 すべての非負整数 $n$ に対して, \[ 5F_n{}^2+4(-1)^n = L_n{}^2\] が成り立つ.

証明

(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$ が成り立つ.
 (i), (ii) から, すべての非負整数 $n$ に対して等式が成り立つ.

フィボナッチ数の判定法

定理《フィボナッチ数の判定法, ゲッセル, $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$ が得られる.

補足

 上記の証明で使った $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$ を $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)であるという).

問題

数学 I: 数と式

問題《$2$ 次体のノルムと単数》

 有理数 $a_1,$ $a_2$ を用いて \[\alpha = a_1+a_2\sqrt 5\] の形に表される実数 $\alpha$ 全体の集合を $K$ とおき, この $\alpha$ に対して \[\tilde\alpha = a_1-a_2\sqrt 5, \quad N(\alpha ) = \alpha\tilde\alpha = a_1{}^2-5a_2{}^2\] と定める.
(1)
$K$ の要素 $\alpha,$ $\beta$ に対して, \[ N(\alpha\beta ) = N(\alpha )N(\beta )\] が成り立つことを示せ.
 また, 偶奇が等しい整数 $a_1,$ $a_2$ を用いて \[\alpha = \dfrac{a_1+a_2\sqrt 5}{2}\] の形に表される実数 $\alpha$ 全体の集合を $O$ とおく.
(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)
$O$ に属する, $\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$: 整数)の形に表されることを示せ.

解答例

 こちらを参照.

数学 B: 数列

問題《ゼッケンドルフの定理》

 $F_1 = F_2 = 1,$ $F_{n+2} = F_n+F_{n+1}$ で定まる数列 $\{ F_n\}$ を「フィボナッチ数列」と呼ぶ. すべての正の整数 $n$ に対して,
$[*]$
$n$ は「フィボナッチ数列」の隣り合わない項の和として表せる
が成り立つことを示せ. ただし,「フィボナッチ数列」の項そのものも項数が $1$ の和として考える.
(参考: 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 横浜国立大)

解答例

 こちらを参照.