フィボナッチ数列

数学において、フィボナッチ数列は、各数がその前の2つの数の和である数列である。フィボナッチ数列の一部である数はフィボナッチ数列と呼ばれ、一般的にはF _n と表記される。多くの著者は数列を0と1から始めるが、1と1から始める著者もいる^{[1] [2]。}また、フィボナッチのように1と2から始める著者もいる。0と1から数列が始まる^[3]

0、1、1、2、3、5、8、13、21、34、55、89、144、...。

フィボナッチ数は紀元前200年頃、ピンガラによる2つの長さの音節からなるサンスクリット詩の可能なパターンを列挙した著作の中で、インドの数学で初めて記述されました。 ^{[4] [5] [6]}フィボナッチ数は、1202年に著書『算盤の書』で西ヨーロッパの数学にこの数列を導入したイタリアの数学者、フィボナッチにちなんで名付けられました。^[7]

フィボナッチ数は数学において意外に頻繁に登場し、その研究を専門とする雑誌「フィボナッチ・クォータリー」があるほどである。フィボナッチ数の応用には、フィボナッチ探索法やフィボナッチ・ヒープ・ データ構造などのコンピュータ・アルゴリズムや、並列システムや分散システムを相互接続するために使用されるフィボナッチ・キューブと呼ばれるグラフがある。また、木の枝分かれ、茎の葉の配置、パイナップルの果実の芽、アーティチョークの開花、松ぼっくりの苞葉の配置など、生物学的な状況にも現れるが、すべての種に現れるわけではない。

フィボナッチ数は黄金比とも深い関係があります。ビネの公式はn番目のフィボナッチ数をnと黄金比で表し、連続する 2 つのフィボナッチ数の比はnが増加するにつれて黄金比に近づくことを示しています。フィボナッチ数はルーカス数とも密接な関係があり、ルーカス数も同じ再帰関係に従い、フィボナッチ数とともにルーカス数列の補完的なペアを形成します。

フィボナッチ数は、 n > 1 の場合の再帰関係^[8] によって定義される。 $${\displaystyle F_{0}=0,\quad F_{1}=1,}$$$${\displaystyle F_{n}=F_{n-1}+F_{n-2}$$

いくつかの古い定義では値が省略されており、シーケンスはから始まり、再帰はn > 2に対して有効です。^{[9] [10]}${\displaystyle F_{0}=0}$${\displaystyle F_{1}=F_{2}=1,}$${\displaystyle F_{n}=F_{n-1}+F_{n-2}$

最初の20個のフィボナッチ数列F _nは以下の通りである: ^[3]

フィボナッチ数列は、インドの数学において、サンスクリットの韻律と関連して登場する。^{[5] [11] [12]}サンスクリットの詩の伝統では、持続時間が 2 単位の長い (L) 音節と持続時間が 1 単位の短い (S) 音節を並置したすべてのパターンを列挙することに関心があった。与えられた合計持続時間で連続する L と S のさまざまなパターンを数えると、フィボナッチ数列が得られる。持続時間がm単位のパターンの数はF _{m +1}である。^[6]

フィボナッチ数列の知識は、ピンガラ（紀元前 450年頃～紀元前200年頃）の時代にはすでに存在していた。シンは、ピンガラの謎の公式ミスラウ・チャ（「2つは混ざっている」）と、それを文脈から解釈して、 m拍（F _{m +1} ）のパターンの数は、F _mの場合に1つの [S] を、 F _{m −1 の}場合に1つの [L] を加えることで得られると解釈する学者を引用している。 ^[13] バラタ・ムニも、ナティヤ・シャーストラ（紀元前100年頃～紀元後350年頃）の中で、この数列の知識を述べている。^{[14] [4]しかし、この数列の最も明確な説明は、}ヴィラハンカ​​（紀元後700年頃） の著作に見られる。ヴィラハンカ​​の著作は失われているが、ゴパーラ（紀元後1135年頃）の引用で入手可能である。^[12]

2 つの前の拍子の変化 [が変化です] ... たとえば、長さが 4 の拍子の場合、2 と 3 の拍子の変化が混ざると、5 になります。[例 8、13、21 を解決します] ... この方法は、すべてのmātrā-vṛttas [韻律の組み合わせ] で従う必要があります。^[a]

ヘマチャンドラ（1150年頃）もこの順序を知っていたとされ、^[4]「最後のものとその前のものを足したものが、次のマートラ・ヴリッタの数である」と書いている。^{[16] [17]}

フィボナッチ数列は、フィボナッチの著書『算盤の書』 （1202年）^{[18] [19]}で初めて登場し、ウサギの個体数の増加を計算するために使用されています。^{[20] [21]フィボナッチは、理想的な（}生物学的に非現実的な）ウサギの個体数の増加を考察し、次のような仮定を立てました。生まれたばかりのウサギの繁殖ペアを野原に置きます。繁殖ペアはそれぞれ生後1か月で交尾し、2か月目の終わりには必ずもう1組のウサギを生みます。ウサギは決して死ぬことなく、永遠に繁殖し続けます。フィボナッチはウサギの数学の問題を提起しました。1年間に何組のペアが存在するでしょうか？

• 最初の月の終わりに交尾しますが、まだペアは 1 つだけです。
• 2 か月目の終わりには新しいペアが生まれるので、フィールドには 2 組のペアが存在することになります。
• 3 か月目の終わりに、最初のペアは 2 番目のペアを産みますが、2 番目のペアは妊娠期間が 1 か月だけなので、ペアは全部で 3 つになります。
• 4 か月目の終わりには、最初のペアがさらに別の新しいペアを産み、2 か月前に生まれたペアも最初のペアを産み、ペアは 5 つになります。

n月の終わりには、ウサギのつがいの数は、成熟したつがいの数（つまり、n – 2月のつがいの数）と、前月（ n – 1月）に生存していたつがいの数を加えた数に等しくなります。n月の数は、n番目のフィボナッチ数です。 ^[22]

「フィボナッチ数列」という名前は、19世紀の数論学者エドゥアール・リュカスによって初めて使用されました。^[23]

定数係数を持つ同次線形回帰によって定義されるすべての数列と同様に、フィボナッチ数列は閉じた形式の表現を持つ。^{[24]これはフランスの数学者}ジャック・フィリップ・マリー・ビネにちなんでビネの公式として知られるようになったが、アブラアン・ド・モアブルとダニエル・ベルヌーイによってすでに知られていた。^[25]

$${\displaystyle F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}={\frac {\varphi ^{n}-\psi ^{ n}}{\sqrt {5}}},}$$

どこ

$${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1.61803\,39887\ldots }$$

は黄金比であり、ψはその共役比である：^[26]

$${\displaystyle \psi ={\frac {1-{\sqrt {5}}}{2}}=1-\varphi =-{1 \over \varphi }\approx -0.61803\,39887\ldots .}$$

なので、この式は次のようにも書ける。 ${\displaystyle \psi =-\varphi ^{-1}}$

$${\displaystyle F_{n}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{\sqrt {5}}}={\frac {\varphi ^{n}- (-\varphi )^{-n}}{2\varphi -1}}.}$$

数列とこれらの定数の関係を見るために、^[27] φとψは両方とも方程式の解であり、したがってφとψの累乗はフィボナッチ再帰を満たすことに留意してください。言い換えれば、 ${\textstyle x^{2}=x+1}$${\displaystyle x^{n}=x^{n-1}+x^{n-2},}$

$${\displaystyle {\begin{aligned}\varphi ^{n}&=\varphi ^{n-1}+\varphi ^{n-2},\\[3mu]\psi ^{n}&=\psi ^{n-1}+\psi ^{n-2}.\end{整列}}}$$

任意の 値aとbに対して、

$${\displaystyle U_{n}=a\varphi ^{n}+b\psi ^{n}}$$

同じ繰り返しを満たす、

