フィボナッチ数列の8つの性質(一般項・黄金比・互いに素)

フィボナッチ数列

フィボナッチ数列(fibonacci sequence)とは,

  • 最初の2つは 11 で,
  • 3つめ以降は「前の2つを足したもの」

になる数列のこと。つまり,

1,1,2,3,5,8,13,21,34,1,1,2,3,5,8,13,21,34,\dots

フィボナッチ数列の定義

フィボナッチ数列の意味と,8つの性質を紹介します。

フィボナッチ数列とは

フィボナッチ数列1,1,2,3,5,8,13,21,34,55, 1,1,2,3,5,8,13,21,34,55, \cdots は,最初の2つが1で,それ以降は「前の2つを足したもの」で定まる数列です。

漸化式を使うと, F1=F2=1,Fn=Fn1+Fn2(n3) F_1=F_2=1 ,\: F_{n}=F_{n-1}+F_{n-2}\:(n\geq 3) で定まる数列と言えます。

フィボナッチ数列にあらわれる数をフィボナッチ数と言います。例えば,5588 はフィボナッチ数です。

フィボナッチ数列はいろいろな分野で登場します。大学入試問題では,数列の問題としてだけでなく,場合の数の問題(漸化式をたてて解く問題)や整数問題に登場することもあります。

フィボナッチ数列の性質を5つ紹介していきます。

一般項(ビネの公式)

性質1(ビネの公式)

フィボナッチ数列の nn 番目の数は,

Fn=15{(1+52)n(152)n}F_n=\dfrac{1}{\sqrt{5}}\left\{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right\}

と表せる。

これを「ビネの公式」と言います。

15{(1+52)3(152)3}\dfrac{1}{\sqrt{5}}\left\{\left(\dfrac{1+\sqrt{5}}{2}\right)^3-\left(\dfrac{1-\sqrt{5}}{2}\right)^3\right\}

という一見複雑な式を計算すると,それはフィボナッチ数列の3項目である 22 になる。

一般項の式には無理数が含まれていますが,計算してみると整数になるというのは不思議ですね。

証明は,三項間漸化式の3通りの解き方にある方法で漸化式を解くだけです。

証明

Fn=Fn1+Fn2F_{n}=F_{n-1}+F_{n-2} という漸化式を解きたい。

特性方程式 x2=x+1x^2=x+1 の解を α=1+52\alpha=\dfrac{1+\sqrt{5}}{2}β=152\beta=\dfrac{1-\sqrt{5}}{2} とおくと,α+β=1\alpha+\beta=1αβ=1\alpha\beta=-1 より

Fn=(α+β)Fn1αβFn2 F_n=(\alpha+\beta)F_{n-1}-\alpha\beta F_{n-2}

これを変形して,

FnαFn1=β(Fn1αFn2) F_n-\alpha F_{n-1}=\beta(F_{n-1}-\alpha F_{n-2})

よって,FnαFn1F_n-\alpha F_{n-1} は公比 β\beta の等比数列となる:

FnαFn1=βn2(F2αF1)=βn1 F_n-\alpha F_{n-1}=\beta^{n-2} (F_2-\alpha F_1)=\beta^{n-1}

同様にして,

FnβFn1=αn2(F2βF1)=αn1 F_n-\beta F_{n-1}=\alpha^{n-2} (F_2-\beta F_1)=\alpha^{n-1}

この2式から Fn1F_{n-1} を消去して FnF_n について解くと Fn=αnβnαβ=15{(1+52)n(152)n}\begin{aligned} F_n &= \dfrac{\alpha^n-\beta^n}{\alpha-\beta}\\ &= \dfrac{1}{\sqrt{5}}\left\{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right\} \end{aligned} が得られる。

補足:高校数学で登場する三項間漸化式は,ほとんどの場合特性方程式の解が整数になりますが,フィボナッチ数列の特性方程式の解は無理数なので計算が多少複雑でした。

性質1(ビネの公式)の証明は帰納法でもできます。

証明の概要

n=1n=1n=2n=2 のときビネの公式が正しいことは簡単に確認できる。

n=kn=kn=k+1n = k+1 のときにビネの公式が正しいと仮定すると,

