フィボナッチ数

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
辺の長さが連続するフィボナッチ数である正方形のタイリング:1、1、2、3、5、8、13、および21。

数学では、一般にF nで表されるフィボナッチ数は、シーケンスフィボナッチ数列を形成します。各数は、先行する2つの数の合計です。シーケンスは通常0と1から始まりますが、一部の作成者は最初の用語を省略して1と1または1と2からシーケンスを開始します。0と1から開始して、シーケンスの次のいくつかの値は次のとおりです

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

フィボナッチ数は、2つの長さの音節から形成されたサンスクリット詩の可能なパターンを列挙することに関するPingalaの研究で、紀元前200年にインドの数学で最初に記述されました[2] [3] [4] 。それらは、後にフィボナッチとして知られるピサのイタリアの数学者レオナルドにちなんで名付けられました。彼は、1202年の著書「算盤の書」で西ヨーロッパの数学にシーケンスを導入しました。[5]

フィボナッチ数は数学で予想外に頻繁に現れるため、彼らの研究に特化したジャーナル全体であるフィボナッチ四半期があります。フィボナッチ数のアプリケーションには、フィボナッチ検索手法フィボナッチヒープデータ構造などのコンピューターアルゴリズム、および並列システムと分散システムの相互接続に使用されるフィボナッチキューブと呼ばれるグラフが含まれます。それらはまた、木の枝分かれ茎の葉の配置、パイナップルの実の芽、アーティチョークの開花、カールしていないシダ、および松ぼっくりの苞葉。

フィボナッチ数は黄金比と強く関連しています。Binetの式n番目のフィボナッチ数をnと黄金比で表し、2つの連続するフィボナッチ数の比率はnが増加するにつれて黄金比になる傾向があることを意味します。フィボナッチ数は、同じ漸化式に従うルーカス数とも密接に関連しており、フィボナッチ数とは、リュカ数列の相補的なペアを形成します

定義

フィボナッチスパイラル:フィボナッチタイリングの正方形の反対側の角を結ぶ円弧を描くことによって作成された黄金のスパイラルの近似。(前の画像を参照)

フィボナッチ数は漸化式によって定義される可能性があります[6]

n > 1 の場合

いくつかの古い定義では、値が省略されているため、シーケンスは次のように始まります。と再発n > 2の場合に有効です[7] [8]フィボナッチは[9]

最初の21個のフィボナッチ数Fnのとおりです。[1]

F 0 F 1 F 2 F 3 F 4 F 5 F 6 F 7 F 8 F 9 F 10 F 11 F 12 F 13 F 14 F 15 F 16 F 17 F 18 F 19 F 20
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597年 2584 4181 6765

歴史

長さ6のリズムで長い音節と短い音節を配置する13(F 7 )の方法。5(F 5)は長い音節で終わり、8(F 6)は短い音節で終わります。

フィボナッチ数列は、1986年にParmanand Singhによって指摘されたように、サンスクリットの韻律に関連してインドの数学に現れます。 [3] [10] [11]サンスクリットの詩の伝統では、長い(L)音節のすべてのパターンを列挙することに関心がありました。 2単位の長さで、1単位の長さの短い(S)音節と並置されます。与えられた合計持続時間で連続するLとSの異なるパターンを数えると、フィボナッチ数が得られます。持続時間m単位のパターンの数はF m +1です。[4]

フィボナッチ数列の知識は、早くもピンガラ紀元前 450年〜紀元前200年頃)で表現されました。シンは、ピンガラの不可解な公式ミスラウチャ(「2つは混合されている」)を引用し、 mビートのパターン数(F m +1 )はFmに1 [S]を加えることによって得られる文脈で解釈する学者ケースと1 [L]からFm - 1ケース。[12] バラタ・ムニはまた、ナティア・シャストラ(紀元前100年頃から西暦350年頃)のシーケンスに関する知識を表現しています。[13] [2] しかし、シーケンスの最も明確な説明は、Virahanka(c。700AD)の作品で発生します。その作品は失われていますが、Gopala(c。1135)による引用で入手できます。[11]

以前の2メートルのバリエーション[バリエーションです] ...たとえば、[長さ1メートル] 4の場合、2 [および] 3メートルのバリエーションが混在していると5が発生します。[例8、13、21を実行] ...このように、プロセスはすべてのmātrā-vṛttas [韻律の組み合わせ]で従う必要があります。[a]

ヘマチャンドラ(1150年頃)もシーケンスの知識を持っていると信じられており[2]、「最後と最後の前の合計は次のmātrā-vṛttaの数です...」と書いています。[15] [16]

インド国外では、フィボナッチ数列は、ウサギの個体数の増加を計算するために使用されるフィボナッチ数[5] [17]による本LiberAbaciThe Book of Calculation、1202)に最初に登場します。[18] [19]フィボナッチは、次のことを前提として、理想化された(生物学的に非現実的な)ウサギの個体数の増加を考慮しています。各繁殖ペアは1か月齢で交尾し、2か月目の終わりには、常に別のウサギのペアを生産します。ウサギは決して死ぬことはありませんが、永遠に繁殖し続けます。フィボナッチはパズルを提起しました:1年にいくつのペアがありますか?

  • 最初の月の終わりに、彼らは交尾しますが、まだ1つのペアしかありません。
  • 2か月目の終わりに、新しいペアが作成されるため、フィールドには2つのペアがあります。
    Biblioteca Nazionale diFirenzeフィボナッチの算盤の書のページ。フィボナッチ数列の位置がラテン数字とローマ数字で、値がヒンドゥーアラビア数字で示されています(右側のボックス内)。
  • 3か月目の終わりに、元のペアは2番目のペアを生成しますが、2番目のペアは繁殖せずに交配するだけなので、全部で3つのペアがあります。
  • 4か月目の終わりに、元のペアはさらに別の新しいペアを生成し、2か月前に生まれたペアも最初のペアを生成して5ペアを作成します。

nか月目の終わりに、ウサギのペアの数は、成熟したペアの数(つまり、n – 2か月のペアの数)に先月(n – 1か月)生きているペアの数を加えたものに等しくなります。 )。n番目の月の数はn番目のフィボナッチ数です。[20]