$${\displaystyle {\begin{aligned}U_{n}&=a\varphi ^{n}+b\psi ^{n}\\[3mu]&=a(\varphi ^{n-1}+\varphi ^{n-2})+b(\psi ^{n-1}+\psi ^{n-2})\\[3mu]&=a\varphi ^{n-1}+b\psi ^{n-1}+a\varphi ^{n-2}+b\psi ^{n-2}\\[3mu]&=U_{n-1}+U_{n-2}.\end{整列しました}}}$$

aとb がU ₀ = 0かつU ₁ = 1となるように選択される場合、結果のシーケンスU _{n は}フィボナッチ数列でなければなりません。これは、 aとb が次の方程式系を満たすこと を要求するのと同じです。

$${\displaystyle \left\{{\begin{aligned}a+b&=0\\\varphi a+\psi b&=1\end{aligned}}\right.}$$

解決策がある

$${\displaystyle a={\frac {1}{\varphi -\psi }}={\frac {1}{\sqrt {5}}},\quad b=-a,}$$

必要な式を生成します。

開始値U ₀とU ₁を任意の定数とすると、より一般的な解は次のようになります。

$${\displaystyle U_{n}=a\varphi ^{n}+b\psi ^{n}}$$

どこ

$${\displaystyle {\begin{aligned}a&={\frac {U_{1}-U_{0}\psi}{\sqrt {5}}},\\[3mu]b&={\frac {U_{0}\varphi -U_{1}}{\sqrt {5}}}.\end{aligned}}}$$

すべてのn ≥ 0に対して 、数F _{n は}に最も近い整数です。したがって、最も近い整数関数を使用してを丸めることで見つけることができます。 ${\textstyle \left|{\frac {\psi ^{n}}{\sqrt {5}}}\right|<{\frac {1}{2}}}$${\displaystyle {\frac {\varphi ^{n}}{\sqrt {5}}}}$$${\displaystyle F_{n}=\left\lfloor {\frac {\varphi ^{n}}{\sqrt {5}}}\right\rceil ,\ n\geq 0.}$$

実際、丸め誤差はn が大きくなるにつれて急速に小さくなり、 n ≥ 4では 0.1 未満、n ≥ 8では 0.01 未満になります。この式を逆にすると、フィボナッチ数Fのインデックスを簡単に見つけることができます。 $${\displaystyle n(F)=\left\lfloor \log _{\varphi }{\sqrt {5}}F\right\rceil ,\ F\geq 1.}$$

代わりに床関数を使用すると、 Fより大きくないフィボナッチ数列の最大指数が得られます。 ここで、、、^[28]、および^[29]です。$${\displaystyle n_{\mathrm {largest} }(F)=\left\lfloor \log _{\varphi }{\sqrt {5}}(F+1/2)\right\rfloor ,\ F\geq 0,}$$${\displaystyle \log _{\varphi }(x)=\ln(x)/\ln(\varphi )=\log _{10}(x)/\log _{10}(\varphi )}$${\displaystyle \ln(\varphi )=0.481211\ldots }$${\displaystyle \log_{10}(\varphi)=0.208987\ldots }$

F _{n は}に漸近するため、F _nの桁数は に漸近します。結果として、すべての整数d > 1に対して、小数点 以下d桁のフィボナッチ数は 4 つまたは 5 つ存在します。${\displaystyle \varphi ^{n}/{\sqrt {5}}}$${\displaystyle n\log_{10}\varphi \approx 0.2090\,n}$

より一般的には、基数 bの表現では、 F _nの桁数は漸近的に${\displaystyle n\log _{b}\varphi ={\frac {n\log \varphi }{\log b}}.}$

ヨハネス・ケプラーは、連続するフィボナッチ数の比率が収束することを観察した。彼は「5と8の比率は、8と13の比率とほぼ同じであり、8と13の比率は、13と21の比率とほぼ同じである」と記し、これらの比率は黄金比に近づくと結論付けた^{[30] [31]。}${\displaystyle \varphi \colon }$ $${\displaystyle \lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}=\varphi .}$$

この収束は、 でない限り、開始値と に関係なく成立します。これは、ビネの公式を使用して検証できます。たとえば、初期値 3 と 2 は、シーケンス 3、2、5、7、12、19、31、50、81、131、212、343、555、... を生成します。このシーケンスの連続する項の比は、黄金比に向かって同様に収束していることを示しています。 ${\displaystyle U_{0}}$${\displaystyle U_{1}}$${\displaystyle U_{1}=-U_{0}/\varphi }$

一般に、連続するフィボナッチ数列間の比率は に近づくため、 となります。 ${\displaystyle \lim _{n\to \infty }{\frac {F_{n+m}}{F_{n}}}=\varphi ^{m}}$${\displaystyle \varphi }$

黄金比は次の式を満たすので $${\displaystyle \varphi ^{2}=\varphi +1,}$$

この式は、高次のべき乗を低次のべき乗の線形関数として分解するのに使用でき、これは、と1の線形結合まで分解できます。結果として生じる再帰関係は、線形係数としてフィボナッチ数をもたらします。 この式は、 n ≥ 1の帰納法によって証明 できます。 の場合、また、また、 ${\displaystyle \varphi ^{n}}$${\displaystyle \varphi }$$${\displaystyle \varphi ^{n}=F_{n}\varphi +F_{n-1}.}$$$${\displaystyle \varphi ^{n+1}=(F_{n}\varphi +F_{n-1})\varphi =F_{n}\varphi ^{2}+F_{n-1}\varphi =F_{n}(\varphi +1)+F_{n-1}\varphi =(F_{n}+F_{n-1})\varphi +F_{n}=F_{n+1}\varphi +F_{n}.}$$${\displaystyle \psi =-1/\varphi }$${\displaystyle \psi ^{2}=\psi +1}$$${\displaystyle \psi ^{n}=F_{n}\psi +F_{n-1}.}$$

これらの式は、フィボナッチ数列F _{n が}フィボナッチの法則を用いて負の整数に拡張された場合、 n < 1に対しても成り立ちます。${\displaystyle F_{n}=F_{n+2}-F_{n+1}.}$

ビネの公式は、正の整数xがフィボナッチ数であるためには、またはの少なくとも一方が完全な平方数である場合に限るという証明を与えている。^[32]これは、 と書くことができるビネの公式に を掛けて、の二次方程式として解くことができるためである。 ${\displaystyle 5x^{2}+4}$${\displaystyle 5x^{2}-4}$${\displaystyle F_{n}=(\varphi ^{n}-(-1)^{n}\varphi ^{-n})/{\sqrt {5}}}$${\displaystyle {\sqrt {5}}\varphi ^{n}}$${\displaystyle \varphi ^{n}}$

$${\displaystyle \varphi ^{n}={\frac {F_{n}{\sqrt {5}}\pm {\sqrt {5{F_{n}}^{2}+4(-1)^{n}}}}{2}}.}$$

これをと比較すると、 ${\displaystyle \varphi ^{n}=F_{n}\varphi +F_{n-1}=(F_{n}{\sqrt {5}}+F_{n}+2F_{n-1})/2}$

$${\displaystyle 5{F_{n}}^{2}+4(-1)^{n}=(F_{n}+2F_{n-1})^{2}\,.}$$

特に、左側は完全な正方形です。

フィボナッチ数列を記述する 2次元線形差分方程式系は

$${\displaystyle {F_{k+2} \choose F_{k+1}}={\begin{pmatrix}1&1\\1&0\end{pmatrix}}{F_{k+1} \choose F_{k}}}$$ あるいは表記される $${\displaystyle {\vec {F}}_{k+1}=\mathbf {A} {\vec {F}}_{k},}$$

となる。行列Aの固有値は、それぞれの固有ベクトルに対応する。${\displaystyle {\vec {F}}_{n}=\mathbf {A} ^{n}{\vec {F}}_{0}}$ ${\displaystyle \varphi ={\tfrac {1}{2}}{\bigl (}1+{\sqrt {5}}~\!{\bigr )}}$${\displaystyle \psi =-\varphi ^{-1}={\tfrac {1}{2}}{\bigl (}1-{\sqrt {5}}~\!{\bigr )}}$ $${\displaystyle {\vec {\mu }}={\varphi \choose 1},\quad {\vec {\nu }}={-\varphi ^{-1} \choose 1}.}$$