Fk+2=αk+1βk+1αβ+αkβkαβ=αk+2βk+2αβ\begin{aligned} F_{k+2} &= \dfrac{\alpha^{k+1}-\beta^{k+1}}{\alpha-\beta}+\dfrac{\alpha^{k}-\beta^{k}}{\alpha-\beta}\\ &= \dfrac{\alpha^{k+2}-\beta^{k+2}}{\alpha-\beta} \end{aligned}

(α+1=α2,β+1=β2)\because \alpha+1=\alpha^2, \beta+1=\beta^2)

となり,n=k+2n=k+2 のときも正しい。

黄金比との関係

性質2

フィボナッチ数列の隣り合う2項の比は黄金比に近づいていく。

黄金比とは,α=1+52\alpha=\dfrac{1+\sqrt{5}}{2} のことです。

いくつか計算してみましょう。

  • 1+52=1.618\dfrac{1+\sqrt{5}}{2} = 1.618\cdots
  • F3F2=2\dfrac{F_3}{F_2} = 2
  • F5F4=53=1.6666\dfrac{F_5}{F_4} = \dfrac{5}{3} = 1.6666\cdots
  • F9F8=3421=1.6190\dfrac{F_9}{F_8} = \dfrac{34}{21} = 1.6190\cdots

もっと計算して F100001F100000\dfrac{F_{100001}}{F_{100000}} を計算すると,黄金比とほぼ等しくなるでしょう。

この黄金比は性質1に登場した数字でもあることがポイントです。

証明

性質1(ビネの公式)より,

limnFn+1Fn=limnαn+1βn+1αnβn=α \lim_{n\to\infty}\dfrac{F_{n+1}}{F_n}=\lim_{n\to\infty}\dfrac{\alpha^{n+1}-\beta^{n+1}}{\alpha^n-\beta^n}=\alpha

(α>β)(\because \alpha > \beta)

隣接する二項は互いに素

性質3

フィボナッチ数列 1,1,2,3,5,8,13,21,1,1,2,3,5,8,13,21,\dots について,どの隣り合う2項も互いに素(最大公約数は1)

例えば,881313 の最大公約数は1です。

性質3を証明してみましょう。

証明

FkF_kFk1F_{k-1} が共通の約数 p2p\geq 2 を持つと仮定すると,

Fk=mp, Fk1=np F_k=mp,\ F_{k-1}=np (ただし m,n,pm, n, p は整数)と書ける。

漸化式より,

Fk2=FkFk1=(mn)p F_{k-2}=F_{k}-F_{k-1}=(m-n)p

pp の倍数なので,

Fk1F_{k-1}Fk2F_{k-2} も共通因数 pp を持つ。

これを繰り返すと F2F_2F1F_1 も共通因数 pp を持つ。

これは F2=F1=1F_2=F_1=1 に矛盾

このように,通常の数学的帰納法とは逆向きに進めていく帰納法を後ろ向き帰納法(無限降下法)といいます。数学的帰納法に関しては様々なタイプがあるので,数学的帰納法のパターンまとめを参考にしてみてください。

その他の性質

フィボナッチ数列同士の関係式

性質4

Fm+n=Fm1Fn+FmFn+1F_{m+n}=F_{m-1}F_{n}+F_{m}F_{n+1}

ただし,m,nm,n は任意の正の整数で,F0=0F_0=0 とする。

フィボナッチ数列 1,1,2,3,5,8,13,21,34,55,1,1,2,3,5,8,13,21,34,55,\cdots について,2×8+3×13=552\times 8+3\times 13=55 などが成立するというおもしろい性質です。

性質1(ビネの公式)を使って右辺を計算すると左辺と一致することがわかります。また,以下のように nn に関する帰納法でも証明できます。

