Binetの公式(Fibonacci数)

同義語:ビネの公式(Fibonacci数)Binet's formula for Fibonacci numbersFibonacci数の一般項

概要

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 の公式とは別のものである。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 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 $$
を満たす。

Binet の公式

すべての $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$ に等しい。

Lucas 数

同じ漸化式を別の初期値で解くと、lem-bf-general の $A,B$ が変わる。

Lucas 数

$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$ である。

Fibonacci 数との関係

すべての $n\ge0$ について、次が成り立つ。

  1. $F_{2n}=F_nL_n$
  2. $L_n^2-5F_n^2=4(-1)^n$
    また $n\ge2$ のとき、$L_n$ は $\varphi^n$ に最も近い整数である。

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$ の公式

$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$

法 $11$ の場合

$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$ でない
反例:切り捨てでは奇数番目で 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アソシエイト)の紹介料で運営されています。 支援について / 寄付する