増加する人口では、ウサギのペアの数がフィボナッチ数列を形成します。n番目の月の終わりに、ペアの数はFnに等しくなります。

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

黄金比との関係

閉じた形の式

定数係数を持つ線形漸化式によって定義されるすべてのシーケンスと同様に、フィボナッチ数は閉形式の式を持ちます。フランスの数学者ジャック・フィリップ・マリー・ビネットにちなんで名付けられたビネットの公式として知られるようになりましたが、アブラーム・ド・モアブルダニエル・ベルヌーイによってすでに知られていました[22]

どこ
黄金比OEIS:  A001622)であり、ψその共役であり、どちらも黄金比の固有の特性を示します。これは、 φの逆数であり、同時に1を超える小数部であるためです。[23]

以来、この式は次のように書くこともできます

シーケンスとこれらの定数の関係を確認するために、[24] φψは両方とも方程式の解である ことに注意してください。

したがって、 φψ の累乗はフィボナッチ再帰を満たします。言い換えると、

したがって、任意の値aおよびbについて、次のように定義されたシーケンス

同じ再発を満たします。

U 0 = 0およびU1 = 1となるようにaおよびbが選択された場合、結果のシーケンスUnはフィボナッチ数列である必要があります。これは、 abが連立方程式を満たすこと を要求するのと同じです。

解決策があります
必要な式を作成します。

開始値U0U1を任意の定数とすると、より一般的な解決策は次のようになります

どこ

四捨五入による計算

以来

すべてのn≥0の場合、数値Fnはに最も近い整数ですしたがって、最も近い整数関数を使用して、を 丸めることで見つけることができます。

実際、丸め誤差は非常に小さく、n≥4の場合は0.1未満n≥8場合は0.01未満です

フィボナッチ数は、床関数の観点から、切り捨てによって計算することもできます。

床関数は単調であるため、後者の式を逆にして、正の整数F 以上の最小のフィボナッチ数のインデックスnFを見つけることができます

どこ、 と

マグニチュード

F n漸近線であるため、Fnの桁数は次のよう漸近します。結果として、すべての整数d > 1に対して、 10進数 のdを持つ4つまたは5つのフィボナッチ数があります。

より一般的には、ベースb表現では、 Fnの桁数は次のように漸近します。

連続する商の制限

Johannes Keplerは、連続するフィボナッチ数の比率が収束することを観察しました。彼は「5は8であるため、実際には8から13であり、8は13であるため、ほぼ13から21である」と書き、これらの比率は黄金比に近づくと結論付けました。 [25] [26]

この収束は、開始値に関係なく保持されます、 そうでもなければこれは、 Binetの式を使用して確認できますたとえば、初期値3と2は、シーケンス3、2、5、7、12、19、31、50、81、131、212、343、555、...を生成します。このシーケンスの連続する用語の比率は次のようになります。黄金比への同じ収束。

一般に、、連続するフィボナッチ数の比率が近づくため

平面の連続したタイリングと、各フィボナッチ数を前の数で割って計算された黄金比の近似値のグラフ

力の分解

黄金比は方程式を満たすので

この式は、より高いパワーを分解するために使用できます低電力の線形関数として、これは次の線形結合に分解することができます。1.結果として得られる漸化式は、線形係数としてフィボナッチ数を生成 します。

この方程式は、 n≥1での誘導 によって証明できます
ために、それはまたその場合ですそしてそれはまたその場合です

これらの式は、フィボナッチ数列F nがフィボナッチ数列を使用して負の整数に拡張された場合、 n <1の場合にも当てはまります。

識別

Binetの式は、正の整数xがフィボナッチ数であるという証明を提供します。また完璧な正方形です[27]これは、Binetの式が次のように記述できるためです。、を掛けることができますで二次方程式として解かれます二次方程式を介して

これをと比較する、それは次のようになります

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

マトリックスフォーム

フィボナッチ数列を記述する 線形差分方程式の2次元システムは次のとおりです。

代わりに示される

これは行列A固有値は次のとおりです。それぞれの固有ベクトルに対応する

初期値は
したがって、n番目の項は 次のようになります。
このことから、フィボナッチ数列のn番目の要素は、閉じた形式の式として直接読み取ることができます

同様に、同じ計算は、その固有分解を使用してA対角化することによって実行できます。

どこしたがって、フィボナッチ数列のn番目の要素 の閉形式の式は次の式で与えられます。

これもまた

行列A行列式は-1であるため、2×2のユニモジュラ行列です。

この特性は、黄金比の 連分数表現の観点から理解できます。

フィボナッチ数は、 φの連分数の連続する収束の比率として発生し、任意の連分数の連続する収束から形成される行列は、+ 1または-1の行列式を持ちます。行列表現は、フィボナッチ数の次の閉形式の式を提供します。

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

この方程式の両側の行列式を取ると、カッシーニのアイデンティティが得られます。

さらに、任意の正方行列Aに対してA n A m = A n + mであるため、次の恒等式を導出できます(これらは、行列積の2つの異なる係数から取得され、最初の恒等式から2番目の恒等式を簡単に推定できます。nn + 1に変更)、

特に、m = nの場合、

これらの最後の2つのIDは、O(log(n))算術演算と時間OMn)log(n))でフィボナッチ数を再帰的に計算する方法を提供します。ここで、Mnは2の乗算の時間です。nの数。これは、閉形式の行列式からn番目のフィボナッチ数を計算する時間と一致しますが、すでに計算されたフィボナッチ数の再計算(メモ化による再帰)を回避すると、冗長な手順が少なくなります。[28]

組み合わせのアイデンティティ

組み合わせ論的証明

フィボナッチ数を含むほとんどの恒等式は、次の事実を使用した組み合わせ引数を使用して証明できます。合計が次の1と2の[おそらく空の]シーケンスの数として解釈できます。これは、の定義と見なすことができます慣習で、合計が-1であるようなシーケンスが存在しないことを意味します。、空のシーケンスが0に「加算」されることを意味します。以下では、セット カーディナリティは次のとおりです。

このように漸化式

分割することで理解できますシーケンスを2つの重複しないセットに分割します。ここで、すべてのシーケンスは1または2で始まります。
最初の要素を除いて、各シーケンスの残りの項は合計で次のようになります。また各セットのカーディナリティまた合計を与えるシーケンス、これが等しいことを示す