初期値は $${\displaystyle {\vec {F}}_{0}={1 \choose 0}={\frac {1}{\sqrt {5}}}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}{\vec {\nu }},}$$

すると、n番目の項は $${\displaystyle {\begin{aligned}{\vec {F}}_{n}&={\frac {1}{\sqrt {5}}}A^{n}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}A^{n}{\vec {\nu }}\\&={\frac {1}{\sqrt {5}}}\varphi ^{n}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}(-\varphi )^{-n}{\vec {\nu }}\\&={\cfrac {1}{\sqrt {5}}}\left({\cfrac {1+{\sqrt {5}}}{2}}\right)^{\!n}{\varphi \choose 1}\,-\,{\cfrac {1}{\sqrt {5}}}\left({\cfrac {1-{\sqrt {5}}}{2}}\right)^{\!n}{-\varphi ^{-1} \choose 1}.\end{aligned}}}$$

このことから、フィボナッチ数列のn番目の要素は、閉じた形式の式として直接読み取ることができます。 $${\displaystyle F_{n}={\cfrac {1}{\sqrt {5}}}\left({\cfrac {1+{\sqrt {5}}}{2}}\right)^{\!n}-\,{\cfrac {1}{\sqrt {5}}}\left({\cfrac {1-{\sqrt {5}}}{2}}\right)^{\!n}.}$$

同様に、Aの固有値分解を使ってAを対角化することでも同じ計算が実行できます。

$${\displaystyle {\begin{aligned}A&=S\Lambda S^{-1},\\[3mu]A^{n}&=S\Lambda ^{n}S^{-1},\end{aligned}}}$$

どこ

$${\displaystyle \Lambda ={\begin{pmatrix}\varphi &0\\0&-\varphi ^{-1}\!\end{pmatrix}},\quad S={\begin{pmatrix}\varphi &-\varphi ^{-1}\\1&1\end{pmatrix}}.}$$

したがって、フィボナッチ数列の n番目の要素の閉じた表現は次のように表される。

$${\displaystyle {\begin{aligned}{F_{n+1} \choose F_{n}}&=A^{n}{F_{1} \choose F_{0}}\\&=S\Lambda ^{n}S^{-1}{F_{1} \choose F_{0}}\\&=S{\begin{pmatrix}\varphi ^{n}&0\\0&(-\varphi )^{-n}\end{pmatrix}}S^{-1}{F_{1} \choose F_{0}}\\&={\begin{pmatrix}\varphi &-\varphi ^{-1}\\1&1\end{pmatrix}}{\begin{pmatrix}\varphi ^{n}&0\\0&(-\varphi )^{-n}\end{pmatrix}}{\frac {1}{\sqrt {5}}}{\begin{pmatrix}1&\varphi ^{-1}\\-1&\varphi \end{pmatrix}}{1 \choose 0},\end{aligned}}}$$

再び $${\displaystyle F_{n}={\cfrac {\varphi ^{n}-(-\varphi )^{-n}}{\sqrt {5}}}.}$$

行列Aの行列式は−1なので、2×2ユニモジュラ行列となります。

この性質は黄金比φの連分数表現によって理解できる。

$${\displaystyle \varphi =1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+\ddots }}}}}}.}$$

φの連分数の収束は、連続するフィボナッチ数列の比である。φ _n = F _{n +1} / F _{n は}n番目の収束であり、( n  + 1)番目の収束は、再帰関係φ _{n +1} = 1 + 1 / φ _nから求められる。^[33]任意の連分数の連続する収束から形成される行列は、+1 または -1 の行列式を持つ。行列表現は、フィボナッチ数列の次の閉じた形式の表現を与える。

$${\displaystyle {\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n}={\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}}.}$$

与えられたnに対して、この行列は、二乗法による累乗法を使用して、 O (log n ) 回の算術演算で計算できます。

この式の両辺の行列式をとるとカッシーニの恒等式が得られる。 $${\displaystyle (-1)^{n}=F_{n+1}F_{n-1}-{F_{n}}^{2}.}$$

さらに、任意の正方行列Aに対してA ⁿ A ^m = A ^{n + m で}あるため、次の恒等式が導かれます（これらは行列積の2つの異なる係数から得られ、 n をn + 1に変更することで最初の係数から2番目の係数を簡単に導くことができます）。 $${\displaystyle {\begin{aligned}{F_{m}}{F_{n}}+{F_{m-1}}{F_{n-1}}&=F_{m+n-1},\\[3mu]F_{m}F_{n+1}+F_{m-1}F_{n}&=F_{m+n}.\end{aligned}}}$$

特に、m = nの場合、 $${\displaystyle {\begin{aligned}F_{2n-1}&={F_{n}}^{2}+{F_{n-1}}^{2}\\[6mu]F_{2n{\phantom {{}-1}}}&=(F_{n-1}+F_{n+1})F_{n}\\[3mu]&=(2F_{n-1}+F_{n})F_{n}\\[3mu]&=(2F_{n+1}-F_{n})F_{n}.\end{aligned}}}$$

これら最後の2つの恒等式は、 O (log n )回の演算でフィボナッチ数列を再帰的に計算する方法を提供します。これは、閉じた形式の行列式からn番目のフィボナッチ数列を計算する時間と一致しますが、すでに計算されたフィボナッチ数列を再計算することを避ければ冗長なステップが少なくなります（メモ化による再帰）。^[34]

フィボナッチ数列を含むほとんどの恒等式は、が となるような 1 と 2 の（空の可能性もある）シーケンスの数として解釈できるという事実を用いた組合せ論的議論によって証明できます。これは、という規則、つまり、合計が −1 となるシーケンスは存在しないこと、 という規則、つまり、空シーケンスを「足すと」 0 になることを意味する、での定義としてとらえることができます。以下では、集合の濃度は です。 ${\displaystyle F_{n}}$${\displaystyle n-1}$${\displaystyle F_{n}}$${\displaystyle F_{0}=0}$${\displaystyle F_{1}=1}$${\displaystyle |{...}|}$

${\displaystyle F_{0}=0=|\{\}|}$

${\displaystyle F_{1}=1=|\{()\}|}$

${\displaystyle F_{2}=1=|\{(1)\}|}$

${\displaystyle F_{3}=2=|\{(1,1),(2)\}|}$

${\displaystyle F_{4}=3=|\{(1,1,1),(1,2),(2,1)\}|}$

${\displaystyle F_{5}=5=|\{(1,1,1,1),(1,1,2),(1,2,1),(2,1,1),(2,2)\}|}$

