フィボナッチ数 (フィボナッチすう、英 : Fibonacci number )は、イタリア の数学者レオナルド・フィボナッチ (ピサのレオナルド)に因んで名付けられた数 である。
フィボナッチ数を一辺とする正方形
ウィキペディア日本語版 のメインページ (2007年 〜2012年 )で使われていたイメージ画像もフィボナッチ数列を利用していた[注釈 1] 。
フィボナッチ数列 ( フィボナッチすうれつ 、( 英 : Fibonacci sequence) (Fn ) は、次の漸化式 で定義される:
{
F
0
=
0
F
1
=
1
F
n
=
F
n
−
1
+
F
n
−
2
(
n
≧
2
)
{\displaystyle {\begin{cases}F_{0}=0&\,\\F_{1}=1&\,\\F_{n}=F_{n-1}+F_{n-2}&(n\geqq 2)\end{cases}}}
第0~22項の値は次の通りである:
0 , 1 , 1, 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , 377 , 610 , 987 , 1597, 2584, 4181, 6765 , 10946, 17711, …(オンライン整数列大辞典 の数列 A000045 )
1202年 にフィボナッチが発行した『算盤の書 』(Liber Abaci) に記載されたことで「フィボナッチ数」と呼ばれているが、それ以前にもインド の学者であるヘーマチャンドラ (Hemachandra) が韻律 の研究により発見し、書物に記したことが判明している[1] [2] 。
レオナルド・フィボナッチ は次の問題を考案した[3] 。
1つがいの兎は、産まれて2か月後から毎月1つがいずつの兎を産む。
兎が死ぬことはない。
この条件の下で、産まれたばかりの1つがいの兎は1年の間に何つがいの兎になるか?
つがいの数は次の表のようになる。どの月のつがいの合計も、その前の2つの月での合計の和となり、フィボナッチ数が現れていることが分かる。
さらに見る 産まれたばかりのつがい, 生後1か月のつがい ...
産まれたばかりのつがい 生後1か月のつがい 生後2か月以降のつがい つがいの数(合計)
0か月後
1 0 0 1
1か月後
0 1 0 1
2か月後
1 0 1 2
3か月後
1 1 1 3
4か月後
2 1 2 5
5か月後
3 2 3 8
6か月後
5 3 5 13
7か月後
8 5 8 21
8か月後
13 8 13 34
9か月後
21 13 21 55
10か月後
34 21 34 89
11か月後
55 34 55 144
12か月後
89 55 89 233
閉じる
フィボナッチ数列の一般項は次の式で表される[3] :
F
n
=
1
5
{
(
1
+
5
2
)
n
−
(
1
−
5
2
)
n
}
=
ϕ
n
−
(
1
−
ϕ
)
n
5
=
ϕ
n
−
(
−
ϕ
)
−
n
5
{\displaystyle F_{n}={\frac {1}{\sqrt {5}}}\left\{\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right\}={\frac {\phi ^{n}-(1-\phi )^{n}}{\sqrt {5}}}={\frac {\phi ^{n}-(-\phi )^{-n}}{\sqrt {5}}}}
この式は1843年 にビネ (Jacques Philippe Marie Binet ) が発表したことからビネの公式と呼ばれるが、それ以前の1730年 (ド・モアブル )・1765年 (オイラー )にも発表されており、ビネは最初の発見者ではない。
なお、この式に現れる
ϕ
=
1
+
5
2
=
1.618033988749894
⋯
{\displaystyle \phi ={\frac {1+{\sqrt {5}}}{2}}=1.618033988749894\cdots }
は黄金数 で、いくつかの数学的特徴がある。黄金数を作る二次方程式 x 2 − x − 1 = 0 の解を α , β (α > β ) とすると、上記の一般項は
F
n
=
α
n
−
β
n
α
−
β
=
α
n
α
−
β
+
β
n
β
−
α
{\displaystyle F_{n}={\frac {\alpha ^{n}-\beta ^{n}}{\alpha -\beta }}={\frac {\alpha ^{n}}{\alpha -\beta }}+{\frac {\beta ^{n}}{\beta -\alpha }}}
と表せる。
また、一般項の第2項 1 / √ 5 (− φ )− n の絶対値は減少列で、n = 0 のとき 1 / √ 5 = 0.447... < 1 / 2 より、第2項を切り捨てた式は Fn の値を 0.447 以下(n > 4 のとき1%以下)の誤差で与える近似式 である。
F
n
≒
ϕ
n
5
{\displaystyle F_{n}\fallingdotseq {\frac {\phi ^{n}}{\sqrt {5}}}}
この誤差の絶対値は0.5未満なので、Fn の正確な整数値は以下の式で得られる[3] 。
F
n
=
⌊
ϕ
n
5
+
1
2
⌋
=
⌊
1
5
(
1
+
5
2
)
n
+
1
2
⌋
{\displaystyle F_{n}=\left\lfloor {\frac {\phi ^{n}}{\sqrt {5}}}+{\frac {1}{2}}\right\rfloor =\left\lfloor {\frac {1}{\sqrt {5}}}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}+{\frac {1}{2}}\right\rfloor }
ただし、⌊ x ⌋ は床関数 である。
なお、後述の負数番への拡張 を考慮した場合、n < 0 では逆に一般項の第1項の絶対値が0.5未満となるため、n < 0 における Fn の正確な整数値は以下の式で得られる。
F
n
=
−
⌊
(
−
ϕ
)
−
n
5
+
1
2
⌋
=
−
⌊
1
5
(
1
−
5
2
)
n
+
1
2
⌋
{\displaystyle F_{n}=-\left\lfloor {\frac {(-\phi )^{-n}}{\sqrt {5}}}+{\frac {1}{2}}\right\rfloor =-\left\lfloor {\frac {1}{\sqrt {5}}}\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}+{\frac {1}{2}}\right\rfloor }
これらのことから、任意の整数 n における Fn の正確な整数値は以下の式で得られる。
F
n
=
(
sgn
n
)
⌊
{
(
sgn
n
)
ϕ
}
|
n
|
5
+
1
2
⌋
=
(
sgn
n
)
⌊
1
5
{
1
+
(
sgn
n
)
5
2
}
n
+
1
2
⌋
{\displaystyle F_{n}=(\operatorname {sgn} n)\left\lfloor {\frac {\{(\operatorname {sgn} n)\phi \}^{|n|}}{\sqrt {5}}}+{\frac {1}{2}}\right\rfloor =(\operatorname {sgn} n)\left\lfloor {\frac {1}{\sqrt {5}}}\left\{{\frac {1+(\operatorname {sgn} n){\sqrt {5}}}{2}}\right\}^{n}+{\frac {1}{2}}\right\rfloor }
ただし、sgn x は符号関数 である。
行列表現
また、フィボナッチ数列の漸化式は次のように行列 表現できる[3] :
[
F
n
+
1
F
n
]
=
[
1
1
1
0
]
[
F
n
F
n
−
1
]
,
[
F
n
F
n
−
1
]
=
[
1
1
1
0
]
[
F
n
−
1
F
n
−
2
]
{\displaystyle {\begin{bmatrix}F_{n+1}\\F_{n}\end{bmatrix}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}{\begin{bmatrix}F_{n}\\F_{n-1}\end{bmatrix}},\;\;{\begin{bmatrix}F_{n}\\F_{n-1}\end{bmatrix}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}{\begin{bmatrix}F_{n-1}\\F_{n-2}\end{bmatrix}}}
これらを並べて表記すると、
[
F
n
+
1
F
n
F
n
F
n
−
1
]
=
[
1
1
1
0
]
[
F
n
F
n
−
1
F
n
−
1
F
n
−
2
]
=
[
1
1
1
0
]
2
[
F
n
−
1
F
n
−
2
F
n
−
2
F
n
−
3
]
=
⋯
=
[
1
1
1
0
]
n
[
F
1
F
0
F
0
F
−
1
]
=
[
1
1
1
0
]
n
[
1
0
0
1
]
{\displaystyle {\begin{aligned}{\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}}&={\begin{bmatrix}1&1\\1&0\end{bmatrix}}{\begin{bmatrix}F_{n}&F_{n-1}\\F_{n-1}&F_{n-2}\end{bmatrix}}\\&={\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{2}{\begin{bmatrix}F_{n-1}&F_{n-2}\\F_{n-2}&F_{n-3}\end{bmatrix}}\\&=\cdots \\&={\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}{\begin{bmatrix}F_{1}&F_{0}\\F_{0}&F_{-1}\end{bmatrix}}\\&={\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}{\begin{bmatrix}1&0\\0&1\end{bmatrix}}\end{aligned}}}
∴
[
F
n
+
1
F
n
F
n
F
n
−
1
]
=
[
1
1
1
0
]
n
{\displaystyle \therefore {\begin{aligned}{\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}\end{aligned}}}
ここで、F − 1 = 1 は、漸化式 Fn = F n − 1 + F n − 2 に n = 1 を代入すると得られる(詳細は後述の負数番への拡張 を参照)。
更に、n を 2n で置換すると、
[
F
2
n
+
1
F
2
n
F
2
n
F
2
n
−
1
]
=
[
1
1
1
0
]
2
n
=
(
[
1
1
1
0
]
n
)
2
=
[
F
n
+
1
F
n
F
n
F
n
−
1
]
2
=
[
F
n
2
+
F
n
+
1
2
(
F
n
−
1
+
F
n
+
1
)
F
n
(
F
n
−
1
+
F
n
+
1
)
F
n
F
n
−
1
2
+
F
n
2
]
{\displaystyle {\begin{aligned}{\begin{bmatrix}F_{2n+1}&F_{2n}\\F_{2n}&F_{2n-1}\end{bmatrix}}&={\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{2n}=\left({\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}\right)^{2}={\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}}^{2}\\&={\begin{bmatrix}{F_{n}}^{2}+{F_{n+1}}^{2}&(F_{n-1}+F_{n+1})F_{n}\\(F_{n-1}+F_{n+1})F_{n}&{F_{n-1}}^{2}+{F_{n}}^{2}\end{bmatrix}}\end{aligned}}}
よって、
F
2
n
+
1
=
F
n
2
+
F
n
+
1
2
F
2
n
=
(
F
n
−
1
+
F
n
+
1
)
F
n
=
(
2
F
n
−
1
+
F
n
)
F
n
=
(
2
F
n
+
1
−
F
n
)
F
n
F
2
n
−
1
=
F
n
−
1
2
+
F
n
2
{\displaystyle {\begin{aligned}F_{2n+1}&={F_{n}}^{2}+{F_{n+1}}^{2}\\F_{2n}&=(F_{n-1}+F_{n+1})F_{n}=(2F_{n-1}+F_{n})F_{n}=(2F_{n+1}-F_{n})F_{n}\\F_{2n-1}&={F_{n-1}}^{2}+{F_{n}}^{2}\end{aligned}}}
母関数 は
g
(
x
)
=
∑
n
=
0
∞
F
n
x
n
=
x
1
−
x
−
x
2
{\displaystyle g(x)=\sum \limits _{n=0}^{\infty }F_{n}x^{n}={\dfrac {x}{1-x-x^{2}}}}
である。
また、この行列表現を基に、以下のような漸化式を考えることが出来る。
{
F
0
=
0
F
1
=
1
F
n
=
F
q
2
+
{
1
+
(
−
1
)
n
}
F
q
−
1
F
q
+
1
−
(
−
1
)
n
2
F
q
+
1
2
(
n
≧
2
,
q
=
⌊
n
2
⌋
)
{\displaystyle {\begin{cases}F_{0}=0&\,\\F_{1}=1&\,\\F_{n}={F_{q}}^{2}+\{1+(-1)^{n}\}F_{q-1}F_{q}+{\dfrac {1-(-1)^{n}}{2}}{F_{q+1}}^{2}&\left(n\geqq 2,\;q=\left\lfloor {\dfrac {n}{2}}\right\rfloor \right)\end{cases}}}
フィボナッチ数列の隣接2項の商は黄金数 φ に収束する。この性質は初期値 (F 0 = 0, F 1 = 1 ) に依らない。
lim
n
→
∞
F
n
F
n
−
1
=
ϕ
{\displaystyle \lim _{n\to \infty }{\frac {F_{n}}{F_{n-1}}}=\phi }
これは次のように導出される:
x
=
lim
n
→
∞
F
n
F
n
−
1
{\displaystyle x=\lim _{n\to \infty }{\frac {F_{n}}{F_{n-1}}}}
が収束するとすれば、
x
=
lim
n
→
∞
F
n
−
1
+
F
n
−
2
F
n
−
1
=
lim
n
→
∞
(
1
+
1
F
n
−
1
/
F
n
−
2
)
=
1
+
1
x
{\displaystyle x=\lim _{n\to \infty }{\frac {F_{n-1}+F_{n-2}}{F_{n-1}}}=\lim _{n\to \infty }\left(1+{\frac {1}{F_{n-1}/F_{n-2}}}\right)=1+{\frac {1}{x}}}
x
2
−
x
−
1
=
0
{\displaystyle x^{2}-x-1=0}
自然数 p , q の最大公約数 を r とすると、Fp と Fq の最大公約数は Fr である。
これより以下を導くことができる。
m が n で割り切れるならば、Fm は Fn で割り切れる。
連続する2数は互いに素 であることより、隣り合うフィボナッチ数も互いに素である。
Fm が偶数 となるのは m が 3 の倍数となるときと一致する。
Fm が 5 の倍数 となるのは m が 5 の倍数となるときと一致する。
p が 2 でも 5 でもない素数 のとき、m = p − (5/p ) とおくと p は Fm を割り切る。ここで ( / ) はルジャンドル記号 である。
フィボナッチ数の累和や累積について以下の式が成り立つ。
F 1 + F 2 + F 3 + … + Fn = F n +2 − 1
F 1 + F 3 + F 5 + … + F 2n − 1 = F 2n
F 2 + F 4 + F 6 + … + F 2n = F 2n +1 − 1
F 1 2 + F 2 2 + F 3 2 + … + Fn 2 = Fn F n +1
F n − 1 F n +1 − Fn 2 = (− 1)n
また、次の関係式が知られている。
∑
k
=
1
∞
F
k
n
k
=
n
n
2
−
n
−
1
{\displaystyle \sum _{k=1}^{\infty }{\frac {F_{k}}{n^{k}}}={\frac {n}{n^{2}-n-1}}}
フィボナッチ数のうち平方数 であるのは F 1 = F 2 = 1 , F 12 = 144 のみ (Cohn 1964)[4] 、立方数 であるのは F 1 = F 2 = 1 , F 6 = 8 のみ (London and Finkelstein 1969)[5] である。フィボナッチ数のうち累乗数 であるのはこれしかない (Bugeaud, Mignotte, Siksek 2006)[6] 。(オンライン整数列大辞典 の数列 A227875 )
フィボナッチ数で素数 であるのは 2 , 3 , 5 , 13 , 89 , 233 , 1597, 28657, … である(オンライン整数列大辞典 の数列 A005478 )。また、これらはフィボナッチ素数 と呼ばれる。
フィボナッチ数で三角数 であるのは 1 , 3 , 21 , 55 (オンライン整数列大辞典 の数列 A039595 )のみであることは Vern Hoggatt によって予想されていたが、のちに Luo Ming によって証明された[7] 。
フィボナッチ数でハーシャッド数 であるのは 1 , 2 , 3 , 5 , 8 , 21 , 144 , 2584, …(オンライン整数列大辞典 の数列 A117774 )。
フィボナッチ数は完全数 にはならない[8] 。より一般に、フィボナッチ数は倍積完全数 にもならず[9] 、2つのフィボナッチ数の商も完全数にはならない[10] 。
フィボナッチ数列の逆数和 は収束し、記号 ψ で表される。
ψ
=
∑
n
=
1
∞
1
F
n
=
1
1
+
1
1
+
1
2
+
1
3
+
⋯
=
3.35988566
⋯
{\displaystyle \psi =\sum _{n=1}^{\infty }{\frac {1}{F_{n}}}={\frac {1}{1}}+{\frac {1}{1}}+{\frac {1}{2}}+{\frac {1}{3}}+\cdots =3.35988566\cdots }
[11]
この ψ が無理数であることは証明されているが (André-Jeannin 1989)、超越数 であるかどうかは分かっていない。
任意の正の整数は、1つ以上の連続しない相異なるフィボナッチ数の和として一意に表すことができる(ゼッケンドルフの定理 )。
再帰 的処理の例としてよく紹介される。以下はPython での例。
ただし、下記実装例の内、#負数番への拡張 に対応しているのは例5・例6のみである。
例1(再帰的処理による実装例)
このプログラムでは、n が与えられてから Fn が求まるまでに Fn ∝ φn 回の関数呼び出しが発生する(すなわち指数時間 の計算となる)ため、実用的ではない。したがって通常は、線形時間 で計算するためにメモ化 などの手法を用いる他、後述するように様々な実装例が検討されている。
def fib ( n : int ) -> int :
if n < 2 :
return n
else :
return fib ( n = n - 1 ) + fib ( n = n - 2 )
メモ化の例を挙げると[注釈 2] 、
from functools import cache
@cache
def fib ( n : int ) -> int :
if n < 2 :
return n
else :
return fib ( n = n - 1 ) + fib ( n = n - 2 )
例2(ループ処理による実装例)
def fib ( n : int ) -> int :
a , b = 1 , 0
for _ in range ( n ):
a , b = b , a + b
return b
例3(指数関数的なコールを必要としない再帰的処理による実装例)
n が1以上の場合に第2・第3の引数を上記例2と同じ要領で順次更新していくことで、コール回数を n 回に抑えられる為、線形時間で処理出来る。
def fib ( n : int , a : int = 1 , b : int = 0 ) -> int :
if n == 0 :
return b
else :
return fib ( n = n - 1 , a = b , b = a + b )
例4(対数時間での再帰的処理による実装例)
#行列表現 で導出した漸化式 (以下に再掲)を用いることで、再帰的処理でも対数時間で処理出来る。
{
F
0
=
0
F
1
=
1
F
n
=
F
q
2
+
{
1
+
(
−
1
)
n
}
F
q
−
1
F
q
+
1
−
(
−
1
)
n
2
F
q
+
1
2
(
n
≧
2
,
q
=
⌊
n
2
⌋
)
{\displaystyle {\begin{cases}F_{0}=0&\,\\F_{1}=1&\,\\F_{n}={F_{q}}^{2}+\{1+(-1)^{n}\}F_{q-1}F_{q}+{\dfrac {1-(-1)^{n}}{2}}{F_{q+1}}^{2}&\left(n\geqq 2,\;q=\left\lfloor {\dfrac {n}{2}}\right\rfloor \right)\end{cases}}}
ただし、プログラム上は0を掛けるからと言ってその対象の値が計算されない訳では無い為(短絡評価 されない)、条件式 による分岐で表記している。
def fib ( n : int ) -> int :
if n < 2 :
return n
q = n // 2
fq = fib ( n = q )
return fq ** 2 + ( 2 * fib ( n = q - 1 ) * fq if n % 2 == 0 else fib ( n = q + 1 ) ** 2 )
例5(一般項による実装例)
浮動小数点 型を使用すると計算誤差 が発生する為、decimal
モジュールを用いている[注釈 3] 。
from decimal import Decimal
SQRT5 = Decimal ( 5 ) . sqrt ()
PHI = ( 1 + SQRT5 ) / 2 # 黄金数
def fib ( n : int ) -> int :
return round (( PHI ** n - ( - PHI ) ** - n ) / SQRT5 )
なお、先述の通りフィボナッチ数列の一般項は、引数 n の符号によって2項の内いずれかが0.5未満となることから、符号関数 及び床関数 を用いて以下のように表すことが出来た。
F
n
=
(
sgn
n
)
⌊
{
(
sgn
n
)
ϕ
}
|
n
|
5
+
1
2
⌋
{\displaystyle F_{n}=(\operatorname {sgn} n)\left\lfloor {\frac {\{(\operatorname {sgn} n)\phi \}^{|n|}}{\sqrt {5}}}+{\frac {1}{2}}\right\rfloor }
(#一般項 より再掲)
このことから、以下のように実装することで冪乗 演算の回数を減らすことが出来る[注釈 4] 。
from decimal import Decimal
ONE = Decimal ( 1 )
SQRT5 = Decimal ( 5 ) . sqrt ()
PHI = ( 1 + SQRT5 ) / 2 # 黄金数
def fib ( n : int ) -> int :
if n == 0 :
return 0
sgn_n = ONE . copy_sign ( n )
return sgn_n * round (( sgn_n * PHI ) ** abs ( n ) / SQRT5 )
例6(行列表現での実装例)
[
F
n
+
1
F
n
F
n
F
n
−
1
]
=
[
1
1
1
0
]
n
{\displaystyle {\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}}
(#行列表現 より再掲)
より、n を n − 1 に置換すると、
[
F
n
F
n
−
1
F
n
−
1
F
n
−
2
]
=
[
1
1
1
0
]
n
−
1
{\displaystyle {\begin{bmatrix}F_{n}&F_{n-1}\\F_{n-1}&F_{n-2}\end{bmatrix}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n-1}}
従って、Fn は、上式右辺(の具体的な計算値)の左上成分に等しい。
行列の冪 を簡潔に記述する為にSymPy を用いた[注釈 5] [注釈 6] 。
{{Syntaxhighlight|lang=python|code=
from sympy import Matrix
def fib(n: int) -> int:
return (Matrix([[1, 1], [1, 0]]) ** (n - 1))[0, 0] # 左上成分
}}
ヒマワリの種は螺旋状に並んでおり、螺旋の数を数えていくとフィボナッチ数が現れる[12]
フィボナッチ数は自然 界の現象に数多く出現する。
また、フィボナッチ数列が生み出す螺旋は、世界で最も美しい螺旋だと言われている。
ヨハネス・ケプラー は1611年に発表した小論文「新年の贈り物あるいは六角形の雪について」において、フィボナッチ数を自己を増殖する比例と呼び、植物の種子の能力の現れであると論じた[13] 。
花びら の数はフィボナッチ数であることが多い。[ 要出典 ]
フィボナッチ数は、花びらの枚数も決めているらしい。(『聖なる幾何学』p63より)
アブラナ やダイコン の花びら は4枚であり、植物学 では花式図 より3数性、4数性、5数性で分類される[15] [16] 。
植物 の花 や実 に現れる螺旋 の数もフィボナッチ数であることが多い。
ヒマワリ の螺旋の数はフィボナッチ数とされることもあるが、螺旋の数が多い場合、中心から離れると螺旋の隙間にも種ができてしまうため、途中から枝分かれしてフィボナッチ数にならないこともある[17] 。
パイナップル の螺旋の数は時計回りは13、反時計回りは8になっている。
葉序 (植物の葉の付き方)はフィボナッチ数と関連している。(シンパー=ブラウンの法則)
らせん葉序におけるシンパー・ブラウンの法則はフィボナッチ数列と関連するが、「近似値を示すにすぎず、またこれにあてはまらない例もある」(岩波生物学辞典)。
ハチ やアリ など、オスに父親がない家系を辿っていくとフィボナッチ数列が現れる(父母2匹、祖父母3匹、曽祖父母5匹、高祖父母8匹…)。
n 段の階段を1段または2段ずつ登るときに、登る場合の数は F n +1 通りある。
●と○を合わせて n 個並べる。●が2個以上続かないように一列に並べる方法は F n +2 通りある。
為替 などのテクニカル分析 で、フィボナッチ・リトレースメント という手法がよく使われている。
フィボナッチ数列は、漸化式 Fn = F n − 1 + F n − 2 を全ての整数 n に対して適用することにより、n が負の整数の場合に拡張できる。そして F − n = (− 1)n +1Fn が成り立つ。この式より、負の番号の項は次のようになる。
さらに見る n, Fn ...
n
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Fn
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
F− n
0 1 − 12 − 35 − 813 − 2134 − 5589 − 144233 − 377610 − 9871597 − 25844181 − 6765
閉じる
フィボナッチ数列の定義である初期値や漸化式をやや変更して、類似の数列が作れる。
項数の変更
フィボナッチ数列は各項が先行する二項の和であるものであったが、それを「先行する k 項の和」と置き換えた一般化
F
n
+
k
(
k
)
:=
F
n
+
k
−
1
(
k
)
+
F
n
+
k
−
2
(
k
)
+
⋯
+
F
n
(
k
)
(
n
≥
0
)
{\displaystyle F_{n+k}^{(k)}:=F_{n+k-1}^{(k)}+F_{n+k-2}^{(k)}+\dotsb +F_{n}^{(k)}\quad (n\geq 0)}
を考えることができる。ただし、初期値は 1 で埋める(1-fil型)
F
0
(
k
)
=
F
1
(
k
)
=
⋯
=
F
k
−
1
(
k
)
=
1
{\displaystyle F_{0}^{(k)}=F_{1}^{(k)}=\dotsb =F_{k-1}^{(k)}=1}
あるいは 0 で埋める(0-fil型)
F
0
(
k
)
=
F
1
(
k
)
=
⋯
=
F
k
−
2
(
k
)
=
0
,
F
k
−
1
(
k
)
=
1
{\displaystyle F_{0}^{(k)}=F_{1}^{(k)}=\dotsb =F_{k-2}^{(k)}=0,\quad F_{k-1}^{(k)}=1}
などを取るのが一般的である。これらフィボナッチ数列の類似物を、項数 k に対応するラテン語またはギリシャ語に由来する倍数接頭辞 を「フィボナッチ」と組み合わせた名称で呼ぶ[注釈 7] 。
トリボナッチ数
特に直前の三項の和として各項が定まるトリボナッチ数列は、フィボナッチ数列に次いでよく調べられている。0-fil型でオフセットが0番目からのものは
T 0 = T 1 = 0, T 2 = 1,
T n +3 = Tn + T n +1 + T n +2 (n ≥ 0)
と表される。第0~21項の値は次の通りである:
0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, … (OEIS A000073 )
トリボナッチ数列の一般項は次で表される。
T
n
=
α
n
(
α
−
β
)
(
α
−
γ
)
+
β
n
(
β
−
γ
)
(
β
−
α
)
+
γ
n
(
γ
−
α
)
(
γ
−
β
)
{\displaystyle T_{n}={\frac {\alpha ^{n}}{(\alpha -\beta )(\alpha -\gamma )}}+{\frac {\beta ^{n}}{(\beta -\gamma )(\beta -\alpha )}}+{\frac {\gamma ^{n}}{(\gamma -\alpha )(\gamma -\beta )}}}
ただし、α , β , γ は三次方程式 x 3 − x 2 − x − 1 = 0 の3解
α
=
1
3
(
1
+
19
−
3
33
3
+
19
+
3
33
3
)
β
=
1
3
(
1
+
ω
19
−
3
33
3
+
ω
¯
19
+
3
33
3
)
γ
=
1
3
(
1
+
ω
¯
19
−
3
33
3
+
ω
19
+
3
33
3
)
{\displaystyle {\begin{aligned}\alpha &={\frac {1}{3}}\left(1+{\sqrt[{3}]{19-3{\sqrt {33}}}}+{\sqrt[{3}]{19+3{\sqrt {33}}}}\right)\\\beta &={\frac {1}{3}}\left(1+\omega {\sqrt[{3}]{19-3{\sqrt {33}}}}+{\bar {\omega }}{\sqrt[{3}]{19+3{\sqrt {33}}}}\right)\\\gamma &={\frac {1}{3}}\left(1+{\bar {\omega }}{\sqrt[{3}]{19-3{\sqrt {33}}}}+\omega {\sqrt[{3}]{19+3{\sqrt {33}}}}\right)\end{aligned}}}
であり、ここで
ω
=
−
1
+
3
i
2
{\displaystyle \omega ={\frac {-1+{\sqrt {3}}i}{2}}}
(1 の虚立方根 )
である。
また、上記の α をトリボナッチ定数 という。これはフィボナッチ数列における黄金数に当たる定数で、トリボナッチ数列の隣接2項間の商はトリボナッチ定数に収束する:
lim
n
→
∞
T
n
T
n
−
1
=
α
=
1.839286755214161
⋯
{\displaystyle \lim _{n\to \infty }{\frac {T_{n}}{T_{n-1}}}=\alpha =1.839286755214161\cdots }
テトラナッチ数
直前の四項の和に変更したテトラナッチ数列も同様に様々なことが知られている。同様にオフセット0番の 0-fil型は
T 0 = T 1 = T 2 = 0, T 3 = 1,
T n +4 = Tn + T n +1 + T n +2 + T n +3 (n ≥ 0)
と書けて、第0~21項の値は次の通りである:
0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, … (OEIS A000078 )
一般項は、四次方程式 x 4 − x 3 − x 2 − x − 1 = 0 の4解を α , β , γ , δ として、
T
n
=
α
n
(
α
−
β
)
(
α
−
γ
)
(
α
−
δ
)
+
β
n
(
β
−
γ
)
(
β
−
δ
)
(
β
−
α
)
+
γ
n
(
γ
−
δ
)
(
γ
−
α
)
(
γ
−
β
)
+
δ
n
(
δ
−
α
)
(
δ
−
β
)
(
δ
−
γ
)
{\displaystyle T_{n}={\frac {\alpha ^{n}}{(\alpha -\beta )(\alpha -\gamma )(\alpha -\delta )}}+{\frac {\beta ^{n}}{(\beta -\gamma )(\beta -\delta )(\beta -\alpha )}}+{\frac {\gamma ^{n}}{(\gamma -\delta )(\gamma -\alpha )(\gamma -\beta )}}+{\frac {\delta ^{n}}{(\delta -\alpha )(\delta -\beta )(\delta -\gamma )}}}
となる。
初期値の変更
リュカ数
フィボナッチ数列の最初の2項を 2, 1 に置き換えた数列の項をリュカ数 という。
2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, … (OEIS A000032 )
この数列の一般項は
L
n
=
(
1
+
5
2
)
n
+
(
1
−
5
2
)
n
=
ϕ
n
+
(
1
−
ϕ
)
n
=
ϕ
n
+
(
−
ϕ
)
−
n
{\displaystyle L_{n}=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}+\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}=\phi ^{n}+(1-\phi )^{n}={\phi ^{n}+(-\phi )^{-n}}}
と表される。
フィボナッチ数列やリュカ数の列を一般化したものがリュカ数列 であり、1878年にエドゥアール・リュカ が体系的な研究を行い、1913年にロバート・ダニエル・カーマイケル (英語版 ) がその結果を整理、拡張した[19] 。これらの研究が現代のフィボナッチ数の理論の基礎となった。
注釈
この例では(メモ化の為の)キャッシュ サイズが無制限に肥大する。 decimal
モジュールの計算精度に依る制約はある(デフォルトでは十進 28桁(二進 93ビット 相当))。便宜上0の0乗 が何らかの定数(プログラミング言語では0の0乗を1とすることが多く、Pythonにおいてもint
型やfloat
型で0の0乗を計算した場合は1が返される)を取るものとすれば、上記の式は0を含む任意の整数 n について成り立つ。ただし、decimal
型で0の0乗を計算するとエラーとなる為、コード上は n = 0 の場合を予め除外している。 SymPy は、フィボナッチ数を求める関数を自前で持っているが、ここでは使ってない。計算速度は、行列の冪 を計算する手法に依存する。幸いにしてSymPy のそれは、素朴な方法(冪の数だけ行列を乗算する)よりは速い。 当然のことだが "Fibonacci" は人名であって、"fibo-" + "-nacci" や "fi-" + "-bonacci" という構成の合成語でもないし、もちろん "fi-" や "fibo-" が "2 " の意味を持つわけでもない(ただし、摩擦音 f と破裂音 b が音韻的に近い関係にあることから 2 を表す "bi-" を "fi-" に結び付けての類推ではあるかもしれない)が、「フィボナッチ」の語を頭から適当な音節分だけ倍数を表す接頭辞で置き換えるという、冗談のような名付け になっている。
出典
Parmanand Singh. "Acharya Hemachandra and the (so called) Fibonacci Numbers". Math. Ed. Siwan, 20(1) : pp. 28–30, 1986. ISSN 0047-6269.
Parmanand Singh, "The So-called Fibonacci numbers in ancient and medieval India." Historia Mathematica 12(3) , pp. 229–244, 1985.
J. H. E. Cohn, On square Fibonacci numbers, J. London Math. Soc. 39 (1964), pp. 537–540.
London, Hymie; Finkelstein, Raphael (1969), “On Fibonacci and Lucas numbers which are perfect powers”, Fibonacci Quart. 7 (5): 476-481, Part1 , Part2 , Correction Yann Bugeaud, Maurice Mignotte, Samir Siksek, Classical and modular approaches to exponential Diophantine equations. I. Fibonacci and Lucas perfect powers. Ann. of Math. 163 (2006), pp. 969–1018. Yann Bugeaud, Publications, 2006. 榎本恵美子 (1977). “翻訳・新年の贈り物あるいは六角形の雪について”. 知の考古学 第11号 : 286ページ.
聖なる幾何学 スティーヴン・スキナー著 p.63「植物成長の幾何学」より抜粋
R. D. Carmichael, On the numerical factors of the arithmetic forms α n ± β n , Ann. of Math. 15 (1913), pp.30–70, doi : 10.2307/1967797 .
佐藤修一 『自然にひそむ数学―自然と数学の不思議な関係』講談社 〈ブルーバックス B-1201〉、1998年1月20日。ISBN 4-06-257201-X 。
中村滋 『フィボナッチ数の小宇宙(ミクロコスモス)―フィボナッチ数、リュカ数、黄金分割』日本評論社 、2002年9月。ISBN 4-535-78281-4 。
中村滋「日本フィボナッチ協会の20年」『数学セミナー』第57巻第8号、日本評論社、2018年8月、48-53頁。
Arakelian, Hrant (2014) (ロシア語), Mathematics and History of the Golden Section , Logos, ISBN 978-5-98704-663-0
Dunlap, Richard A. (1997-12-17), The Golden Ratio and Fibonacci Numbers , World Scientific Pub. Co. Inc., ISBN 978-981-02-3264-1
Koshy, Thomas (2017-12-04), Fibonacci and Lucas Numbers with Applications , Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts, Volume 1 (2nd ed.), Wiley, ISBN 978-1-118-74212-9
Koshy, Thomas (2019-01-07), Fibonacci and Lucas Numbers with Applications , Pure and Applied Mathematics: A Wiley Series of Texts, Monographs and Tracts, Volume 2 (2nd ed.), Wiley, ISBN 978-1-118-74208-2
Leonardo Pisano Fibonacci L. E. Sigler訳 (1987-02-11), The Book of Squares , Academic Press, ISBN 978-0-12-643130-8 - 『平方の書 』の英訳。
Sigler, Laurence (2003-11-11), Fibonacci's Liber Abaci: A Translation into Modern English of Leonardo Pisano's Book of Calculation , Sources and Studies in the History of Mathematics and Physical Sciences, Springer-Verlag, ISBN 978-0-387-40737-1 - 『算盤の書 』の英訳。
ウィキメディア・コモンズには、
フィボナッチ数 に関連するカテゴリがあります。