同様の方法で、n番目までの最初のフィボナッチ数の合計が(n + 2)番目フィボナッチ数から1を引いたものに等しいことが示される場合があります

これは、合計するすべてのシーケンスを分割することで確認できます。最初の2の位置に基づきます。具体的には、各セットは、開始するシーケンスで構成されます。最後の2セットまでそれぞれカーディナリティ1。


以前と同じロジックに従って、各セットのカーディナリティを合計すると、次のようになります。

...最後の2つの用語の値はこのことから、次のようになります

同様の議論で、最初の2つではなく最初の1つの位置で合計をグループ化すると、さらに2つのIDが得られます。

つまり、奇数のインデックスを持つ最初のフィボナッチ数の合計はは(2 n)番目のフィボナッチ数であり、インデックスが最大の最初のフィボナッチ数の合計です。(2 n  + 1)番目のフィボナッチ数から1を引いたものです。[30]


別のトリックを使用して証明することができます

または、言い換えると、最初のフィボナッチ数の2乗の合計はn番目と(n  + 1)番目のフィボナッチ数の積です。これを確認するには、サイズのフィボナッチ長方形から始めますそしてそれをサイズの正方形に分解します; これから、アイデンティティは領域を比較することによって続きます:

フィボナッチスクエア.svg

シンボリックメソッド

シーケンスシンボリックメソッドを使用することも考慮されます。[31]より正確には、このシーケンスは指定可能な組み合わせクラスに対応します。このシーケンスの仕様は次のとおりです。確かに、上記のように、-番目のフィボナッチ数は、の組み合わせ構成(順序付けられたパーティション)の数に等しい用語1と2を使用します。

したがって、フィボナッチ数列の通常の母関数、すなわち、は複素関数です

帰納法の証明

フィボナッチのアイデンティティは、数学的帰納法を使用して簡単に証明できることがよくあります

たとえば、再考する

追加する両側に与える

だから私たちはのための式を持っています

同様に、の両側に

与えるために

Binet式の証明

Binetの式は

これは、フィボナッチの身元を証明するために使用できます。

たとえば、それを証明するために 左側に乗算されていることに注意してくださいになります

必要に応じて、事実を使用して方程式を単純化するため。

その他のアイデンティティ

他の多くのアイデンティティは、さまざまな方法を使用して導出できます。それらのいくつかを次に示します。[32]

カッシーニとカタロニア語のアイデンティティ

カッシーニのアイデンティティは次のように述べています

カタランのアイデンティティは一般化です:

d'Ocagneのアイデンティティ

ここで、Lnn番目リュカ数です。最後はnを2倍にするためのアイデンティティですこのタイプの他のIDは次のとおりです。
カッシーニのアイデンティティによって。

これらは、格子基底縮小 を使用して実験的に見つけることができ、フィボナッチ数 因数分解するための特殊数体ふるいを設定するのに役立ちます。

より一般的には、[32]

または代わりに

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

母関数

フィボナッチ数列の母関数べき級数です

このシリーズは収束しますそしてその合計は単純な閉じた形をしています:[33]

これは、フィボナッチの漸化式を使用して、無限の合計の各係数を展開することで証明できます。

方程式を解く

for sx)は閉じた形になります。

部分分数分解は次の式で与えられます 。

どこ黄金比であり、その共役です。

ネガフィボナッチの母関数を与え、関数方程式を満たす

逆数の合計

フィボナッチ数の逆数の無限の合計は、テータ関数の観点から評価できる場合がありますたとえば、すべての奇数インデックスの逆数フィボナッチ数の合計は、次のように書くことができます。

およびフィボナッチ数の逆数の2乗の合計は次のようになります。

最初の合計の各フィボナッチ数に1を加えると、閉じた形もあります

そして、黄金比の逆数を与えるフィボナッチ数の二乗のネストされた合計があります、

すべての偶数インデックスの逆数フィボナッチ数の合計は[34]です。

ランバート級数     以来  

したがって、フィボナッチ数列の逆数は 次のようになります。

さらに、この数は、RichardAndré-Jeanninによって不合理であることが証明されています。[35]

ミリンシリーズはアイデンティティを与えます[ 36]

これは、 Nが無限大になる傾向がある ため、部分和の閉形式から得られます。

素数と分割可能性

分割可能性プロパティ

シーケンスの3番目ごとの数はさらに一般的であり、シーケンスのk番目ごとの数はFkの倍数ですしたがって、フィボナッチ数列は分割可能数列の例です実際、フィボナッチ数列はより強い分割性を満たしています[37] [38]

ここで、gcd最大公約数関数です。

特に、3つの連続するフィボナッチ数は、両方が互いに素であるため、互いに素です。あれは、

nごとに

すべての素数pは、5を法とするpの値によって決定できるフィボナッチ数を除算します。pが1または4(mod 5)に合同である場合、 pはF p  − 1を除算し、 pが2または3に合同である場合(mod 5)次に、pはF p  +1を除算します。残りのケースは、p  = 5であり、この場合、pFpを除算します。

これらのケースは、ルジャンドル記号を使用して、単一の区分的でない式に組み合わせることができます[39]

素数性テスト

上記の式は、次のような意味で素数性テストとして使用できます。

ルジャンドル記号がヤコビ記号に 置き換えられた場合、これはnが素数であることの証拠であり、それが成り立たない場合、nは間違いなく素数ではありません。nが合成であり、式を満たす場合、nフィボナッチ擬素数です。mが大きい場合(たとえば500ビットの数値)、行列形式を使用してF m(mod n )を効率的に計算できます。したがって

ここで、行列のべき乗A mは、べき乗剰余を使用して計算されます。これは、行列に適合させることができます[40]

フィボナッチ素数

フィボナッチ素数は、素数であるフィボナッチです最初のいくつかは次のとおりです。

2、3、5、13、89、233、1597、28657、514229、... OEIS:  A005478

数千桁のフィボナッチ素数が見つかっていますが、無限にあるかどうかは不明です。[41]

FknはFnで割り切れるので、F 4 = 3を除いて、フィボナッチ素数素数インデックスが必要です。合成数任意の長い実行があるため、したがって、合成フィボナッチ数の任意の長い実行もあります。