このように、 すべてのシーケンスが 1 または 2 で始まる 2 つの重複しないセットにシーケンスを 分割することによって、再帰関係を理解できます。 最初の要素を除いて、各シーケンスの残りの項の合計はまたはになり、各セットの濃度はまたはとなり、シーケンスの合計は になり、これが に等しいことがわかります。 $${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$$${\displaystyle F_{n}}$$${\displaystyle F_{n}=|\{(1,...),(1,...),...\}|+|\{(2,...),(2,...),...\}|}$$${\displaystyle n-2}$${\displaystyle n-3}$${\displaystyle F_{n-1}}$${\displaystyle F_{n-2}}$${\displaystyle F_{n-1}+F_{n-2}}$${\displaystyle F_{n}}$

同様に、最初のフィボナッチ数からn番目までの和は、 ( n +2)番目のフィボナッチ数から1を引いた値に等しいことが示される。 ^[35] 記号で表すと、 $${\displaystyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1}$$

これは、最初の 2 つの位置に基づいて、合計するすべてのシーケンスを分割することで確認できます。具体的には、各セットは、それぞれ基数 1 の最後の 2 つのセットまで始まるシーケンスで構成されます。 ${\displaystyle n+1}$${\displaystyle (2,...),(1,2,...),...,}$${\displaystyle \{(1,1,...,1,2)\},\{(1,1,...,1)\}}$

先ほどと同じ論理に従って、各集合の濃度を合計すると、次のようになります。

${\displaystyle F_{n+2}=F_{n}+F_{n-1}+...+|\{(1,1,...,1,2)\}|+|\{(1,1,...,1)\}|}$

...ここで、最後の 2 つの項の値は です。このことから、 という式が成り立ちます。 ${\displaystyle F_{1}=1}$${\displaystyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1}$

同様の議論で、最初の 2 ではなく最初の 1 の位置で合計をグループ化すると、さらに 2 つの恒等式が得られます。 および 言葉で言えば、奇数指数 の最初のフィボナッチ数から までの和は(2 n )番目のフィボナッチ数であり、偶数指数の最初のフィボナッチ数から までの和は(2 n + 1)番目のフィボナッチ数から 1 を引いた数です。 ^[36]$${\displaystyle \sum _{i=0}^{n-1}F_{2i+1}=F_{2n}}$$$${\displaystyle \sum _{i=1}^{n}F_{2i}=F_{2n+1}-1.}$$${\displaystyle F_{2n-1}}$${\displaystyle F_{2n}}$

別のトリックを使って証明することもできます 。つまり、 までの最初のフィボナッチ数の平方の合計は、 n番目と( n + 1)番目のフィボナッチ数の積です。これを確認するには、 サイズのフィボナッチ長方形から始めて、 サイズの平方に分解します。これにより、面積を比較することで等式が導かれます。 $${\displaystyle \sum _{i=1}^{n}F_{i}^{2}=F_{n}F_{n+1}}$$${\displaystyle F_{n}}$${\displaystyle F_{n}\times F_{n+1}}$${\displaystyle F_{n},F_{n-1},...,F_{1}}$

数列は記号法を用いても考察される。^[37]より正確には、この数列は指定可能な組合せクラスに対応する。この数列の指定はである。確かに、上で述べたように、数列フィボナッチ数は項1と2を使用したの組合せ合成（順序付けられた分割）の数に等しい。 ${\displaystyle (F_{n})_{n\in \mathbb {N} }}$${\displaystyle \operatorname {Seq} ({\mathcal {Z+Z^{2}}})}$${\displaystyle n}$${\displaystyle n-1}$

フィボナッチ数列の通常の生成関数は有理関数である。${\displaystyle \sum _{i=0}^{\infty }F_{i}z^{i}}$ ${\displaystyle {\frac {z}{1-z-z^{2}}}.}$

フィボナッチ等式は、多くの場合、数学的帰納法を使って簡単に証明できます。

例えば、 両辺を 足すと次のようになる。$${\displaystyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1.}$$${\displaystyle F_{n+1}}$

${\displaystyle \sum _{i=1}^{n}F_{i}+F_{n+1}=F_{n+1}+F_{n+2}-1}$

そして次の式が得られます${\displaystyle n+1}$ $${\displaystyle \sum _{i=1}^{n+1}F_{i}=F_{n+3}-1}$$

同様に、の両辺に 足す と、 ${\displaystyle {F_{n+1}}^{2}}$$${\displaystyle \sum _{i=1}^{n}F_{i}^{2}=F_{n}F_{n+1}}$$$${\displaystyle \sum _{i=1}^{n}F_{i}^{2}+{F_{n+1}}^{2}=F_{n+1}\left(F_{n}+F_{n+1}\right)}$$ $${\displaystyle \sum _{i=1}^{n+1}F_{i}^{2}=F_{n+1}F_{n+2}}$$

ビネの公式は、 フィボナッチ数列を証明するために使用できます。 $${\displaystyle {\sqrt {5}}F_{n}=\varphi ^{n}-\psi ^{n}.}$$

たとえば、 事実と方程式を簡略 化して、 左辺に を掛けると必要なようになること に注意することを証明します。${\textstyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1}$${\displaystyle {\sqrt {5}}}$$${\displaystyle {\begin{aligned}1+&\varphi +\varphi ^{2}+\dots +\varphi ^{n}-\left(1+\psi +\psi ^{2}+\dots +\psi ^{n}\right)\\&={\frac {\varphi ^{n+1}-1}{\varphi -1}}-{\frac {\psi ^{n+1}-1}{\psi -1}}\\&={\frac {\varphi ^{n+1}-1}{-\psi }}-{\frac {\psi ^{n+1}-1}{-\varphi }}\\&={\frac {-\varphi ^{n+2}+\varphi +\psi ^{n+2}-\psi }{\varphi \psi }}\\&=\varphi ^{n+2}-\psi ^{n+2}-(\varphi -\psi )\\&={\sqrt {5}}(F_{n+2}-1)\\\end{aligned}}}$$${\textstyle \varphi \psi =-1}$${\textstyle \varphi -\psi ={\sqrt {5}}}$

他にも様々な方法で数多くのアイデンティティを導き出すことができます。そのいくつかを次に示します。^[38]

カッシーニの恒等式は、 カタランの恒等式が一般化したものであると述べています。 $${\displaystyle {F_{n}}^{2}-F_{n+1}F_{n-1}=(-1)^{n-1}}$$$${\displaystyle {F_{n}}^{2}-F_{n+r}F_{n-r}=(-1)^{n-r}{F_{r}}^{2}}$$

$${\displaystyle F_{m}F_{n+1}-F_{m+1}F_{n}=(-1)^{n}F_{m-n}}$$ $${\displaystyle F_{2n}={F_{n+1}}^{2}-{F_{n-1}}^{2}=F_{n}\left(F_{n+1}+F_{n-1}\right)=F_{n}L_{n}}$$ ここで、L _{n は}n番目のルーカス数です。最後のものはn を2 倍にした時の恒等式です。このタイプの他の恒等式は カッシーニの恒等式によって表されます。 $${\displaystyle F_{3n}=2{F_{n}}^{3}+3F_{n}F_{n+1}F_{n-1}=5{F_{n}}^{3}+3(-1)^{n}F_{n}}$$

$${\displaystyle F_{3n+1}={F_{n+1}}^{3}+3F_{n+1}{F_{n}}^{2}-{F_{n}}^{3}}$$ $${\displaystyle F_{3n+2}={F_{n+1}}^{3}+3{F_{n+1}}^{2}F_{n}+{F_{n}}^{3}}$$ $${\displaystyle F_{4n}=4F_{n}F_{n+1}\left({F_{n+1}}^{2}+2{F_{n}}^{2}\right)-3{F_{n}}^{2}\left({F_{n}}^{2}+2{F_{n+1}}^{2}\right)}$$これらは格子縮小法 を使って実験的に見つけることができ、フィボナッチ数を 因数分解するための特殊数体ふるいを設定する際に役立ちます。

より一般的には、^[38]

$${\displaystyle F_{kn+c}=\sum _{i=0}^{k}{k \choose i}F_{c-i}{F_{n}}^{i}{F_{n+1}}^{k-i}.}$$

あるいは

$${\displaystyle F_{kn+c}=\sum _{i=0}^{k}{k \choose i}F_{c+i}{F_{n}}^{i}{F_{n-1}}^{k-i}.}$$

この式にk = 2 を代入すると、上記セクションの最後の行列形式の式が再び得られます。

フィボナッチ数列の生成関数は冪級数である。

$${\displaystyle s(z)=\sum _{k=0}^{\infty }F_{k}z^{k}=0+z+z^{2}+2z^{3}+3z^{4}+5z^{5}+\dots .}$$

この級数は任意の複素数 に対して収束し、その和は単純な閉形式を持つ: ^[39]${\displaystyle z}$${\displaystyle |z|<1/\varphi ,}$

$${\displaystyle s(z)={\frac {z}{1-z-z^{2}}}.}$$

これは を掛け合わせることで証明できます: ${\textstyle (1-z-z^{2})}$$${\displaystyle {\begin{aligned}(1-z-z^{2})s(z)&=\sum _{k=0}^{\infty }F_{k}z^{k}-\sum _{k=0}^{\infty }F_{k}z^{k+1}-\sum _{k=0}^{\infty }F_{k}z^{k+2}\\&=\sum _{k=0}^{\infty }F_{k}z^{k}-\sum _{k=1}^{\infty }F_{k-1}z^{k}-\sum _{k=2}^{\infty }F_{k-2}z^{k}\\&=0z^{0}+1z^{1}-0z^{1}+\sum _{k=2}^{\infty }(F_{k}-F_{k-1}-F_{k-2})z^{k}\\&=z,\end{aligned}}}$$

ここで、 を含むすべての項は、定義するフィボナッチ再帰関係により打ち消されます 。${\displaystyle z^{k}}$${\displaystyle k\geq 2}$

部分分数分解は、 が黄金比、 がその共役で あるで与えられます 。 $${\displaystyle s(z)={\frac {1}{\sqrt {5}}}\left({\frac {1}{1-\varphi z}}-{\frac {1}{1-\psi z}}\right)}$$${\textstyle \varphi ={\tfrac {1}{2}}\left(1+{\sqrt {5}}\right)}$${\displaystyle \psi ={\tfrac {1}{2}}\left(1-{\sqrt {5}}\right)}$

関連する関数は、負のフィボナッチ数の生成関数であり、関数方程式を満たす。${\textstyle z\mapsto -s\left(-1/z\right)}$${\displaystyle s(z)}$

$${\displaystyle s(z)=s\!\left(-{\frac {1}{z}}\right).}$$

0.01、0.001、0.0001 などに等しいを使用すると、 の 10 進展開の最初のフィボナッチ数列が表示されます。たとえば、${\displaystyle z}$${\displaystyle s(z)}$${\displaystyle s(0.001)={\frac {0.001}{0.998999}}={\frac {1000}{998999}}=0.001001002003005008013021\ldots .}$

フィボナッチ数の逆数の無限和は、シータ関数で評価できる場合があります。たとえば、奇数添字のフィボナッチ数の逆数の合計は次のように表すことができます。 $${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{F_{2k-1}}}={\frac {\sqrt {5}}{4}}\;\vartheta _{2}\!\left(0,{\frac {3-{\sqrt {5}}}{2}}\right)^{2},}$$