証明
  • n=1n=1 のとき,Fm+1=Fm1F1+FmF2F_{m+1}=F_{m-1}F_1+F_{m}F_2 はフィボナッチ数列の漸化式そのものであり成立。

  • n=2n=2 のとき,フィボナッチ数列の漸化式を使うと Fm+2=Fm+1+Fm=Fm1+2Fm=Fm1F2+FmF3\begin{aligned} F_{m+2}&=F_{m+1}+F_{m}\\ &=F_{m-1}+2F_{m}\\ &=F_{m-1}F_2+F_{m}F_{3} \end{aligned} となり成立。

  • n=kn=kn=k1n=k-1 の場合も正しいと仮定して n=k+1n=k+1 の場合を計算すると, Fm+k+1=Fm+k+Fm+k1=(Fm1Fk+FmFk+1)+(Fm1Fk1+FmFk)=Fm1(Fk+Fk1)+Fm(Fk+1+Fk)=Fm1Fk+1+FmFk+2\begin{aligned} F_{m+k+1}&=F_{m+k}+F_{m+k-1}\\ &=(F_{m-1}F_{k}+F_{m}F_{k+1})+(F_{m-1}F_{k-1}+F_{m}F_{k})\\ &=F_{m-1}(F_{k}+F_{k-1})+F_{m} (F_{k+1}+F_{k})\\ &=F_{m-1}F_{k+1}+F_{m}F_{k+2} \end{aligned} となり成立。

性質5(カッシーニの定理)

Fn+1Fn1Fn2=(1)nF_{n+1} F_{n-1} - {F_n}^2 = (-1)^n

ただし,nn は任意の正の整数で,F0=0F_0=0 とする。

これも帰納法で示しましょう。

証明
  • n=1n=1 のとき,F2F0F12=01=(1)2F_2 F_0 - {F_1}^2 = 0-1= (-1)^2 より成立する。

  • n=kn = k で成立すると仮定する。
    この下で n=k+1n = k+1 のときは Fk+2FkFk+12=(Fk+1+Fk)FkFk+12=Fk2+Fk+1(FkFk+1)=Fk2Fk+1Fk1=(Fk+1Fk1Fk2)=(1)k+1\begin{aligned} &F_{k+2} F_{k} - {F_{k+1}}^2\\ &= (F_{k+1} + F_k) F_k - {F_{k+1}}^2\\ &= {F_k}^2 + F_{k+1} (F_k - F_{k+1})\\ &= {F_k}^2 - F_{k+1} F_{k-1}\\ &= - (F_{k+1} F_{k-1} - {F_k}^2)\\ &= (-1)^{k+1} \end{aligned} より成立する。

よって数学的帰納法より従う。

添え字との関連

次に紹介する性質はフィボナッチ数の性質でも特に面白いものとなっています。

性質6(Divisibility)

m,nm,n33 以上の整数とする。

FnF_nFmF_m の倍数     \iff nnmm の倍数。

フィボナッチ数列 1,1,2,3,5,8,13,21,34,55,1,1,2,3,5,8,13,21,34,55,\cdots について, 33 つおきに F3=2F_3=2 の倍数が登場,44 つおきに F4=3F_4=3 の倍数が登場,55 つおきに F4=5F_4=5 の倍数が登場,という性質です!

性質6は性質4と帰納法で証明できます。ProofWiki

ゼッケンドルフの定理

性質7

任意の正の整数は「連続しない」フィボナッチ数の和で一意に表すことができる。

定理の意味と証明はゼッケンドルフの定理とその証明で説明しています。

余りの周期性

性質8

pp を素数とし,p2,5p\neq 2,5 とする。フィボナッチ数列を pp で割った余りを並べた数列の周期について,

pp55 で割った余りが 11 または 44 なら,周期は p1p-1 の約数

pp55 で割った余りが 22 または 33 なら,周期は 2(p+1)2(p+1) の約数

詳しくは数列における余りの周期性(特にフィボナッチ数列)で説明しています。

一般化

初項を a0=2a_0 = 2 に取り換えるとまた異なる面白い数列が現れます。→ リュカ数の意味とおもしろい性質

an=an1+an2+an3 a_{n} = a_{n-1} + a_{n-2} + a_{n-3} のように漸化式の項数を増やした数列もおもしろいです。 → トリボナッチ数列、テトラナッチ数列とその一般項

高校時代はじめてビネの公式を見たときはとても感動しました。

Tag:数学的帰納法をわかりやすく【例題3問、応用5パターン】

Tag:漸化式の解き方11パターンと応用例まとめ

Tag:数学Bの教科書に載っている公式の解説一覧