F 6 = 8より大きいフィボナッチ数は、素数より1大きいまたは1小さいものではありません。[42]

唯一の自明でない二乗フィボナッチ数は144です。[43] AttilaPethőは2001年に、累乗フィボナッチ数が有限数しかないことを証明しました。[44] 2006年、Y。Bugeaud、M。Mignotte、およびS. Siksekは、8と144がそのような自明でない累乗数だけであることを証明しました。[45]

1、3、21、および55は、Vern Hoggattによって推測され、LuoMingによって証明された唯一の三角形のフィボナッチ数です。[46]

フィボナッチ数は完全数にはなり得ません。[47]より一般的には、1以外のフィボナッチ数は倍積完全数にはなり得ず[48]2つのフィボナッチ数の比率は完全にはなり得ません。[49]

素数除数

1、8、および144(F 1 = F 2F6およびF12 )を除いて、すべてのフィボナッチ数には、より小さいフィボナッチ数の因数ではない素因数があります(カーマイケルの定理)。[50]結果として、8と144(F6F12 は、他のフィボナッチ数OEIS:A235383の積である唯一フィボナッチ です

素数pによるフィボナッチ数の分割可能性は、ルジャンドル記号に関連しています。 これは次のように評価されます。

pが素数の 場合、

[51] [52]

例えば、

次のような 素数pが存在するかどうかは不明です。

このような素数(存在する場合)は、ウォール-孫-太陽素数と呼ばれます。

また、p ≠5が奇数の素数である場合、次のようになります。[53]

1.p = 7、この場合はp≡3(mod 4)であり、次のようになります。

例2.p = 11、この場合はp≡3(mod 4)であり、次のようになります。

例3.p = 13、この場合はp≡1(mod 4)であり、次のようになります。

例4.p = 29、この場合はp≡1(mod 4)であり、次のようになります。

奇数nの場合、 F nのすべての奇数素数除数は1モジュロ4に合同です。これは、 F nのすべての奇数除数(奇数素数除数の積として)が1モジュロ4に合同であることを意味します。 [54]

例えば、

すべてのi <50000のフィボナッチ数Fi)のすべての既知の因子は、関連するリポジトリで収集されます。[55] [56]

nを法とする周期性

フィボナッチ数列のメンバーがmodnである場合 結果の列は周期的で、最大 6nの周期になります。[57]さまざまなnの期間の長さは、いわゆるPisano期間OEIS:  A001175を形成します。ピサーノ周期の一般式を決定することは未解決の問題であり、サブ問題として、モジュラー整数または有限体の要素の乗法次数を見つける問題の特別なインスタンスが含まれますただし、特定のnの場合、Pisano期間は次のインスタンスとして検出される可能性があります。 サイクル検出

一般化

フィボナッチ数列は、漸化式、特に線形差分方程式によって定義される最も単純で最も初期の既知の数列の1つですこれらのシーケンスはすべて、フィボナッチ数列の一般化と見なすことができます。特に、Binetの式は、一定の係数を持つ均一な線形差分方程式の解である任意のシーケンスに一般化できます。

ある意味でフィボナッチ数列に近いいくつかの特定の例には、次のものがあります。

  • インデックスを負の整数に一般化して、負の数を生成します
  • Binetの式の修正を使用して、インデックスを実数に一般化します。[32]
  • 他の整数から始めます。リュカ数は、 L 1 = 1、L 2 = 3、およびL n = L n −1 + L n −2です。Primefreeシーケンスは、他の開始点でフィボナッチ再帰を使用して、すべての数値が合成であるシーケンスを生成します。
  • 数値を、先行する2つの数値の線形関数(合計以外)とします。ペル数Pn = 2 P n1 + P n −2です。前の値の係数に変数値xが割り当てられている場合、結果はフィボナッチ多項式のシーケンスになります。
  • 直前の数字を加算しない。パドヴァン数列ペラン数は、P n = Pn − 2)+ Pn − 3)です。
  • 3つの数(tribonacci数)、4つの数(tetranacci数)、またはそれ以上を追加することによって次の数を生成します。結果として得られるシーケンスは、nステップフィボナッチ数として知られています。[58]

アプリケーション

数学

フィボナッチ数は、パスカルの三角形の「浅い」対角線(赤で表示)の合計です。

フィボナッチ数は、パスカルの三角形の「浅い」対角線の合計で発生します(二項係数を参照):[59]

母関数はに拡張することができます

の同類項を収集します、私たちはアイデンティティを持っています

数式がどのように使用されるかを確認するために、存在する用語の数で合計を整理できます。

5 = 1 + 1 + 1 + 1 + 1
= 2 + 1 + 1 + 1 = 1 + 2 + 1 + 1 = 1 + 1 + 2 + 1 = 1 + 1 + 1 + 2
= 2 + 2 + 1 = 2 + 1 + 2 = 1 + 2 + 2

これは、ここで、nk-1からk2の位置を選択しています。

フィボナッチ数列を使用して{1、2}で制限された構成をカウントする

これらの数はまた、特定の列挙問題の解決策を提供します[60]。その最も一般的なものは、与えられた数nを1と2の順序付けられた合計として書く方法の数を数えることです(構成と呼ばれます)。これを行うにはFn +1の方法があります(同等に、それはドミノタイリング数でもあります矩形)。たとえば、F 5 + 1 = F 6 = 8つの方法があり、一度に1つまたは2つのステップを踏んで、5つのステップの階段を上ることができます。

5 = 1 + 1 + 1 + 1 + 1 = 2 + 1 + 1 + 1 = 1 + 2 + 1 + 1 = 1 + 1 + 2 + 1 = 2 + 2 + 1
= 1 + 1 + 1 + 2 = 2 + 1 + 2 = 1 + 2 + 2

この図は、8を5(4ステップを登る方法の数とそれに続くシングルステップ)と3(3ステップを登る方法の数とそれに続くダブルステップ)に分解できることを示しています。同じ推論が、登る方法が1つしかない単一のステップまで 再帰的に適用されます。