そしてフィボナッチ数の逆数の二乗の和は $${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{{F_{k}}^{2}}}={\frac {5}{24}}\!\left(\vartheta _{2}\!\left(0,{\frac {3-{\sqrt {5}}}{2}}\right)^{4}-\vartheta _{4}\!\left(0,{\frac {3-{\sqrt {5}}}{2}}\right)^{4}+1\right).}$$

最初の合計の各フィボナッチ数に1を加えると、閉じた形式も存在します。 $${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{1+F_{2k-1}}}={\frac {\sqrt {5}}{2}},}$$

そして、フィボナッチ数の二乗の和が入れ子になっていて、黄金比の逆数を与える。 $${\displaystyle \sum _{k=1}^{\infty }{\frac {(-1)^{k+1}}{\sum _{j=1}^{k}{F_{j}}^{2}}}={\frac {{\sqrt {5}}-1}{2}}.}$$

すべての偶数指数逆数フィボナッチ数の和は^[40] ランバート級数 で表され、$${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{F_{2k}}}={\sqrt {5}}\left(L(\psi ^{2})-L(\psi ^{4})\right)}$$ ${\displaystyle \textstyle L(q):=\sum _{k=1}^{\infty }{\frac {q^{k}}{1-q^{k}}},}$${\displaystyle \textstyle {\frac {1}{F_{2k}}}={\sqrt {5}}\left({\frac {\psi ^{2k}}{1-\psi ^{2k}}}-{\frac {\psi ^{4k}}{1-\psi ^{4k}}}\right)\!.}$

したがって、フィボナッチ定数の逆数は^[41]である。 $${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{F_{k}}}=\sum _{k=1}^{\infty }{\frac {1}{F_{2k-1}}}+\sum _{k=1}^{\infty }{\frac {1}{F_{2k}}}=3.359885666243\dots }$$

さらに、この数はリチャード・アンドレ・ジャンナンによって無理数であることが証明されている。 ^[42]

ミリン級数は、Nが無限大に近づく につれて部分和の閉じた形式から従う恒等式^[43] を与える。 $${\displaystyle \sum _{k=0}^{\infty }{\frac {1}{F_{2^{k}}}}={\frac {7-{\sqrt {5}}}{2}},}$$$${\displaystyle \sum _{k=0}^{N}{\frac {1}{F_{2^{k}}}}=3-{\frac {F_{2^{N}-1}}{F_{2^{N}}}}.}$$

数列の3番目ごとには偶数（ の倍数）であり、より一般的には、数列のk番目ごとにはF _kの倍数です。したがって、フィボナッチ数列は割り切れる数列の例です。実際、フィボナッチ数列はより強い割り切れる性質^{[44] [45]}を満たしており 、ここでgcdは最大公約数関数です。 ${\displaystyle F_{3}=2}$ $${\displaystyle \gcd(F_{a},F_{b},F_{c},\ldots )=F_{\gcd(a,b,c,\ldots )}\,}$$

特に、連続する3つのフィボナッチ数は、と の両方が互いに素であるため、互いに素である。つまり、 ${\displaystyle F_{1}=1}$${\displaystyle F_{2}=1}$

${\displaystyle \gcd(F_{n},F_{n+1})=\gcd(F_{n},F_{n+2})=\gcd(F_{n+1},F_{n+2})=1}$

すべてのnに対して。

すべての素数 p は、p を 5で割った値で決まるフィボナッチ数を割り切れます。p が5 を法として 1 または 4 と合同な場合、p はF _{p −1}で割り切れます。また、p が5 を法として 2 または 3 と合同な場合、p はF _{p +1 で}割り切れます。 残りのケースはp = 5の場合で、この場合はp はF _pで割り切れます。

$${\displaystyle {\begin{cases}p=5&\Rightarrow p\mid F_{p},\\p\equiv \pm 1{\pmod {5}}&\Rightarrow p\mid F_{p-1},\\p\equiv \pm 2{\pmod {5}}&\Rightarrow p\mid F_{p+1}.\end{cases}}}$$

これらのケースは、ルジャンドル記号を使用して、単一の非区分式にまとめることができます。 [ ^46] $${\displaystyle p\mid F_{p\;-\,\left({\frac {5}{p}}\right)}.}$$

上記の式は素数判定に使用できる。つまり、 ルジャンドル記号をヤコビ記号 に置き換えた場合、これはnが素数であることの証拠であり、それが成り立たない場合、n は間違いなく素数ではない。n が合成数で式を満たす場合、nはフィボナッチ擬素数である。m が大きい場合、たとえば 500 ビットの数値の場合、行列形式を使用して F m (mod n )_を効率的に計算できる。したがって、$${\displaystyle n\mid F_{n\;-\,\left({\frac {5}{n}}\right)},}$$

