Binetの公式(Fibonacci数)(Binet's formula for Fibonacci numbers)とは、Fibonacci 数 $F_n$ を $\varphi=\frac{1+\sqrt5}2$、$\psi=\frac{1-\sqrt5}2$ により $F_n=(\varphi^n-\psi^n)/\sqrt5$ と表す式である。漸化式 $F_{n+2}=F_{n+1}+F_n$ の解が 2 つの等比数列の 1 次結合になることから得られる。$|\psi|< 1$ なので $F_n$ は $\varphi^n/\sqrt5$ に最も近い整数であり、増え方や隣り合う項の比の収束の速さが読める。行列式についての Cauchy–Binet の公式とは別のものである。
前提知識: Fibonacci数, 黄金比, 漸化式
Fibonacci数 は $F_{n+2}=F_{n+1}+F_n$ で順に定まる整数の列である。Binetの公式(Binet's formula)は、その第 $n$ 項を漸化式をたどらずに
$$
F_n=\frac{\varphi^n-\psi^n}{\sqrt5},\qquad\varphi=\frac{1+\sqrt5}2,\quad\psi=\frac{1-\sqrt5}2
$$
と直接書く式である。$\sqrt5$ を含む式の値がすべての $n$ で整数になるので一見意外だが、$\varphi,\psi$ は方程式 $x^2=x+1$ の 2 根であり、この方程式は漸化式を「等比数列の解」で読んだものにほかならない。
公式の値打ちは、$|\psi|< 1$ から第 2 項がすぐに小さくなることにある。$F_n$ は $\varphi^n/\sqrt5$ にいちばん近い整数であり、増え方、隣り合う項の比、桁数、Lucas 数との関係がこの式から読める。行列式についての Cauchy–Binetの公式 とは別の公式である。
| 問い | 答え |
|---|---|
| なぜこの形か | 漸化式の解が等比数列 $\varphi^n,\psi^n$ の 1 次結合だから(lem-bf-general) |
| なぜ整数になるか | $\varphi^n=F_n\varphi+F_{n-1}$ の係数を比べているから。二項展開でも見える(prop-bf-binomial) |
| 大きい $n$ では | $F_n$ は $\varphi^n/\sqrt5$ の四捨五入である(cor-bf-nearest) |
| 比の収束の速さは | $F_{n+1}-\varphi F_n=\psi^n$(prop-bf-ratio) |
| 整数以外の世界では | 標数が $2$、$5$ でなく $5$ が平方である有限体でも同じ形で成り立つ(prop-bf-mod) |
$F_0=0$、$F_1=1$、$F_{n+2}=F_{n+1}+F_n$($n\ge0$)とする。$\varphi=\frac{1+\sqrt5}2$ を 黄金比、$\psi=\frac{1-\sqrt5}2$ をその共役と呼ぶ。これらは $x^2-x-1=0$ の 2 根で、
$$
\varphi+\psi=1,\qquad\varphi\psi=-1,\qquad\varphi-\psi=\sqrt5,\qquad\psi=-\frac1\varphi=-0.618\ldots
$$
を満たす。
すべての $n\ge0$ について
$$
F_n=\frac{\varphi^n-\psi^n}{\sqrt5}
$$
である。
右辺を $G_n$ とおく。$G_0=0$、$G_1=(\varphi-\psi)/\sqrt5=1$ である。$\varphi^2=\varphi+1$ の両辺に $\varphi^n$ を掛けると $\varphi^{n+2}=\varphi^{n+1}+\varphi^n$ であり、$\psi$ についても同じなので、$G_{n+2}=G_{n+1}+G_n$ である。$(G_n)$ と $(F_n)$ は同じ初期値と同じ漸化式をもつので、帰納法によりすべての $n$ で一致する。$\square$
この証明は式を知っていれば確かめられるが、式がどこから来たかは語らない。次の節で、同じ式を導く。
実数列 $(a_n)_{n\ge0}$ が $a_{n+2}=a_{n+1}+a_n$ を満たすことと、ある実数 $A,B$ によって $a_n=A\varphi^n+B\psi^n$($n\ge0$)と書けることは同値である。このとき
$$
A=\frac{a_1-\psi a_0}{\sqrt5},\qquad B=\frac{\varphi a_0-a_1}{\sqrt5}
$$
である。
$a_n=x^n$($x\ne0$)が漸化式を満たすのは、$x^{n+2}=x^{n+1}+x^n$、すなわち $x^2=x+1$ のとき、そのときに限る。よって $x=\varphi,\psi$ である。漸化式は線形なので、解の定数倍と和も解であり、$A\varphi^n+B\psi^n$ は解である。
逆に $(a_n)$ を解とし、$A,B$ を上の式で定める。$b_n:=A\varphi^n+B\psi^n$ とおくと
$$
b_0=A+B=\frac{(\varphi-\psi)a_0}{\sqrt5}=a_0,\qquad b_1=A\varphi+B\psi=\frac{(\varphi-\psi)a_1}{\sqrt5}=a_1
$$
である($b_1$ では $\varphi\psi$ の項が打ち消し合う)。$(a_n)$ と $(b_n)$ は最初の 2 項が等しく同じ漸化式を満たすので、帰納法で全項が一致する。この $A,B$ の値が唯一であることは、連立方程式 $A+B=a_0$、$A\varphi+B\psi=a_1$ の行列式 $\psi-\varphi$ が $0$ でないことによる。$\square$
$a_0=0$、$a_1=1$ とすると $A=1/\sqrt5$、$B=-1/\sqrt5$ となり、thm-bf-main が導かれる。これが特性方程式の方法である(Lev24 §4.4.3、pp. 356–358)。3 つの項の間の一般の漸化式は 三項間漸化式の特性方程式 で扱われている。
同じ式は別の 2 つの道からも導ける。どの道でも、$x^2-x-1$ の 2 根に分解することが要である。
| 方法 | $x^2-x-1$ の現れ方 | 所在 |
|---|---|---|
| 特性方程式 | 等比数列の解の条件 | lem-bf-general |
| 行列の対角化 | $\begin{pmatrix}1&1\\1&0\end{pmatrix}$ の固有多項式 | 漸化式の行列表示 の例「Fibonacci 数と Binet の公式」 |
| 母関数 | 分母 $1-x-x^2$ の因数分解 | Fibonacci数の母関数 の定理「Fibonacci 数の母関数と一般項」 |
なぜ整数になるのかは、$\varphi$ の冪の計算で見える。$\varphi^2=\varphi+1$ を繰り返し使うと、$\varphi^n=F_n\varphi+F_{n-1}$($n\ge1$)となり、$\psi^n=F_n\psi+F_{n-1}$ も同じである(黄金比 の命題「黄金比の基本的な等式」)。2 式を引くと $\varphi^n-\psi^n=F_n(\varphi-\psi)=\sqrt5F_n$ となって、thm-bf-main をもう一度得る。$\sqrt5$ で割れることは、差が $\varphi-\psi$ の整数倍であることの言い換えである。二項展開でも同じことが見える。
すべての $n\ge1$ について
$$
2^{n-1}F_n=\sum_{k\ge0}\binom n{2k+1}5^k=\binom n1+5\binom n3+5^2\binom n5+\cdots
$$
である。
$2^n\sqrt5F_n=(1+\sqrt5)^n-(1-\sqrt5)^n$ を二項定理で展開すると、$\sqrt5$ の偶数乗の項は打ち消し合い、奇数乗の項は 2 倍になる。$(\sqrt5)^{2k+1}=5^k\sqrt5$ なので、
$$
2^n\sqrt5F_n=2\sqrt5\sum_{k\ge0}\binom n{2k+1}5^k
$$
である。両辺を $2\sqrt5$ で割る。$\square$
$n=5$ では $16\cdot5=80=5+5\cdot10+25\cdot1$ である。この式は HW60 の (10.14.11)(p. 150)にある。右辺の形から、$n$ が素数 $p$ なら $\binom pj$ が $p$ で割れることを使って $F_p\equiv5^{(p-1)/2}\pmod p$($p$ は奇素数)も読める($2^{p-1}\equiv1$ を使う)。
$|\psi|< 1$ なので、thm-bf-main の第 2 項は急速に小さくなる。
すべての $n\ge0$ について、$F_n$ は $\varphi^n/\sqrt5$ に最も近い整数である。また、$n$ が偶数のとき $F_n< \varphi^n/\sqrt5$、$n$ が奇数のとき $F_n>\varphi^n/\sqrt5$ である。
thm-bf-main より $F_n-\dfrac{\varphi^n}{\sqrt5}=-\dfrac{\psi^n}{\sqrt5}$ である。右辺の絶対値は $\dfrac1{\sqrt5}< \dfrac12$ 以下なので、$F_n$ が最も近い整数である。符号は $\psi< 0$ から $\psi^n$ の符号で決まる。$\square$
| $n$ | $5$ | $6$ | $10$ | $11$ | $20$ |
|---|---|---|---|---|---|
| $\varphi^n/\sqrt5$ | $4.9597\ldots$ | $8.0249\ldots$ | $55.0036\ldots$ | $88.9977\ldots$ | $6765.00002\ldots$ |
| $F_n$ | $5$ | $8$ | $55$ | $89$ | $6765$ |
式で書くと $F_n=\bigl\lfloor\varphi^n/\sqrt5+\tfrac12\bigr\rfloor$ である。常用対数をとると、$n$ が大きいとき
$$
\log_{10}F_n\approx n\log_{10}\varphi-\log_{10}\sqrt5=0.20898\ldots\,n-0.34948\ldots
$$
である。たとえば $n=100$ では右辺は $20.549\ldots$ で、$F_{100}$ は $21$ 桁の数であり、実際 $F_{100}=354224848179261915075$ である。およそ $5$ 項ごとに桁が $1$ 増える。
逆に、Fibonacci 数の値から添字を求めることもできる。
$n\ge2$ のとき、$n$ は $\log_\varphi(\sqrt5F_n)$ に最も近い整数である。
thm-bf-main より $\sqrt5F_n=\varphi^n(1-\varepsilon)$、$\varepsilon:=(\psi/\varphi)^n$ である。$|\psi/\varphi|=\varphi^{-2}< 0.39$ なので、$n\ge2$ では $|\varepsilon|\le\varphi^{-4}< 0.15$ である。$\varphi^{1/2}=1.27\ldots$、$\varphi^{-1/2}=0.78\ldots$ より $\varphi^{-1/2}< 1-\varepsilon< \varphi^{1/2}$ だから、$\bigl|\log_\varphi(\sqrt5F_n)-n\bigr|=|\log_\varphi(1-\varepsilon)|< \frac12$ である。$\square$
$n=1$ は除く必要がある。$F_1=F_2=1$ なので、値 $1$ から添字は決まらない。
すべての $n\ge0$ について $F_{n+1}-\varphi F_n=\psi^n$ である。特に $n\ge1$ で
$$
\frac{F_{n+1}}{F_n}-\varphi=\frac{\psi^n}{F_n}
$$
であり、$F_{n+1}/F_n$ は $\varphi$ の上下に交互にきながら $\varphi$ に収束する。
thm-bf-main から
$$
\sqrt5(F_{n+1}-\varphi F_n)=\varphi^{n+1}-\psi^{n+1}-\varphi^{n+1}+\varphi\psi^n=\psi^n(\varphi-\psi)=\sqrt5\psi^n
$$
である。$n\ge1$ なら $F_n\ge1$ で割ると第 2 の式になる。$\psi< 0$ なので右辺の符号は交互に変わり、絶対値は $|\psi|^n$ 以下だから $0$ に近づく。$\square$
$F_n$ はほぼ $\varphi^n/\sqrt5$ なので、誤差の絶対値はほぼ $\sqrt5\,\varphi^{-2n}$ である。$1$ 項進むごとに誤差の絶対値はおよそ $\varphi^{-2}=0.38\ldots$ 倍になる。$n=10$ では $89/55-\varphi=0.000147\ldots$ で、これは $\psi^{10}/55$ に等しい。
同じ漸化式を別の初期値で解くと、lem-bf-general の $A,B$ が変わる。
$L_0=2$、$L_1=1$、$L_{n+2}=L_{n+1}+L_n$($n\ge0$)で定まる数 $2,1,3,4,7,11,18,29,\dots$ を Lucas 数 という。
lem-bf-general で $a_0=2$、$a_1=1$ とすると $A=(1-2\psi)/\sqrt5=1$、$B=(2\varphi-1)/\sqrt5=1$ なので、$L_n=\varphi^n+\psi^n$ である。
すべての $n\ge0$ について、次が成り立つ。
1:$\sqrt5F_{2n}=\varphi^{2n}-\psi^{2n}=(\varphi^n-\psi^n)(\varphi^n+\psi^n)=\sqrt5F_nL_n$ である。
2:$L_n^2-5F_n^2=(\varphi^n+\psi^n)^2-(\varphi^n-\psi^n)^2=4(\varphi\psi)^n=4(-1)^n$ である。
最後の主張:$|L_n-\varphi^n|=|\psi|^n\le\psi^2=0.38\ldots< \frac12$ による。$\square$
2 は HW60 の (10.14.7)(p. 149)で、Cassiniの恒等式 の系「Fibonacci数の判定法」の根にある式である。最後の主張から、$\varphi$ の高い冪は整数に近い。たとえば $\varphi^{20}=15126.99993\ldots$ で、$L_{20}=15127$ である。
漸化式 $F_n=F_{n+2}-F_{n+1}$ で添字を負の方へ伸ばすと、$F_{-1}=1$、$F_{-2}=-1$、$F_{-3}=2,\dots$ となる。$\varphi\psi=-1$ から $\varphi^{-1}=-\psi$、$\psi^{-1}=-\varphi$ なので、$G_n:=(\varphi^n-\psi^n)/\sqrt5$ は負の $n$ でも意味をもち、$G_{n+2}=G_{n+1}+G_n$ を満たす。よって thm-bf-main はすべての整数 $n$ で成り立つ。特に
$$
F_{-n}=\frac{(-\psi)^n-(-\varphi)^n}{\sqrt5}=(-1)^{n+1}F_n
$$
である(HW60 (10.14.5)、p. 148)。
thm-bf-main の証明で使ったのは、$x^2=x+1$ の異なる 2 根の差で割れることだけだった。したがって実数でなくても、標数が $2$、$5$ でなく $5$ の平方根がある体なら同じ公式が成り立つ。
$p$ を $2,5$ と異なる素数とし、整数 $s$ が $s^2\equiv5\pmod p$ を満たすとする。$\mathbb{F}_p$ の中で $a=\frac{1+s}2$、$b=\frac{1-s}2$ とおくと、すべての $n\ge0$ について
$$
F_n\equiv\frac{a^n-b^n}s\pmod p
$$
である。さらに $F_{n+p-1}\equiv F_n\pmod p$ であり、特に $p\mid F_{p-1}$ である。
$\mathbb{F}_p$ で $s^2=5\ne0$ なので $s$ は可逆である。$a^2=\frac{1+2s+5}4=\frac{3+s}2=a+1$ で、$b$ も同じである。よって $G_n:=(a^n-b^n)/s$ は $G_{n+2}=G_{n+1}+G_n$ を満たし、$G_0=0$、$G_1=(a-b)/s=1$ なので、$F_n$ の $\mathbb{F}_p$ での像と一致する。$ab=\frac{1-5}4=-1$ なので $a,b\ne0$ であり、Fermat の小定理から $a^{p-1}=b^{p-1}=1$ である。よって $G_{n+p-1}=G_n$ である。$n=0$ として $F_{p-1}\equiv F_0=0$ を得る。$\square$
$p=11$ では $4^2\equiv5$ なので $s=4$ ととれる。$\frac12\equiv6$ から $a\equiv30\equiv8$、$b\equiv-18\equiv4$ である。$\frac14\equiv3$ なので $F_n\equiv3(8^n-4^n)\pmod{11}$ である。$n=5$ では $8^5\equiv10$、$4^5\equiv1$ より $3\cdot9=27\equiv5=F_5$ である。また $F_{10}=55\equiv0$ である。
$s$ が存在するのは、平方剰余の相互法則により $p\equiv\pm1\pmod5$ のときである。HW60 Theorem 180(p. 150)はこの場合の $p\mid F_{p-1}$ を別の道で示している。$5$ が平方剰余でないときは $\mathbb{F}_p$ に根がなく、2 次の拡大の中で同じ計算をする。一般の 2 項の漸化式で環の中の公式を立てたものが Lucas擬素数 の補題「環 $A$ での Binet の公式」である。
| 変えること | 反例 | 成り立たなくなること |
|---|---|---|
| 四捨五入を切り捨てにする | $n=1$:$\varphi/\sqrt5=0.72\ldots$ | 切り捨ては $0$ で $F_1=1$ でない |
| 分子の符号を $+$ にする | $(\varphi+\psi)/\sqrt5=1/\sqrt5$ | 値は整数でない |
| 2 根が異なるという条件 | $a_{n+2}=2a_{n+1}-a_n$ | $a_n=n$ が $A\lambda^n+B\lambda^n$ の形でない |
| Lucas 数の $n\ge2$ | $n=1$:$\varphi=1.61\ldots$ | 最も近い整数は $2$ で $L_1=1$ でない |
「$F_n=\lfloor\varphi^n/\sqrt5\rfloor$」は $n$ が奇数のとき正しくない。cor-bf-nearest より $n$ が奇数なら $\varphi^n/\sqrt5< F_n$ で、差は $\frac12$ より小さい。また $\varphi^n/\sqrt5>F_n-\frac12$ なので、切り捨てると $F_n-1$ になる。たとえば $n=11$ で $\lfloor88.99\ldots\rfloor=88\ne89$ である。$n$ が偶数のときは、差が $1$ より小さいので切り捨てで正しい。
$a_{n+2}=2a_{n+1}-a_n$、$a_0=0$、$a_1=1$ の解は $a_n=n$ である。特性方程式 $x^2=2x-1$ は重解 $x=1$ をもつので、$A\cdot1^n+B\cdot1^n$ の形の数列は定数列に限り、$a_n=n$ を表せない。lem-bf-general で $\sqrt5=\varphi-\psi\ne0$ で割ったところが、この場合には $0$ で割ることになる。重解のときの形は 三項間漸化式の特性方程式 の定理「重解のときの一般項」にある。
Dickson の歴史書は、$v_{n+2}=v_{n+1}+r_nv_n$ の解の項数についての J. P. M. Binet の 1843 年の式を挙げ、各 $r_n$ を $1$ とすると Fibonacci 数の列になると述べている(Dic05 p. 394)。L. Euler が $(a+\sqrt b)^k=A_k+B_k\sqrt b$ の係数 $A_k,B_k$ について同じ形の式を記していることも、同書 p. 393 に挙げられている。E. Lucas は $2^n\sqrt5\,F_n=(1+\sqrt5)^n-(1-\sqrt5)^n$ の形で述べている(同書 p. 395)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する