フィボナッチ数列

出典: 謎の百科事典もどき『エンペディア（Enpedia）』
ナビゲーションに移動 検索に移動

フィボナッチ数列（ふぃぼなっちすうれつ）にはさまざまな定義があり、人によって理解のしかたが異なるので、説明が難しい。

概要[編集]

素朴な定義としては、数論的なものがある。「初項が１で次項も１、そこから先は前前項と前項の和」という説明である。
{1, 1, 2, 3, 5, 8, 13, 21, 34, ……} と続く。

以下の仮定を置く、ウサギの数として説明することもある。

  • 1年目に0歳のウサギが1匹いる。
  • ウサギは2歳になると、1匹の子ウサギ(0歳)を産む。(一匹なのに産むなんて無性生殖じゃねぇか、ということは考えない。)

つまり、バイバインより少し増加速度の遅いウサギである。
このとき、数列はn年目のウサギの数になっている。

漸化式による一般化[編集]

3項間漸化式として記述し、解くことを考える。

漸化式による表現[編集]

フィボナッチ数列は、漸化式を用いて以下のように表現できる。

  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a(n+2)=a(n+1)+a(n)}
  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a(1)=a(2)=1} (初期値)

特性方程式[編集]

一つ目の式より、特性方程式

  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a^2-a-1=0}

を得る。この二次方程式の解は2次方程式の解の公式より

  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a=\frac{1\pm\sqrt{1+4}}{2}=\frac{1\pm\sqrt{5}}{2}}

となって黄金比と、その有理数からみた共役な無理数が出てくる。
ここで、以下でよく使う黄金比構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \varphi=\frac{1+\sqrt{5}}{2}} の性質を述べておく。黄金比は特性方程式の解だったので、
構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \varphi^2-\varphi-1=0} より構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \varphi^2-\varphi=1} であり、構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \varphi-1=\varphi^{-1}}
また、構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \frac{1-\sqrt{5}}{2}=1-\varphi=-\varphi^{-1}}

第一の書き換え[編集]

よって、黄金比を用いて漸化式は次のように書き換えられる。

  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a(n+2)-\varphi a(n+1)=(1-\varphi)(a(n+1)-\varphi a(n))}

ここで、構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle b(n)=a(n+1)-\varphi a(n)} という数列を導入すると、等比数列の問題に帰着できて

  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle b(n+1)=(1-\varphi)b(n)}
  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle b(1)=a(2)-\varphi a(1)=1-\varphi} (初期値)

である。これを等比数列の問題として解くと、

  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle b(n)=b(1)(-\varphi^{-1})^{n-1}=(1-\varphi)^n}

さらに、構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle b(n)=a(n+1)-\varphi a(n)} より構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a(n+1)=\varphi a(n)+b(n)} なので

  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a(n+1)=\varphi a(n)+(1-\varphi)^n}

第二の書き換え[編集]

また、漸化式は次のようにも書き換えられる。

  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a(n+2)-(1-\varphi)a(n+1)=\varphi (a(n+1)-(1-\varphi)a(n))}

ここで、構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c(n)=a(n+1)-(1-\varphi)a(n)} という数列を導入すると、等比数列の問題に帰着できて

  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c(n+1)=\varphi c(n)}
  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c(1)=a(2)-(1-\varphi)a(1)=\varphi} (初期値)

である。これを等比数列の問題として解くと、

  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c(n)=c(1)\varphi^{n-1}=\varphi^n}

さらに、構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c(n)=a(n+1)-(1-\varphi)a(n)} より構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a(n+1)=(1-\varphi)a(n)+c(n)} なので

  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a(n+1)=(1-\varphi)a(n)+\varphi^n}

結果の結合[編集]

上記より、

  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a(n+1)=\varphi a(n)+(1-\varphi)^n}
  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a(n+1)=(1-\varphi)a(n)+\varphi^n}

よって、

  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (1-\varphi)a(n+1)=\varphi(1-\varphi)a(n)+(1-\varphi)^{n+1}}
  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \varphi a(n+1)=\varphi(1-\varphi)a(n)+\varphi^{n+1}}

2式の差から

  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (2\varphi-1)a(n+1)=\varphi^{n+1}-(1-\varphi)^{n+1}}

よって、

  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a(n+1)=\frac{\varphi^{n+1}-(1-\varphi)^{n+1}}{2\varphi-1}}

n+1をnにして、また黄金比を代入すると、

  • 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a(n)=\frac{\frac{1+\sqrt{5}}{2}^n-\frac{1-\sqrt{5}}{2}^n}{\sqrt{5}}}

となった。これが答えである。実際にn=1,2,3と代入していくと確かにあっている。

結果の考察[編集]

このことから、一般式に無理数が含まれていても整数の数列になる数列が存在することがわかる。

さらにnが十分に大きければ、 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle |\frac{1+\sqrt{5}}{2}|>1} ,構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle |\frac{1-\sqrt{5}}{2}|<1} より、近似的に 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a(n+1)=\varphi a(n)} となって、フィボナッチ数列は指数関数的に爆発していることがわかる。 構文解析に失敗 (SVG（ブラウザのプラグインで MathML を有効にすることができます）: サーバー「https://ja.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 1<\varphi=\frac{1+\sqrt{5}}{2}<2} なので、バイバインよりは少しマシなウサギという説明に合致する。

人間生活との関わり・利用[編集]

ソフトウェア業界に入ると、プログラミング研修において最初にやらされるのがユークリッドの互除法であるが、このあたりは解っている奴は五分もかからずにプログラムを書き上げてしまうので、頭の悪い上司に目をつけられてハラスメントの標的になったりする。

関連項目[編集]

類似の数列[編集]

脚注[編集]

「https://enpedia.org/w/index.php?title=フィボナッチ数列&oldid=1053620」から取得