数学B / 数列

フィボナッチ数のカッシーニ恒等式と互いに素

実戦編数列整数の性質数学的帰納法3項間漸化式単元横断

問題

フィボナッチ数列を $F_{1} = F_{2} = 1, F_{n + 2} = F_{n + 1} + F_{n}$ で定める。(1) $F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n}$ ( $n \geq 2$ )を示せ。

(2) これを用いて、連続する2つのフィボナッチ数 $F_{n}, F_{n + 1}$ が互いに素であることを示せ。

ヒントを見る

(1) $F_{n + 2} F_{n} - F_{n + 1}^{2}$ を $F_{n + 2} = F_{n + 1} + F_{n}$ で書き換えると、符号が反転して1つ前の式に戻る。(2) 公約数 $d$ は左辺を割るので $\pm 1$ も割る。

解答・解説

方針

(1) $n$ での式から $n + 1$ での式を漸化式で導く帰納法。(2) $F_{n}, F_{n + 1}$ の公約数 $d$ はカッシーニ式の左辺を割り、右辺 $\pm 1$ も割る。

解答

⓪ 発想 — どう考え始めるか。 (1) のカッシーニ恒等式 $F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n}$ は、 $n$ から $n + 1$ へ渡る形をしている。数学的帰納法が自然だ。

(2) の「互いに素」は、(1) を道具として使う。連続する2数 $F_{n}, F_{n + 1}$ の公約数 $d$ を考える。

$d$ は $F_{n - 1} = F_{n + 1} - F_{n}$ も割るから、カッシーニ式の左辺 $F_{n + 1} F_{n - 1} - F_{n}^{2}$ を割る。ということは右辺 $\pm 1$ も割る。 $1$ を割れる正の整数は $1$ だけ — だから $g cd = 1$ 。

① カッシーニ恒等式(帰納法)。 $P_{n} : F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n}$ とする。 $n = 2$ : $F_{3} F_{1} - F_{2}^{2} = 2 \cdot 1 - 1 = 1 = (- 1)^{2}$ で成立。 $P_{n}$ を仮定して $P_{n + 1}$ を示す。 $F_{n + 2} = F_{n + 1} + F_{n}$ を使うと $F_{n + 2} F_{n} - F_{n + 1}^{2} = (F_{n + 1} + F_{n}) F_{n} - F_{n + 1}^{2} = F_{n + 1} F_{n} + F_{n}^{2} - F_{n + 1}^{2} .$ ここで $F_{n} = F_{n + 1} - F_{n - 1}$ を最初の項に使うと $F_{n + 1} F_{n} = F_{n + 1}^{2} - F_{n + 1} F_{n - 1}$ 、まとめて $F_{n + 2} F_{n} - F_{n + 1}^{2} = F_{n + 1}^{2} - F_{n + 1} F_{n - 1} + F_{n}^{2} - F_{n + 1}^{2} = - (F_{n + 1} F_{n - 1} - F_{n}^{2}) = - (- 1)^{n} = (- 1)^{n + 1} .$ よって $P_{n + 1}$ も成立し、すべての $n \geq 2$ で $F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n}$ 。

② 連続する2数は互いに素。 $d = g cd (F_{n}, F_{n + 1})$ とする。 $d$ は $F_{n}$ と $F_{n + 1}$ をともに割るから、 $F_{n + 1} F_{n - 1} - F_{n}^{2}$ も割る( $F_{n - 1} = F_{n + 1} - F_{n}$ も $d$ の倍数だから、左辺は $d$ の倍数)。

重要①より

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

。

d

が

\pm 1

を割るので

d = 1

したがって $F_{n}$ と $F_{n + 1}$ は互いに素。

まとめ カッシーニ恒等式は、漸化式で1つ前に戻す帰納法で示せる(符号が交代するのが味)。その値が $\pm 1$ なので、連続フィボナッチ数の公約数は $\pm 1$ を割り $= 1$ 。数列の恒等式と整数(互いに素)の融合。

発展 — 一歩先へ。 カッシーニ恒等式は、より一般の $g cd (F_{m}, F_{n}) = F_{g c d (m, n)}$ という美しい定理の入り口だ。連続項が互いに素なのは、 $g cd (m, m + 1) = 1$ の場合。ユークリッドの互除法がフィボナッチ数の添字の上でそっくり成り立つ — 数列と整数論が深いところでつながっている。

答

(1) 数学的帰納法(または差の漸化式)で $F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n}$ 。(2) $F_{n}$ と $F_{n + 1}$ の公約数は $(- 1)^{n}$ すなわち $1$ を割るので $g cd = 1$ 。

別解

別解 — 行列 $(1110)$ の累乗で一撃(得意な人向けの高い視点)。 フィボナッチ数は行列で書ける。

$(1110)^{n} = (F_{n + 1} F_{n} F_{n} F_{n - 1}) .$

この両辺の行列式をとる。左辺は $det (1110)^{n} = (- 1)^{n}$ 、右辺は $F_{n + 1} F_{n - 1} - F_{n}^{2}$ 。等号で結んで

$F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n} .$

カッシーニ恒等式が、帰納法なしで「行列式は積の順に掛かる」という1つの性質から出た。(2) も同じで、 $F_{n}, F_{n + 1}$ の公約数 $d$ はこの行列式 $\pm 1$ を割るから $d = 1$ 。行列で書くと、 $g cd (F_{m}, F_{n}) = F_{g c d (m, n)}$ のような深い性質も見通しよく扱える。

ポイント

カッシーニ式は $F_{n + 2} = F_{n + 1} + F_{n}$ を代入する帰納法で示せる(符号が交代)。
公約数 $d$ はカッシーニ式の左辺を割る。
左辺 $= \pm 1$ なので $d = 1$ 、連続フィボナッチ数は互いに素。

よくある間違い

(1) の帰納法で、 $n$ の式から $n + 1$ の式へ渡す漸化式 $F_{n + 2} = F_{n + 1} + F_{n}$ の使い方を誤る。
(2) で公約数 $d$ が $F_{n - 1} = F_{n + 1} - F_{n}$ を割ること(だからカッシーニ式全体を割る)を飛ばす。
$(- 1)^{n}$ を「 $d$ が割る数」として $\pm 1$ にまとめず、 $n$ の偶奇で場合分けして混乱する。