$${\displaystyle {\begin{pmatrix}F_{m+1}&F_{m}\\F_{m}&F_{m-1}\end{pmatrix}}\equiv {\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{m}{\pmod {n}}.}$$ ここで行列のべき乗Am^はべき乗剰余法を使用して計算され、これは行列に適応することができる。^[47]

フィボナッチ素数とは、素数であるフィボナッチ数である。最初のいくつかは以下の通りである: ^[48]

2、3、5、13、89、233、1597、28657、514229、...

数千桁のフィボナッチ素数は発見されているが、無限に存在するかどうかは分かっていない。^[49]

F _{kn は}F _nで割り切れるので、 F ₄ = 3を除いて、すべてのフィボナッチ素数は素数指数を持つ必要があります。合成数には任意の長さの連続があるため、合成フィボナッチ数にも任意の長さの連続が存在します。

F6 =8より大きいフィボナッチ数は素数より1大きいか1小さいことはない_。 [ ^50]

唯一の非自明な平方フィボナッチ数は144である。 ^{[51] Attila Pethőは2001年に}完全累乗フィボナッチ数 は有限個しか存在しないことを証明した。 ^[52] 2006年に、Y. Bugeaud、M. Mignotte、S. Siksekは8と144がそのような非自明な完全累乗数であることを証明した。^[53]

1、3、21、55は唯一の三角形のフィボナッチ数であり、これはヴァーン・ホガットによって推測され、羅明によって証明された。^[54]

フィボナッチ数は完全数にはなり得ない。^[55]より一般的には、1以外のフィボナッチ数は完全数にはなり得ず、^[56] 2つのフィボナッチ数の比は完全数にはなり得ない。^[57]

1、8、144（F ₁ = F ₂、F ₆、F ₁₂）を除いて、すべてのフィボナッチ数には、それより小さいフィボナッチ数の因数ではない素因数があります（カーマイケルの定理）。^[58]その結果、8と144（F ₆とF ₁₂）は、他のフィボナッチ数の積となる唯一のフィボナッチ数です。^[59]

フィボナッチ数が素数pで割り切れるかどうかは、次のように評価されるルジャンドル記号 と関係があります。 ${\displaystyle {\bigl (}{\tfrac {p}{5}}{\bigr )}}$$${\displaystyle \left({\frac {p}{5}}\right)={\begin{cases}0&{\text{if }}p=5\\1&{\text{if }}p\equiv \pm 1{\pmod {5}}\\-1&{\text{if }}p\equiv \pm 2{\pmod {5}}.\end{cases}}}$$

pが素数 ならば^{[60] [61]}$${\displaystyle F_{p}\equiv \left({\frac {p}{5}}\right){\pmod {p}}\quad {\text{and}}\quad F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p}}.}$$

例えば、 $${\displaystyle {\begin{aligned}{\bigl (}{\tfrac {2}{5}}{\bigr )}&=-1,&F_{3}&=2,&F_{2}&=1,\\{\bigl (}{\tfrac {3}{5}}{\bigr )}&=-1,&F_{4}&=3,&F_{3}&=2,\\{\bigl (}{\tfrac {5}{5}}{\bigr )}&=0,&F_{5}&=5,\\{\bigl (}{\tfrac {7}{5}}{\bigr )}&=-1,&F_{8}&=21,&F_{7}&=13,\\{\bigl (}{\tfrac {11}{5}}{\bigr )}&=+1,&F_{10}&=55,&F_{11}&=89.\end{aligned}}}$$

素数pが存在するかどうかは不明である。

$${\displaystyle F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p^{2}}}.}$$

そのような素数は（もし存在するならば）ウォール・サン・サン素数と呼ばれるでしょう。

また、p ≠5が奇数の素数である場合は^[62] $${\displaystyle 5{F_{\frac {p\pm 1}{2}}}^{2}\equiv {\begin{cases}{\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {p}{5}}{\bigr )}\pm 5\right){\pmod {p}}&{\text{if }}p\equiv 1{\pmod {4}}\\{\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {p}{5}}{\bigr )}\mp 3\right){\pmod {p}}&{\text{if }}p\equiv 3{\pmod {4}}.\end{cases}}}$$

例 1. p = 7、この場合p ≡ 3 (mod 4)となり、次のようになります。 $${\displaystyle {\bigl (}{\tfrac {7}{5}}{\bigr )}=-1:\qquad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {7}{5}}{\bigr )}+3\right)=-1,\quad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {7}{5}}{\bigr )}-3\right)=-4.}$$ $${\displaystyle F_{3}=2{\text{ and }}F_{4}=3.}$$ $${\displaystyle 5{F_{3}}^{2}=20\equiv -1{\pmod {7}}\;\;{\text{ and }}\;\;5{F_{4}}^{2}=45\equiv -4{\pmod {7}}}$$

例 2. p = 11、この場合p ≡ 3 (mod 4) となり、次のようになります。 $${\displaystyle {\bigl (}{\tfrac {11}{5}}{\bigr )}=+1:\qquad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {11}{5}}{\bigr )}+3\right)=4,\quad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {11}{5}}{\bigr )}-3\right)=1.}$$ $${\displaystyle F_{5}=5{\text{ and }}F_{6}=8.}$$ $${\displaystyle 5{F_{5}}^{2}=125\equiv 4{\pmod {11}}\;\;{\text{ and }}\;\;5{F_{6}}^{2}=320\equiv 1{\pmod {11}}}$$

例 3. p = 13、この場合p ≡ 1 (mod 4) となり、次のようになります。 $${\displaystyle {\bigl (}{\tfrac {13}{5}}{\bigr )}=-1:\qquad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {13}{5}}{\bigr )}-5\right)=-5,\quad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {13}{5}}{\bigr )}+5\right)=0.}$$ $${\displaystyle F_{6}=8{\text{ and }}F_{7}=13.}$$ $${\displaystyle 5{F_{6}}^{2}=320\equiv -5{\pmod {13}}\;\;{\text{ and }}\;\;5{F_{7}}^{2}=845\equiv 0{\pmod {13}}}$$

例4. p = 29、この場合p ≡ 1 (mod 4)であり、次のようになります。 $${\displaystyle {\bigl (}{\tfrac {29}{5}}{\bigr )}=+1:\qquad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {29}{5}}{\bigr )}-5\right)=0,\quad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {29}{5}}{\bigr )}+5\right)=5.}$$ $${\displaystyle F_{14}=377{\text{ and }}F_{15}=610.}$$ $${\displaystyle 5{F_{14}}^{2}=710645\equiv 0{\pmod {29}}\;\;{\text{ and }}\;\;5{F_{15}}^{2}=1860500\equiv 5{\pmod {29}}}$$

nが奇数の場合、 Fnのすべての奇数素因数は_{4を法として}1と合同であり、これはFnのすべての奇数因数（奇数素因数の積として）が4を法として1と合同であることを意味する。 ^[63]

例えば、 $${\displaystyle F_{1}=1,\ F_{3}=2,\ F_{5}=5,\ F_{7}=13,\ F_{9}={\color {Red}34}=2\cdot 17,\ F_{11}=89,\ F_{13}=233,\ F_{15}={\color {Red}610}=2\cdot 5\cdot 61.}$$

フィボナッチ数F ( i )の既知の因数（i <50000）はすべて関連リポジトリに収集されています。^{[64] [65]}

フィボナッチ数列の要素を nを法としてとると、結果として得られる数列は周期的となり、その周期は最大で 6 nとなる。^{[66]様々な}nに対する周期の長さは、いわゆるピサノ周期を形成する。^[67]ピサノ周期の一般公式を決定することは未解決問題であり、そのサブ問題として、モジュラー整数または有限体内の元の乗法順序を見つける問題の特別な例が含まれる。しかし、任意の特定のnに対して、ピサノ周期はサイクル検出の例として見つけられる可能性がある。

フィボナッチ数列は、再帰関係、具体的には線形差分方程式によって定義される最も単純かつ最も古い既知の数列の 1 つです。これらすべての数列は、フィボナッチ数列の一般化として考えることができます。特に、ビネの公式は、定数係数を持つ同次線形差分方程式の解である任意の数列に一般化できます。

ある意味でフィボナッチ数列に近い具体的な例としては、次のようなものがあります。

• インデックスを負の整数に一般化して、ネガフィボナッチ数を生成します。
• ビネの公式の修正を用いて指数を実数に一般化する。 ^[38]
• 他の整数から始めます。ルーカス数はL ₁ = 1、L ₂ = 3、L _n = L _{n −1} + L _{n −2}です。素数のない数列は、他の開始点とフィボナッチ再帰を使用して、すべての数が合成数である数列を生成します。
• ある数を、その前の 2 つの数の線形関数 (合計以外) とします。ペル数はP _n = 2 P _{n −1} + P _{n −2}です。前の値の係数に変数値xが割り当てられている場合、結果はフィボナッチ多項式のシーケンスになります。
• 直前の数字を加算しない。パドヴァン数列とペラン数はP ( n ) = P ( n − 2) + P ( n − 3)である。
• 3つの数（トリボナッチ数）、4つの数（テトラナッチ数）、またはそれ以上の数を加算して次の数を生成します。結果として得られる数列はnステップフィボナッチ数として知られています。^[68]