フィボナッチ数は、 2進 文字列のセット間、または同等に、特定のセットのサブセット間でさまざまな方法で見つけることができます

  • 連続する1秒のない長さnの2進文字列の数は、フィボナッチ数F n + 2です。たとえば、長さ4の16個のバイナリ文字列のうち、連続する1がないF 6 = 8があります– 0000、0001、0010、0100、0101、1000、1001、および1010です。同等に、F n + 2はサブセットの数S連続する整数のない{1、...、n}の、つまりすべてiに対して{ i i +1 } ⊈SあるS。合計がn + 1全単射は、 10に、210に置き換え、最後のゼロを削除することです。
  • 奇数の連続する1秒のない長さnの2進文字列の数は、フィボナッチ数F n +1です。たとえば、長さ4の16個のバイナリ文字列のうち、奇数の連続する1がないF 5 = 5があります。これらは0000、0011、0110、1100、1111です。同等に、{1のサブセットSの数、...、n }は、奇数の連続する整数がない場合、F n + 1です。合計がnの全単射は、 10に、2を2に置き換えることです。11
  • 連続する0秒または1秒の数が偶数でない長さnのバイナリ文字列のは2Fnです。たとえば、長さ4の16個のバイナリ文字列のうち、2 F 4 = 6があり、連続する0秒または1秒の数は偶数ではありません。これらは0001、0111、0101、1000、1010、1110です。同等のものがあります。サブセットに関するステートメント。
  • ユーリ・マチャセビッチは、フィボナッチ数がディオファントス方程式で定義できることを示すことができました。これにより、ヒルベルトの第10問題が解かれました [61]
  • フィボナッチ数も完全数列の例です。これは、すべての正の整数がフィボナッチ数の合計として記述できることを意味します。ここで、任意の1つの数が最大で1回使用されます。
  • さらに、すべての正の整数は、合計に2つの連続するフィボナッチ数が含まれないように、1つ以上の異なるフィボナッチ数の合計として一意の方法で書き込むことができます。これはゼッケンドルフの定理として知られており、これらの条件を満たすフィボナッチ数の合計はゼッケンドルフ表現と呼ばれます。数値のゼッケンドルフ表現を使用して、フィボナッチ符号化を導出できます。
  • 5から始まり、毎秒のフィボナッチ数は、整数の辺を持つ直角三角形の斜辺の長さ、つまり、式から得られるピタゴラストリプルの最大数です。
    この式から得られるピタゴラスの三角形のシーケンスには、長さ(3,4,5)、(5,12,13)、(16,30,34)、(39,80,89)、...の辺があります。これらの三角形のそれぞれの辺は、前の三角形の3つの辺の合計です。[62]
  • フィボナッチキューブは、並列コンピューティングのネットワークトポロジとして提案されている、フィボナッチ数のノードを持つ無向グラフです。
  • フィボナッチ数は、円パッキング定理と正角図法の間の関係を証明するために使用されるリングレンマに表示されます。[63]

コンピュータサイエンス

高さ6のフィボナッチの木。バランスファクターは緑。高さは赤。
左背骨の鍵はフィボナッチ数です。

自然

21(青)と13(アクア)のらせん状の配置を示す黄色のカモミールの頭。連続するフィボナッチ数を含むこのような配置は、多種多様な植物に見られます。

フィボナッチ数列は、[69]木の枝分かれ、茎の葉の配置、パイナップルの子実[70]アーティチョークの開花、カールしていないシダ、松ぼっくりの配置などの生物学的設定に現れます[71 ]とミツバチの家族の木。[72] [73] ケプラーは、自然界にフィボナッチ数列が存在することを指摘し、それを使用して、いくつかの花の(黄金比に関連する)五角形を説明しました。[74]野外のヒナギクは、ほとんどの場合、フィボナッチ数で花びらを持っています。[75]1754年、シャルル・ボネは、植物のらせん状葉序がフィボナッチ数列で頻繁に表現されることを発見しました。[76]

PrzemysławPrusinkiewiczは、実際のインスタンスは、自由群に対する特定の代数的制約の表現、特に特定のLindenmayer文法として部分的に理解できるという考えを発展させました。[77]

n = 1 ... 500のフォーゲルのモデルの図

ヒマワリの頭の小花のパターンのモデルは1979年にHelmutVogelによって提案されました。 [78] これは次の形式を持っています

ここで、nは小花のインデックス番号、cは一定の倍率です。したがって、小花はフェルマー螺旋上にあります。約137.51°の発散角は黄金角であり、円を黄金比で分割します。この比率は不合理であるため、中心からまったく同じ角度に隣接する小花はなく、小花は効率的にパックされます。黄金比の有理数近似はFj):Fj + 1)の形式であるため、小花番号nの最近傍はn ± F j での最近傍です。中心からの距離であるrに依存するいくつかのインデックスjの場合。ヒマワリおよび同様の花は、最も一般的には、隣接するフィボナッチ数の量で時計回りおよび反時計回りの方向に小花の渦巻きを持ち、[79]通常は半径の最も外側の範囲で数えられます。[80]

フィボナッチ数は、次の規則に従って、理想化されたミツバチの血統にも表示されます。

  • 交尾していない雌が産卵すると、雄またはドローンのハチが孵化します。
  • しかし、卵子がオスによって受精された場合、それはメスを孵化します。

したがって、オスのミツバチには常に1人の親がいて、メスのミツバチには2人の親がいます。男性の蜂(1匹の蜂)の血統をたどると、彼には1人の親(1匹の蜂)、2人の祖父母、3人の曽祖父母、5人の曽祖父母などがいます。この親の数列はフィボナッチ数列です。各レベルの祖先の数Fn、女性の祖先の数(F n -1)に男性の祖先の数(F n -2 加えたものです。[81] これは、各レベルの祖先が他の点では無関係であるという非現実的な仮定の下にあります。

特定の祖先世代でのX染色体継承ライン上の可能な祖先の数は、フィボナッチ数列に従います。(ハチソンの後、L。「家族の木の成長:家族関係の再構築におけるDNAの力」。[82]

所与の祖先世代におけるヒトX染色体遺伝系統上の可能な祖先の数もフィボナッチ数列に従うことに気づきました。[82]男性の個人は、母親から受け取ったX染色体と、父親から受け取ったY染色体を持っています。男性は彼自身のX染色体の「起源」として数えられます()、そして彼の両親の世代では、彼のX染色体はひとり親から来ました()。男性の母親は母親(息子の母方の祖母)から1本、父親(息子の母方の祖父)から1本のX染色体を受け取ったため、2人の祖父母が男性の子孫のX染色体に貢献しました()。母方の祖父は母親からX染色体を受け取り、母方の祖母は両親の両方からX染色体を受け取ったので、3人の曽祖父母が男性の子孫のX染色体に貢献しました()。5人の曽祖父母が男性の子孫のX染色体に貢献しました()など(これは、特定の子孫のすべての祖先が独立していることを前提としていますが、いずれかの系図が過去にさかのぼると、祖先は系図の複数の行に表示され始め、最終的には人口の創設者が系図。)

細胞内微小管上のチューブリンの経路は、3、5、8、および13のパターンで配置されます。[83]

その他

  • 光学では、光線が屈折率の異なる異なる材料の2つの積み重ねられた透明なプレートを斜めに照らすと、2つのプレートの上面、中間、下面の3つの面で反射する場合があります。k > 1の場合、k回の反射を持つさまざまなビームパスの数は次のようになります。フィボナッチ数。(ただし、k = 1の場合、3つの表面のそれぞれに1つずつ、2つではなく、3つの反射経路があります。)[84]
  • フィボナッチリトレースメントレベルは、金融市場取引のテクニカル分析で広く使用されています。
  • マイルからキロメートルへの変換係数1.609344は黄金比に近いため、フィボナッチ数を後継者に置き換えると、マイル単位の距離をフィボナッチ数の合計に分解すると、ほぼキロメートルの合計になります。この方法は、黄金比ベースφの基数2の数値レジスタがシフトされることになります。キロメートルからマイルに変換するには、代わりにレジスタをフィボナッチ数列にシフトダウンします。[85]
  • 無限抵抗チェーン回路(抵抗ラダーまたは無限直並列回路とも呼ばれます)の電圧と電流の測定値は、フィボナッチ数列に従います。交互の直列抵抗と並列抵抗を加算した中間結果は、連続するフィボナッチ数で構成される分数を生成します。回路全体の等価抵抗は黄金比に等しくなります。[86]
  • Brasch etal。2012年は、一般化されたフィボナッチ数列が経済学の分野にもどのように関連するかを示しています。[87] 特に、一般化されたフィボナッチ数列が、1つの状態と1つの制御変数を持つ有限範囲動的最適化問題の制御関数にどのように入るかが示されています。この手順は、ブロック-マーマン経済成長モデルと呼ばれることが多い例に示されています。
  • マリオ・メルツは、1970年に始まった彼の作品のいくつかにフィボナッチ数列を含めました。[88]
  • ヨーゼフ・シリンガー(1895–1943)は、いくつかのメロディーでフィボナッチ音程を使用する作曲システムを開発しました。彼はこれらを自然の中で明らかな精巧な調和の音楽的対応物と見なしました。[89]黄金比§音楽も参照してください

も参照してください

参考文献

脚注

  1. ^ 「4つの場合、2つの[および] 3つのメーターのバリエーションが混合され、5つが発生します。5つの場合、以前の2つのバリエーション– 3つの[および] 4つの混合された、8つが得られます。このように、6つの場合、[バリエーション] 4つのうち[および] 5つのうち13が混合されます。そのように、以前の2つのメーターのバリエーションが混合され、7つのモーラが21になります。このように、すべてのmātrā-vṛttasでプロセスに従う必要があります。 [14]

引用

  1. ^ a b Sloane、N。J. A.(ed。)、"Sequence A000045"The Online Encyclopedia of Integer Sequences、OEIS Foundation
  2. ^ a b c Goonatilake、Susantha(1998)、Toward a Global Science、Indiana University Press、p。126、ISBN 978-0-253-33388-9
  3. ^ a b Singh、Parmanand(1985)、「古代および中世のインドにおけるいわゆるフィボナッチ数」、Historia Mathematica12(3):229–44、doi10.1016 / 0315-0860(85)90021-7
  4. ^ a b Knuth、Donald(2006)、The Art of Computer Programming、vol。4.すべての木の生成–組み合わせ生成の歴史、Addison–Wesley、p。50、ISBN 978-0-321-33570-8正確にmビートを持つ[L]と[S]のすべてのシーケンスのセットを検討するのは自然なことでした。...正確にFm + 1があります。たとえば、m  = 7の場合の21のシーケンスは次のとおりです。[リストを提供]。このようにして、セクション1.2.8(v.1から)で観察したように、インドのプロソディストはフィボナッチ数列を発見するように導かれました。
  5. ^ a b Pisano 2002、pp。404–05。
  6. ^ ルーカス1891、p。3.3。
  7. ^ Beck&Geoghegan2010
  8. ^ Bóna2011、p。180。
  9. ^ Leonardo da Pisa(1202)、ファイル:Liber abbaci magliab f124r.jpg-Wikimedia Commons
  10. ^ Knuth、Donald(1968)、The Art of Computer Programming、vol。1、アディソンウェスリー、p。100、ISBN 978-81-7758-754-8フィボナッチが彼の作品を書く前に、シーケンスFnは、リズムパターンに長い間興味を持っていたインドの学者によってすでに議論されていました...ゴパラ(西暦1135年以前)とヘマチャンドラ(1150年頃)の両方が数字1、2、 3,5,8,13,21明示的に[P.Singh Historia Math 12(1985)229–44を参照] "p。100(3d ed).. ..
  11. ^ a b Livio 2003、p。197。
  12. ^ Agrawala、VS(1969)、PāṇinikālīnaBhāratavarṣa (Hn。)バラナシ-I:TheChowkhamba VidyabhawanSadgurushiShyaは、PingalaはPāṇiniの弟だったと書いています[Agrawala 1969、lb]。彼がPāṇiniの母方の叔父であったという別の意見があります[Vinayasagar1965、序文、121]。... Agrawala [1969、463–76]は、初期の学者の見解を考慮した慎重な調査の結果、パーニニは紀元前480年から410年の間に住んでいたと結論付けました。
  13. ^ Singh、Parmanand(1985)、「古代および中世インドのいわゆるフィボナッチ数」(PDF)Historia MathematicaAcademic Press12(3):232、doi10.1016 / 0315-0860(85)90021- 7
  14. ^ Velankar、HD(1962)、ジョードプルのカヴィ・ビラハンカの「Vṛttajātisamuccaya」:ラジャスタンオリエンタル研究所、p。101
  15. ^ Livio 2003、p。197–98。
  16. ^ Shah、Jayant(1991)、「A HistoryofPiṅgala'sCombinatorics」(PDF)ノースイースタン大学:41 、 2019年1月4日取得
  17. ^ 「フィボナッチの算盤の書(計算書)」ユタ大学、 2009年12月13日、 2018年11月28日検索
  18. ^ Hemenway、Priya(2005)、Divine Proportion:Phi In Art、Nature、and Science、New York:Sterling、pp。20–21、ISBN 1-4027-3522-7
  19. ^ ノット、ロン博士(2016年9月25日)、「自然のフィボナッチ数と黄金分割– 1」サリー大学、 2018年11月27日検索
  20. ^ ノット、ロン、フィボナッチのウサギサリー大学工学物理学部
  21. ^ ガードナー、マーティン(1996)、数学サーカス、アメリカ数学協会、p。153、ISBN 978-0-88385-506-5数学に貴重な貢献をしたレオナルドが今日記憶されているのは皮肉なことです。これは主に、19世紀のフランスの数論者エドゥアールリュカが...算盤の書の些細な問題に現れる数列にフィボナッチという名前を付けたためです。
  22. ^ ワイスタイン、エリックW.「ビネットのフィボナッチ数式」MathWorld
  23. ^ Ball 2003、p。156。
  24. ^ Ball 2003、pp。155–6。
  25. ^ ケプラー、ヨハネス(1966)、新年の贈り物:六角形の雪について、オックスフォード大学出版局、p。92、ISBN 978-0-19-858120-8
  26. ^ Strena seu de Nive Sexangula、1611
  27. ^ Gessel、Ira(1972年10月)、「Fibonacci is a Square」(PDF)The Fibonacci Quarterly10(4):417–19 、 2012年4月11日取得
  28. ^ Dijkstra、Edsger W.(1978)、フィボナッチに敬意を表して(PDF)
  29. ^ ルーカス1891、p。4.4。
  30. ^ Vorobiev、NikolaĭNikolaevich; Martin、Mircea(2002)、「Chapter 1」、Fibonacci Numbers、Birkhäuser、pp。5–6、ISBN 978-3-7643-6135-8
  31. ^ フラジョレ、フィリップ; Sedgewick、Robert(2009)、Analytic Combinatorics、Cambridge University Press、p。42、ISBN 978-0521898065
  32. ^ a b c ワイスタイン、エリックW.「フィボナッチ数」MathWorld
  33. ^ Glaister、P(1995)、 "Fibonacci power series"、The Mathematical Gazette79(486):521–25、doi10.2307 / 3618079JSTOR 3618079 
  34. ^ Borwein、95ページ、演習3bに従って引用されたLandau(1899)
  35. ^ André-Jeannin、Richard(1989)、「Irrationalitédela somme des reverses de sureessuitesrécurrentes」、Comptes Rendusdel'AcadémiedesSciences、SérieI 、308(19):539–41、MR 0999451 
  36. ^ ワイスタイン、エリックW.「ミリンシリーズ」MathWorld
  37. ^ Ribenboim、Paulo(2000)、My Numbers、My Friends、Springer-Verlag
  38. ^ Su、Francis E(2000)、「Fibonacci GCD's、please」、Mudd Math Fun Facts 、et al、HMC、 2009-12-14にオリジナルからアーカイブ、2007-02-23を取得
  39. ^ Williams、HC(1982)、「フィボナッチ商に関する注記"、Canadian Mathematical Bulletin25(3):366–70、doi10.4153 / CMB-1982-053-0hdl10338.dmlcz / 137492MR  0668957ウィリアムズはこの物件を「よく知られている」と呼んでいます。
  40. ^ 素数、リチャードクランドル、カールポメランス、スプリンガー、第2版、2005年、p。142。
  41. ^ ワイスタイン、エリックW.「フィボナッチ素数」MathWorld
  42. ^ Honsberger、Ross(1985)、「Mathematical Gems III」、AMS Dolciani Mathematical Expositions(9):133、ISBN 978-0-88385-318-4
  43. ^ Cohn、JHE(1964)、「平方フィボナッチ数について」、The Journal of the London Mathematical Society39:537–540、doi10.1112 / jlms / s1-39.1.537MR 0163867 
  44. ^ Pethő、Attila(2001)、「線形再帰シーケンスのディオファントス特性II」、Acta MathematicaAcademiaePaedagogicaeNyíregyháziensis17:81–96
  45. ^ ブゴー、Y; Mignotte、M; Siksek、S(2006)、「指数ディオファントス方程式への古典的およびモジュール式アプローチ。I。フィボナッチおよびルーカスの累乗」、アン。算数。2(163):969-1018、arXivmath / 0403046Bibcode2004math ...... 3046Bdoi10.4007 / annals.2006.163.969S2CID 10266596 
  46. ^ Ming、Luo(1989)、「三角形のフィボナッチ数について」(PDF)フィボナッチ数。27(2):98–108
  47. ^ Luca、Florian(2000)、 "Perfect Fibonacci and Lucas numbers"、Rendiconti del Circolo Matematico di Palermo49(2):313–18、doi10.1007 / BF02904236ISSN 1973-4409MR 1765401S2CID 121789033   
  48. ^ ブロハン、ケビンA。; ゴンザレス、マルコスJ。; ルイス、ライアンH。; ルカ、フロリアン; MejíaHuguet、V。Janitzio; Togbé、Alain(2011)、「倍積完全数のフィボナッチ数はありません」整数11a:A7、MR 2988067 
  49. ^ ルカ、フロリアン; MejíaHuguet、V。Janitzio(2010)、「2つのフィボナッチ数の比率である完全数について」InformaticaeのAnnales Mathematicae37:107–24、ISSN 1787-6117MR 2753031  
  50. ^ ノット、ロン、フィボナッチ数、英国:サリー
  51. ^ Ribenboim、Paulo(1996)、The New Book of Prime Number Records、ニューヨーク:Springer、p。64、ISBN 978-0-387-94457-9
  52. ^ Lemmermeyer 2000、pp。73–74、例。2.25–28。
  53. ^ Lemmermeyer 2000、pp。73–74、例。2.28。
  54. ^ Lemmermeyer 2000、p。73、例 2.27。
  55. ^ フィボナッチとルーカスの因数分解、Mersennusi <10000のFiのすべての既知の因子を収集します。
  56. ^ フィボナッチとルーカス数の因数分解、レッドゴルペ10000 < i <50000のFi )のすべての既知の因子を収集します。
  57. ^ フレイド、ピーター; Brown、Kevin S.(1993)、「Problems and Solutions:Solutions:E3410」、The American Mathematical Monthly99(3):278–79、doi10.2307 / 2325076JSTOR 2325076 
  58. ^ Weisstein、Eric W。「Fibonacci n -Step Number」MathWorld
  59. ^ ルーカス1891、p。7。
  60. ^ スタンレー、リチャード(2011)、列挙型組み合わせ論I(第2版)、ケンブリッジ大学 プレス、p。121、例1.35、ISBN 978-1-107-60262-5
  61. ^ Harizanov、Valentina(1995)、「Yuri V. Matiyasevichのレビュー、Hibertの第10の問題Modern Logic5(3):345–55
  62. ^ Pagni、David(2001年9月)、「Fibonacci Meets Pythagoras」、Mathematics in School30(4):39–40、JSTOR 30215477 
  63. ^ Stephenson、Kenneth(2005)、サークルパッキングの概要:離散分析関数の理論、ケンブリッジ大学出版局、ISBN 978-0-521-82356-2MR  2131318; 特に補題8.2(リング補題)の73〜74ページ、および付録Bのリング補題の318〜321ページを参照してください。
  64. ^ Knuth、Donald E(1997)、The Art of Computer Programming、vol。1:基本的なアルゴリズム(第3版)、Addison–Wesley、p。343、ISBN 978-0-201-89683-1
  65. ^ Adelson-Velsky、Georgy; Landis、Evgenii(1962)、「情報の編成のためのアルゴリズム」、USSR科学アカデミーの議事録(ロシア語)、146:263–266 Myron J.Ricciによるソビエト数学の英訳-Doklady 3:1259–1263、1962。
  66. ^ Avriel、M; Wilde、DJ(1966)、「対称フィボナッチ検索手法の最適性」、Fibonacci Quarterly(3):265–69
  67. ^ Amiga ROMカーネルリファレンスマニュアル、Addison–Wesley、1991
  68. ^ 「IFF」、マルチメディアWiki
  69. ^ ドゥアディ、S; Couder 、Y(1996)、「動的自己組織化プロセスとしての葉序」(PDF)Journal of Theoretical Biology178(3):255–74、doi10.1006 / jtbi.1996.0026 、オリジナル(PDF)からアーカイブ2006-05-26
  70. ^ ジョーンズ、ジュディ; Wilson、William(2006)、「Science」、不完全な教育、Ballantine Books、p。544、ISBN 978-0-7394-7582-9
  71. ^ Brousseau、A(1969)、「針葉樹のフィボナッチ統計」、Fibonacci Quarterly(7):525–32
  72. ^ 「ダヴィンチコードのマーク:B–」数学、楽しみのためのコンピュータサイエンス:CS4FN
  73. ^ スコット、TC; Marketos、P。(2014年3月)、フィボナッチ数列の起源について(PDF)MacTutor数学史アーカイブ、セントアンドリュース大学
  74. ^ Livio 2003、p。110。
  75. ^ Livio 2003、pp。112–13。
  76. ^ 「木のフィボナッチ数列の秘密」アメリカ自然史博物館、2011年、2013年5月4日にオリジナルからアーカイブ、 2019年2月4日取得
  77. ^ Prusinkiewicz、Przemyslaw; ハナン、ジェームズ(1989)、リンデンマイヤーシステム、フラクタル、および植物(生物数学の講義ノート)Springer-VerlagISBN 978-0-387-97092-9
  78. ^ Vogel、Helmut(1979)、「ヒマワリの頭を構築するためのより良い方法」、Mathematical Biosciences44(3–4):179–89、doi10.1016 / 0025-5564(79)90080-4
  79. ^ Livio 2003、p。112。
  80. ^ Prusinkiewicz、Przemyslaw ; Lindenmayer、Aristid(1990)、"4"The Algorithmic Beauty of Plants、Springer-Verlag、  pp。101–107ISBN 978-0-387-97297-8
  81. ^ 「自然界に現れるフィボナッチ数列」(PDF)フィボナッチ四半期1(1):53–56、1963
  82. ^ a b Hutchison、Luke(2004年9月)、「Growing the Family Tree:The Power of DNA in Reconstructing Family Relationships」(PDF)Proceedings of the First Symposium on Bioinformatics and Biotechnology(BIOT-04)2016年9月検索03
  83. ^ ハメロフ、スチュアート; ペンローズ、ロジャー(2014年3月)、「宇宙の意識:「オーチOR」理論のレビュー」、Physics of Life Reviews、Elsevier、11(1):39–78、Bibcode2014PhLRv..11 .. .. 39Hdoi10.1016 / j.plrev.2013.08.002PMID 24070914 
  84. ^ Livio 2003、98〜99ページ。
  85. ^ 「ゼッケンドルフ表現」、数学百科事典
  86. ^ パトラナビス、D。; Dana、SK(1985年12月)、「端末減衰測定とフィボナッチ数を使用したシングルシャント障害診断」、IEEE Transactions on Instrumentation and Measurement、IM-34(4):650–653、doi10.1109 / tim.1985.4315428
  87. ^ Brasch、T。von; Byström、J。; Lystad、LP(2012)、「最適制御とフィボナッチ数列」、Journal of Optimization Theory and Applications154(3):857–78、doi10.1007 / s10957-012-0061-2hdl11250/180781S2CID 8550726 
  88. ^ Livio 2003、p。176。
  89. ^ Livio 2003、p。193。

引用された作品

外部リンク