フィボナッチ数はパスカルの三角形の「浅い」対角線の二項係数の和として現れる。^[69] これは生成関数を展開し 、の同類項を集めることで証明できる。 $${\displaystyle F_{n}=\sum _{k=0}^{\left\lfloor {\frac {n-1}{2}}\right\rfloor }{\binom {n-k-1}{k}}.}$$$${\displaystyle {\frac {x}{1-x-x^{2}}}=x+x^{2}(1+x)+x^{3}(1+x)^{2}+\dots +x^{k+1}(1+x)^{k}+\dots =\sum \limits _{n=0}^{\infty }F_{n}x^{n}}$$${\displaystyle x^{n}}$

この式がどのように使用されるかを確認するには、存在する項の数によって合計を並べます。

これは であり、ここではn − k −1個の項からk個の 2 の位置を選択しています。 ${\displaystyle \textstyle {\binom {5}{0}}+{\binom {4}{1}}+{\binom {3}{2}}}$

これらの数は特定の列挙問題にも解を与える。^[70]最も一般的な問題は、与えられた数n を1 と 2 の順序付けられた和（合成と呼ばれる）として表記する方法の数を数える問題である。これにはF _{n +1 通り}の方法がある（つまり、長方形のドミノのタイルの数でもある）。たとえば、 5 段の階段を 1 段または 2 段ずつ上るには、 F ₅₊₁ = F ₆ = 8 通りの方法がある。${\displaystyle 2\times n}$

この図は、8 を 5 (4 段の階段を登り、その後に 1 段の階段を登る方法の数) と 3 (3 段の階段を登り、その後に 2 段の階段を登る方法の数) に分解できることを示しています。同じ推論が、 1 段の階段まで再帰的に適用されます。1 段の階段では、登る方法は 1 つしかありません。

フィボナッチ数は、バイナリ 文字列のセット内、または同等に、特定のセットの サブセット内において、さまざまな方法で見つけることができます。

• 連続する1のない長さnのバイナリ文字列の数は、フィボナッチ数F _{n +2}です。たとえば、長さ 4 の 16 個のバイナリ文字列のうち、連続する1のないものはF ₆ = 8 個あります。これらは、0000、0001、0010、0100、0101、1000、1001、および 1010 です。このような文字列は、フィボナッチ数のバイナリ表現です。同様に、F _{n +2 は}、連続する整数のない{1, ..., n }の部分集合Sの数、つまり、すべての i に対して{ i , i + 1} ⊈ Sとなる部分集合 S の数です。合計をn +1に全単射にするには、 1 を 0 に、2 を 10 に置き換え、最後のゼロを削除します。
• 長さnのバイナリ文字列で1が奇数個連続しないものの数は、フィボナッチ数F _{n +1}です。たとえば、長さ 4 のバイナリ文字列 16 個のうち、1が奇数個連続しないものはF ₅ = 5 個あります。これらは、0000、0011、0110、1100、1111 です。同様に、{1、...、n }の部分集合Sで連続する整数が奇数個ないものの数はF _{n +1}です。nへの和の全単射は、1 を 0 に、2 を 11 に置き換えることです。
• 長さnのバイナリ文字列のうち、連続する0または1が偶数個ない文字列の数は2 F _nです。たとえば、長さ 4 の 16 個のバイナリ文字列のうち、連続する0または1が偶数個ない文字列は2 F ₄ = 6 個あります。つまり、0001、0111、0101、1000、1010、1110 です。サブセットについても同等の記述があります。
• ユーリ・マティヤセビッチは、フィボナッチ数がディオファントス方程式によって定義できることを証明し、ヒルベルトの第10問題を解く ことに成功した。^[71]
• フィボナッチ数列も完全な数列の例です。つまり、すべての正の整数はフィボナッチ数列の和として表すことができ、1 つの数は最大で 1 回しか使用されません。
• さらに、すべての正の整数は、 1 つ以上の異なるフィボナッチ数の合計として一意に表すことができます。この場合、合計には 2 つの連続するフィボナッチ数が含まれません。これはゼッケンドルフの定理として知られており、これらの条件を満たすフィボナッチ数の合計はゼッケンドルフ表現と呼ばれます。数値のゼッケンドルフ表現を使用して、そのフィボナッチ コーディングを導出できます。
• 5から始めて、2つおきのフィボナッチ数は、整数の辺を持つ直角三角形の斜辺の長さ、つまり、式から得られるピタゴラスの三つ組における最大の数です。この式から得られるピタゴラス三角形の列は、辺の長さが (3,4,5)、(5,12,13)​​、(16,30,34)、(39,80,89)、... です。これらの三角形のそれぞれの中央の辺は、前の三角形の3辺の合計です。^[72]$${\displaystyle (F_{n}F_{n+3})^{2}+(2F_{n+1}F_{n+2})^{2}={F_{2n+3}}^{2}.}$$
• フィボナッチキューブは、並列コンピューティングのネットワーク トポロジーとして提案されている、フィボナッチ数のノードを持つ無向グラフです。
• フィボナッチ数は環の補題に現れ、円充填定理と等角写像の関係を証明するのに使われる。^[73]

• フィボナッチ数は、 2つの整数の最大公約数を決定するユークリッドのアルゴリズムの計算実行時解析において重要です。このアルゴリズムの最悪の入力は、連続するフィボナッチ数のペアです。^[74]
• フィボナッチ数は、ソートされていないリストを、長さが連続するフィボナッチ数に対応する 2 つのリストに分割するマージソートアルゴリズムの多相バージョンで使用されます。つまり、2 つの部分の長さがおよそφ の割合になるようにリストを分割します。多相マージ ソートのテープ ドライブ実装は、『The Art of Computer Programming』で説明されています。
• フィボナッチ木は、子木の高さが（再帰的に）ちょうど1だけ異なる二分木です。したがって、これはAVL木であり、与えられた高さに対して最も少ないノードを持つ木、つまり「最も薄い」AVL木です。これらの木には、フィボナッチ数から1を引いた数の頂点があり、これはAVL木の分析において重要な事実です。^[75]
• フィボナッチ数は、いくつかの疑似乱数ジェネレーターによって使用されます。
• フィボナッチ数は、フィボナッチ ヒープデータ構造の分析で発生します。
• フィボナッチ探索法と呼ばれる1次元最適化手法では、フィボナッチ数列が使用されます。^[76]
• フィボナッチ数列は、Amigaコンピュータで使用されるIFF 8SVXオーディオファイル形式のオプションの非可逆圧縮に使用されます。この数列は、μ-lawなどの対数法と同様に、元のオーディオ波形を圧縮します。^{[77] [78]}
• 一部のアジャイルチームは、プランニングポーカーで「修正フィボナッチ数列」と呼ばれる修正された数列を見積もりツールとして使用しています。プランニングポーカーは、スケールドアジャイルフレームワークの正式な一部です。^[79]
• フィボナッチコーディング
• ネガフィボナッチコーディング

フィボナッチ数列は生物学的な設定に現れます。^[80]木の枝分かれ、茎の葉の配置、パイナップルの果実、^[81]アーティチョークの開花、松ぼっくりの配置、^[82]ミツバチの系統樹などです。^{[83] [84]} ケプラーは自然界にフィボナッチ数列が存在することを指摘し、それを使っていくつかの花の（黄金比に関連した）五角形の形状を説明しました。 ^[85]野生のデイジーはほとんどの場合、フィボナッチ数列の花びらを持っています。^[86] 1830年、カール・フリードリヒ・シンパーとアレクサンダー・ブラウンは、植物の寄生（螺旋状の葉序）がフィボナッチ数列を含む分数として頻繁に表現されることを発見しました。 ^[87]

プシェミスワフ・プルシンキェヴィチは、実インスタンスは部分的には自由群に対する特定の代数的制約の表現、具体的には特定のリンデンマイヤー文法として理解できるという考えを提唱した。^[88]

ヒマワリの頭花のパターンのモデルは、 1979年にヘルムート・フォーゲル [de]によって提案されました。^[89] これは次の形式です。

$${\displaystyle \theta ={\frac {2\pi }{\varphi ^{2}}}n,\ r=c{\sqrt {n}}}$$

ここでnは小花のインデックス番号、c は定数のスケーリング係数です。したがって、小花はフェルマーの螺旋上にあります。発散角は約 137.51° で、円を黄金比で分割する黄金角です。この比率は無理数なので、中心からまったく同じ角度に隣接する小花はなく、小花は効率的に詰め込まれます。黄金比の有理近似はF (  j ): F (  j + 1)の形式であるため、小花番号nに最も近い隣接小花は、中心からの距離rに依存するインデックスjに対してn ± F (  j )にある小花です。ヒマワリや類似の花は、最も一般的には、隣接するフィボナッチ数列の時計回りと反時計回りの方向に小花の螺旋を持ちます。^[90]通常は、半径の最も外側の範囲で数えられます。^[91]

フィボナッチ数は、次の規則に従って、 ハチ（半二倍体）の祖先の系図にも現れます。

• 卵が産まれても受精しない場合は、雄蜂（ミツバチの場合は雄蜂）が生まれます。
• しかし、卵子が受精すると雌が生まれます。

したがって、オスの蜂には必ず 1 人の親がいて、メスの蜂には 2 人の親がいます。オスの蜂 (1 匹の蜂) の系図をたどると、そのオスには 1 人の親 (1 匹の蜂)、2 人の祖父母、3 人の曽祖父母、5 人の高祖父母、というように続きます。この親の数のシーケンスはフィボナッチ数列です。各レベルの祖先の数F _nは、メスの祖先の数F _{n −1}とオスの祖先の数F _{n −2}を足したものです。^{[92] [93]}これは、各レベルの祖先がそれ以外は無関係であるという非現実的な仮定に基づいています。

同様に、ある祖先世代におけるヒトのX染色体継承系統上の祖先の数もフィボナッチ数列に従うことが分かっている。^[94]男性は、母親から受け継いだX染色体と、父親から受け継いだY染色体を持つ。男性は自身のX染色体の「起源」（）として数えられ、両親の世代では、その男性のX染色体は片親（）から受け継がれた。男性の母親は、母親（息子の母方の祖母）から1つのX染色体を、父親（息子の母方の祖父）から1つを受け継いでいるため、2人の祖父母が男性の子孫のX染色体（）に寄与していることになる。母方の祖父は母親から X 染色体を受け継ぎ、母方の祖母は両親から X 染色体を受け継いでいるため、男性の子孫の X 染色体( )には 3 人の曽祖父母が寄与しています。男性の子孫の X 染色体( )には 5 人の高祖父母が寄与しています。(これは、特定の子孫のすべての祖先が独立していると仮定していますが、系図を十分に遡ると、祖先が複数の系図に現れ始め、最終的には集団の創始者が系図のすべての系図に現れるようになります。) ${\displaystyle F_{1}=1}$${\displaystyle F_{2}=1}$${\displaystyle F_{3}=2}$${\displaystyle F_{4}=3}$${\displaystyle F_{5}=5}$

• 光学では、光線が2枚の異なる屈折率の異なる材料でできた透明板を斜めに透過すると、2枚の板の上面、中間面、下面の3つの面で反射することがあります。k > 1の場合、 k回の反射がある異なる光線経路の数は、 k番目のフィボナッチ数です。（ただし、 k = 1の場合、反射経路は2つではなく、3つの表面に1つずつ、合計3つあります。）^[95]
• フィボナッチ リトレースメントレベルは、金融市場取引のテクニカル分析で広く使用されています。
• マイルからキロメートルへの変換係数1.609344は黄金比に近いため、フィボナッチ数を次の数に置き換えると、マイル単位の距離をフィボナッチ数列に分解すると、ほぼキロメートルの合計になります。この方法は、黄金比を底とするφの基数2の数値レジスタをシフトすることになります。キロメートルからマイルに変換するには、代わりにレジスタをフィボナッチ数列に沿ってシフトします。^[96]
• 無限抵抗器連鎖回路（抵抗器ラダーまたは無限直列並列回路とも呼ばれる）の電圧と電流の測定値はフィボナッチ数列に従います。直列抵抗と並列抵抗を交互に加算した中間結果は、連続するフィボナッチ数列で構成される分数になります。回路全体の等価抵抗は黄金比に等しくなります。^[97]
• Brasch et al. 2012は、一般化フィボナッチ数列が経済学の分野にもどのように関連しているかを示しています。^[98] 特に、一般化フィボナッチ数列が、1つの状態と1つの制御変数を持つ有限期間の動的最適化問題の制御関数にどのように組み込まれるかを示しています。この手順は、ブロック・ミルマン経済成長モデルと呼ばれる例で説明されています。
• マリオ・メルツは1970年代からいくつかの作品にフィボナッチ数列を取り入れた。^[99]
• ジョセフ・シリンガー（1895-1943）は、いくつかのメロディーにフィボナッチ音程を使用する作曲システムを考案しました。彼はこれを、自然界に見られる精巧なハーモニーの音楽的対応物とみなしました。^[100]黄金比§音楽も参照してください。

• フィボナッチ協会 – フィボナッチ数列の研究組織
• 大衆文化におけるフィボナッチ数列
• フィボナッチ語 – フィボナッチ再帰からの二進数列
• ランダムフィボナッチ数列 – フィボナッチ数列に基づいたランダムな数学的数列
• ウィトフ配列 – フィボナッチ数列から導かれた整数の無限行列

• ボール、キース M (2003)、「8: フィボナッチのウサギ再考」、奇妙な曲線、ウサギの数え方、その他の数学的探究、プリンストン、ニュージャージー州:プリンストン大学出版局、ISBN 978-0-691-11321-0。
• ベック、マティアス、ジオゲガン、ロス（2010）、証明の芸術：より深い数学のための基礎トレーニング、ニューヨーク：シュプリンガー、ISBN 978-1-4419-7022-0。
• Bóna、Miklós (2011)、A Walk Through Combinatorics (第 3 版)、ニュージャージー: World Scientific、ISBN 978-981-4335-23-2。
• ボルウェイン、ジョナサン M. ;ボルウェイン、ピーター B. (1998 年 7 月)、円周率と AGM: 解析的数論と計算複雑性の研究、Wiley、pp. 91–101、ISBN 978-0-471-31515-5
• レマーマイヤー、フランツ（2000）、相互法則：オイラーからアイゼンシュタインまで、Springer Monographs in Mathematics、ニューヨーク：Springer、ISBN 978-3-540-66957-9。
• リヴィオ、マリオ（2003）[2002]、黄金比：世界で最も驚くべき数字ファイの物語（最初のトレードペーパーバック版）、ニューヨーク市：ブロードウェイブックス、ISBN 0-7679-0816-3
• Lucas、Édouard (1891)、Théorie des nombres (フランス語)、vol. 1、パリ: ゴティエ ヴィラール。
• シグラー、LE（2002）、フィボナッチの算盤：レオナルド・ピサーノの計算書の現代英語への翻訳、数学と物理科学の歴史における資料と研究、シュプリンガー、ISBN 978-0-387-95419-6

• フィボナッチ数列と黄金比: 現代世界の数学 - YouTubeの Sir Ram による Mathuklasan - 数列、螺旋、黄金比、ウサギのつがいの成長のアニメーション。芸術、音楽、建築、自然、天文学における例
• MathPages のフィボナッチ数列の周期 Mod m
• 科学者が自然界におけるフィボナッチ螺旋の形成の手がかりを発見
• BBCのIn Our Timeにおけるフィボナッチ数列
• 「フィボナッチ数列」、数学百科事典、EMS Press、2001 [1994]
• OEISシーケンス A000045 (フィボナッチ数列)