このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

フィボナッチ数列

[定義]フィボナッチ数列{un}は次によって定義される。
u_0~=~0,u_1=1,~u_{n-2}~+~u_{n-1}=u_n,~\,~(n~\ge~2)

フィボナッチ数列の性質

[定理]{un}:フィボナッチ数列とする。 u_{n+m}~=~u_{n-1}~u_m~+~u_n~u_{m+1}~\,~(n~\ge~1,m~\ge~0)

[証明]nを固定して、mについての数学的帰納法で証明する。

[1]m=0の場合

これは条件u_0~=~0,u_1=1により、u_n=u_{n-1}u_0~+~u_n~u_{1}=u_nとなり、明らかに成り立つ。

[2]m=1の場合

u_{n+1}
=~u_{n-1}~u_1~+~u_n~u_{2}
=~u_{n-1}~+~u_n (∵u_1=u_2=1より)

これはフィボナッチ数列の定義そのものであるので、成り立つ。

[3]m=k,k+1の場合に以下が成り立つと仮定する。

  • u_{n+k}~=~u_{n-1}~u_k~+~u_n~u_{k+1} ←(*)
  • u_{n+k+1}~=~u_{n-1}~u_{k+1}~+~u_n~u_{k+2} ←(**)

このとき、m=k+2の場合を考える。

(右辺)
=u_{n-1}~u_{k+2}~+~u_n~u_{k+3}

(左辺)
=u_{n+k+2}
=u_{n+k}~+~u_{n+k+1} (∵フィボナッチ数列の定義)
=u_{n-1}~u_k~+~u_n~u_{k+1}~+~u_{n-1}~u_{k+1}~+~u_n~u_{k+2} (∵(*)(**))
=u_{n-1}~(u_k~+~u_{k+1})~+~u_n(u_{k+1}~+~u_{k+2}) (∵フィボナッチ数列の定義)
=u_{n-1}~u_{k+2}~+~u_n~u_{k+3}

よって、m=k+2の場合も成り立つ。

したがって、数学的帰納法により、題意が示される。 □

[定理]{un}:フィボナッチ数列とする。 m,n≧1とする。
そのとき、umnはunで割り切れる。

[証明]nを固定して、mについての数学的帰納法で証明する。

[1]m=1の場合

unはunを割り切るので、成り立つ。

[2]m=kの場合、即ちuknはunで割り切れると仮定する。

ここで、m=k+1を考える。

u_{(k+1)n}
=u_{nk+n}
=u_{nk-1}u_n~+~u_{nk}u_{n+1} (∵u_{n+m}~=~u_{n-1}~u_m~+~u_n~u_{m+1}

これはunで割り切れる。

よって、m=k+1の場合も成り立つ。

したがって、数学的帰納法により、題意が示される。 □

[例]u15=610は、u5=5でも、u3=2でも割り切れる。 ◇

 {un}:フィボナッチ数列とする。このとき、レオナルドは次が成り立つことを予想した。

[1]nが素数のときは、unも素数である。
[2]n=4のときを除けば、unが素数になるときは、nが素数のときに限る。

 しかし、この予想は間違っている。
 [1]において、n≦17までの素数に対しては正しいが、u19=4181(=37×113)は素数ではない。

 ただし、[2]の方は正しいことが証明されている。

[定理]{un}:フィボナッチ数列とする。 n=4のときを除けば、unが素数になるときは、nが素数のときに限る。

[証明]nが素数でないとして、n=kl(k,l≧2)とおく。

[定理]「m,n≧1とする。このとき、umnはunで割り切れる」より、un、即ちuSUB{kl}は、ukおよびulによって割り切れる。
よって、unは素数ではない。

これの対偶を取ると、題意を満たす。 □

[補講]この定理の証明において、uSUB{k}=uSUB{l}=1とすると、unは素数ではないとは限らないので、この議論が通用しない。

uk=ul=1となるのは、k=l=2の場合だけ、即ちn=4の場合である。

よって、このn=4を除外している。 ◇

[定理]{un}:フィボナッチ数列とする。
隣接するフィボナッチ数unとun+1は互いに素である。

[証明]unとun+1の共役数をdとする。
すると、d~|~u_nかつd~|~u_{n+1}が成り立つ。

u_{n+1}~~=~u_n~+~u_{n-1}
u_{n+1}~-~u_n~=~u_{n-1}
d~|~u_{n-1} (∵d~|~u_nかつd~|~u_{n+1}より)

さらに、d~|~u_{n-2}

同様にこれを続けて、d~|~u_{1}

u1=1なので、d=1になる。

ゆえに、(u_n,~u_{n+1})=1 □

[定理]{un}:フィボナッチ数列とする。
nq>1とする。
すると、unq-1とunは互いに素である。

[証明]SUB{nq-1}とunの共役数をdとする。
すると、d~|~u_{nq-1}かつd~|~u_{n}が成り立つ。

[定理]「m,n≧1とする。そのとき、umnはunで割り切れる」により、u_n|u_{nq}が成り立つ。

これとd~|~u_{n}より、d~|~u_{nq}が成り立つ。

よって、隣り合うフィボナッチ数uSUB{nq-1},uSUB{nq}はdで割り切れる。

ここで、[定理]「隣接するフィボナッチ数unとun+1は互いに素である」により、d=1になる。

ゆえに、(u_{nq-1},~u_{n})=1 □

[定理]{un}:フィボナッチ数列とする。
m≧n≧1とする。
このとき、u_n~|~u_mなら、n|mである。

 これは、[定理]「m,n≧1とする。そのとき、umnはunで割り切れる」の逆を意味する。

[証明]mをnで割って、その商をq、余りをrとする。すると、次が成り立つ。

m=qn+r,~(0~\le~r~<~n)

r≠0と仮定して矛盾を導く。

[定理]「u_{n+m}~=~u_{n-1}~u_m~+~u_n~u_{m+1}~\,~(n~\ge~1,m~\ge~0)」により、次が成り立つ。

u_{qn+r}~=~u_{qn-1}~u_r~+~u_{qn}~u_{r+1}

仮定により、左辺のu_{qn+r}~=u_mは、u_nで割り切れる。

[定理]「m,n≧1とする。そのとき、umnはunで割り切れる」により、右辺のu_{qn}は、u_nで割り切れる。

よって、u_n~|~u_{qn-1}~u_rが成り立つ。

しかし、[定理]「nq>1とする。すると、unq-1とunは互いに素である」により、u_n~|~u_rが成り立つ。

一方、r<nなので、u_r~<~u_nであるが、u_n~|~u_rと矛盾する。 □

[定理]自然数m,nの最大公約数を(m,n)、同様にum,unの最大公約数を(um,un)と書くと、次の関係が成り立つ。
(u_m,~u_n)=u_{(m,n)}

[証明]n<mとしても一般性は失われない。

ユークリッドの互除法により、文字を以下のように置く。

  • m=nq_0+r_1,~\,~(0~<~r_1~<~n)
  • n=r_1q_1+r_2,~\,~(0~<~r_2~<~r_1)
  • r_1=r_2q_2+r_3,~\,~(0~<~r_3~<~r_2)
  • r_{k-2}~=~r_{k-1}~q_{k-1}~+~r_k,~\,~(0<r_k<r_{k-1}
  • r_{k-1}~=~r_k~q_k
  • r_k~=~(m,n)

すると、(u_m,~u_n)は次のように展開できる。

(左辺)
(u_m,~u_n)
=~(u_{nq_0~+~r_1},~u_n) (∵m=nq_0~+~r_1より)
=~(u_{nq_0~-1}u_{r_1}~+~u_{nq_0}~u_{r_1~+~1},~u_n) (∵[定理]「u_{n+m}~=~u_{n-1}~u_m~+~u_n~u_{m+1}~\,~(n~\ge~1,m~\ge~0)」より)
=~(u_{nq_0~-1}u_{r_1}~,~u_n) (∵[定理]「c|b⇒(a+b,c)=(a,c)」)
=~(u_{r_1},~u_n) (∵[定理]「nq>1とする。すると、unq-1とunは互いに素である」と[定理]「(b,c)=1⇒(ab,c)=(a,c)」)
=~(u_n,~u_{r_1})

同様にして、次が成り立つ。

  • (u_n,~u_{r_1})~=~(u_{r_1},~u_{r_2})
  • (u_{r_1},~u_{r_2})~=~(u_{r_2},~u_{r_3})
  • (u_{r_{k-2}},~u_{r_{k-1}})~=~(u_{r_{k-1}},~u_{r_k})

ここで、r_k~|~r_{k-1}だから、[定理]「m,n≧1とする。そのとき、umnはunで割り切れる」により、u_{r_k}~|~u_{r_{k-1}}が成り立つ。

よって、(u_{r_{k-1}}~,~u_{r_{k}})=u_{r_k}

ゆえに、次が成り立つ。

(u_m,u_n)~=~(u_n,u_{r_1})~=~(u_{r_1},~u_{r_2})~=~\cdots~=~(u_{r_{k-1}}~,~u_{r_{k}})~=~u_{r_k}~=~u_{(m,n)} □

[例]m=12,n=18とする。

(m,n)=(12,18)=6なので、以下が成り立つ。

(um,un)=(u12,u18)=(144,2584)=8=u6=u(12,18) ◇

[系]「フィボナッチ数umがunで割り切れる」⇔「mがnで割り切れる」

[証明][定理]「(u_m,~u_n)=u_{(m,n)}」より成り立つ。 □

フィボナッチ数を割り切るかどうか

[定理]{un}:フィボナッチ数列とする。
このとき、以下が成り立つ。

  • 2~|~u_m~\Longleftrightarrow~3|m
  • 3~|~u_m~\Longleftrightarrow~4|m
  • 5~|~u_m~\Longleftrightarrow~5|m
  • 8~|~u_m~\Longleftrightarrow~6|m
  • 13~|~u_m~\Longleftrightarrow~7|m

[証明][系]「「フィボナッチ数umがunで割り切れる」⇔「mがnで割り切れる」」より、以下が成り立つ。

  • u_3~|~u_m~\Longleftrightarrow~3|m
    • u3=2なので、2~|~u_m~\Longleftrightarrow~3|mが成り立つ。
  • u_4~|~u_m~\Longleftrightarrow~4|m
    • u4=3なので、3~|~u_m~\Longleftrightarrow~4|mが成り立つ。
  • u_5~|~u_m~\Longleftrightarrow~5|m
    • u5=5なので、5~|~u_m~\Longleftrightarrow~5|mが成り立つ。
  • u_6~|~u_m~\Longleftrightarrow~6|m
    • u6=8なので、8~|~u_m~\Longleftrightarrow~6|mが成り立つ。
  • u_7~|~u_m~\Longleftrightarrow~7|m
    • u7=13なので、13~|~u_m~\Longleftrightarrow~7|mが成り立つ。

 フィボナッチ数を素因数分解するときに、この結果が成り立つ。

 しかし、4はフィボナッチ数ではないため、umが4で割り切れるかどうかを決めるには別のアプローチが必要である。

[定理]{un}:フィボナッチ数列とする。
このとき、以下が成り立つ。

  • 4~|~u_m~\Longleftrightarrow~6|m
  • 6~|~u_m~\Longleftrightarrow~12|m
  • 7~|~u_m~\Longleftrightarrow~8|m

[証明][1]mimetex("4 | u_m \Longleftrightarrow 6|m");を示す。

[定理]「(u_m,~u_n)=u_{(m,n)}」より、(u_m,~u_6)=u_{(m,6)}が成り立つ。
u6=8なので、次が成り立つ。

(u_m,~8)=u_{(m,6)} ←(*)

(u_m,~8)は8の約数なので、8 or 4 or 2 or 1である。

ここで、6|mならば、8|u_mである。
そのため、当然4|u_mである。

そのため、(u_m,~8)は8 or 4である。

[1](u_m,~8)=8の場合

8~|~u_mなので、定理より6|mである。

[2](u_m,~8)=4の場合

(*)より、u_{(m,6)}=4"となり、これはフィボナッチ数が4となり矛盾する。

ゆえに、4~|~u_m~\Longleftrightarrow~6|m

[2]6~|~u_m~\Longleftrightarrow~12|mを示す。

6~|~u_m
⇔「2~|~u_m,~3~|~u_m
⇔「3|m~,~4|m
⇔「12|m

[3]7~|~u_m~\Longleftrightarrow~8|mを示す。

(i)[定理]「(u_m,~u_n)=u_{(m,n)}」により、次が成り立つ。

(u_m,~u_8)=u_{(m,8)}
(u_m,~21)=u_{(m,8)} (∵u8=21)

よって、u_{(m,8)}は21の約数だから、21 or 7 or 3 or 1である。

一方、u_{(m,8)}はumの約数であるから、7|umと仮定すると、u_{(m,8)}は21 or 7である。

7はフィボナッチ数ではないので、u_{(m,8)}=21でなければならない。

よって、フィボナッチ数u8=21より、(m,8)=8である。

(ii)8|mならば、[定理]「」により、umはu8(=21)で割り切れる。

よって、7でも割り切れる。 □

 以上の議論を一般化すると、次の定理になる。

[定理]a|u_m~\Longleftrightarrow~n|m
ただし、a|unであるような最小のフィボナッチ数unを取ったものとする。

[証明]もしa|umならば、a|(u_m,u_n)である。

[定理]

[1]⇒を示す。

(u_m,~u_n)=u_{(m,n)}」により、a|u_{(m,n)}が成り立つ。

一方、unはaの倍数となる最小のフィボナッチ数として定義したので、n~\le~(m,n)

しかし、(m,n)はnの約数なので、n=(m,n)である。
つまり、n|mである。

[2]←を示す。

[定理]「m,n≧1とする。そのとき、umnはunで割り切れる」と仮定「n|m」より、u_n~|~u_mが成り立つ。

よって、a~|~u_m □

 上記の定理における、フィボナッチ数unはaの倍数となる。このようなフィボナッチ数が存在することは次の定理によって保証される。

[定理]a≧2を自然数とすると、最初のa2個のフィボナッチ数u_1,~u_2,\cdots,~u_{a^2}の少なくともどれか1つはaで割り切れる。

[証明]ukをaで割ったときの余りを\bar{u_k}と置き、次のa2+1個の対を考える。

<~\bar{u_1},~\bar{u_2}>,~<~\bar{u_2},~\bar{u_3}>,~\cdots,~<~\bar{u_{a^2}},~\bar{u_{a^2~+~1}}>,~<~\bar{u_{a^2~+~1}},~\bar{u_{a^2~+~2}}>

\bar{u_k}は0,1,2,…,a-1のどれかであるから、\bar{u_k}はa通りあるため、対の組み合わせはa2通りある。
上記の対はa2+1個あり、鳩ノ巣原理より、そこには同じものが必ずある。

ここで、<~\bar{u_k},~\bar{u_{k+1}}>を少なくとも2度現れる対で、最小のkとする。

そのとき、k=1であることを示す。

k>1と仮定して、矛盾を導く。

<~\bar{u_l},~\bar{u_{l+1}}>(ただし、l>k)が、対<~\bar{u_k},~\bar{u_{k+1}}>に等しいとする。
即ち、\bar{u_k}~=~\bar{u_l},~\bar{u_l}~=~\bar{u_{l+1}}

一方、フィボナッチ数列の定義より、次が成り立つ。

  • u_{k-1}~=~u_{k+1}~-~u_k
  • u_{l-1}~=~u_{l+1}~-~u_l

この2式の両辺をaで割ると次が得られる。 なお、ここでukはaで割ったときの余りを\bar{u_k}であることを使った。

  • aq_{k-1}~+~\bar{u_{k-1}}~=~q(q_{k+1}~-q_k)~+~\bar{u_{k+1}}~-~\bar{u_k}
  • aq_{l-1}~+~\bar{u_{l-1}}~=~q(q_{l+1}~-q_l)~+~\bar{u_{l+1}}~-~\bar{u_l}

これらの余り\bar{u_{k+1}}~-~\bar{u_k},~\bar{u_{l+1}}~-~\bar{u_l}について比べる。

[1]\bar{u_{k+1}}~-~\bar{u_k}~\ge~0のとき

a~>~\bar{u_{k+1}}~-~\bar{u_k},~a~>~\bar{u_{k-1}}"なので、\bar{u_{k-1}}~=~\bar{u_{k+1}}~-~\bar{u_k}である。

そのとき、\bar{u_{l+1}}~-~\bar{u_l}~=~\bar{u_{k+1}}~-~\bar{u_k}~\ge~0だから、\bar{u_{l-1}}~=~\bar{u_{l+1}}~-~\bar{u_l}である。

よって、\bar{r_{k-1}}~=~\bar{u_{l-1}}が成り立つ。

[2]\bar{u_{k+1}}~-~\bar{u_k}~<~0のとき

aq_{k-1}~+~\bar{u_{k-1}}~=~a(q_{k+1}~-~q_k~-1)~+~a~+~\bar{u_{k+1}}~-~\bar{u_k}

と書き直すと、\bar{u_{k-1}}~=~\bar{u_{k+1}}~-~\bar{u_k}~+~a~(>0)で、\bar{u_{l-1}}についても同様である。

よって、\bar{r_{k-1}}~=~\bar{u_{l-1}}が成り立つ。

したがって、いずれにしても\bar{r_{k-1}}~=~\bar{u_{l-1}}が成り立つ。
つまり、対<~\bar{u_{k-1}},~\bar{u_{k}}><~\bar{u_{l-1}},~\bar{u_{l}}>が等しくなり、<~\bar{u_{k}},~\bar{u_{k+1}}>より、小さい対が見つかるので、矛盾である。

ゆえに、k=1である。

適当なl(0<l≦a2+1)に対し、<~\bar{u_{1}},~\bar{u_{2}}>~=~~\bar{u_{l}},~\bar{u_{l+1}}>が成り立つ。

u1=u2=1なので、\bar{u_l}=\bar{u_1}=1,~\bar{u_{l+1}}=\bar{u_2}=1である。

これはulもul+1もaで割って1余るということであるため、u_{l-1}~(=u_{l+1}~-~u_l)はaで割り切れるということになる。 □

[定理]
[1]5m±1の形の素数pは、up-1を割り切る。
[2]5m±2の形の素数pは、up+1を割り切る。

フィボナッチ数と黄金比

フィボナッチ数の比の収束値

[定理](ド・モアブル)
{un}:フィボナッチ数列とする。
u_n~=~\frac{1}{\sqrt{5}}~(~\alpha^n~-~\beta^n)
ただし、\alpha~=~\frac{1+\sqrt{5}}{2},~\beta~=~\frac{1-\sqrt{5}}{2}(x2-x-1=0の解)とする。

[証明]フィボナッチ数unを係数とする次のべき級数を考える。

g(x)~=~\sum_{n=0}^{\infty}~u_n~x^n~(=x+x^2+2x^3+3x^4+5x^5+\cdots) ←(*)

このとき、g(x)-xを計算すると次のように展開できる。

g(x)-x
=\sum_{n=2}^{\infty}~u_n~x^n
=\sum_{n=2}^{\infty}~(u_{n-1}~x^n~+~u_{n-2}~x^2) (∵フィボナッチ数列の定義)
=x~\sum_{n=0}^{\infty}~u_n~x^n~+~x^2~\sum_{n=0}^{\infty}~u_n~x^n
=xg(x)~+~x^2~g(x)

g(x)~=~\frac{x}{1-x-x^2}
=\frac{x}{(1-\alpha~x)(1-\beta~x)} (∵α,βの定義)
=\frac{1}{\sqrt{5}(1-\alpha~x)}~-~\frac{1}{\sqrt{5}(1-\beta~x)}
=\frac{1}{\sqrt{5}}(1+\alpha~x~+~\alpha^2~x^2~+~\cdots)~-~\frac{1}{\sqrt{5}}(1+\beta~x~+~\beta^2~x^2~+~\cdots)

よって、g(x)=\frac{1}{\sqrt{5}}((\alpha~-~\beta)x~+~(\alpha^2~-~\beta^2)~x^2~+~\cdots) ←(**)

(*)と(**)の係数を比較すると、題意が成り立つ。 □

[補講]この証明のように、与えられた数列から作られるべき級数は生成関数と呼ばれ、数論でよく使われる。 ◇

[定理](ド・モアブル)
{un}:フィボナッチ数列とする。
\lim_{n~\to~\infty}~\frac{u_{n+1}}{u_n}~=~\frac{1}{2}(\sqrt{5}~+~1)

[証明]

\frac{u_{n+1}}{u_n}
=\frac{\alpha^{n+1}-\beta^{n+1}}{\alpha^{n}-\beta^{n}} (∵u_n~=~\frac{1}{\sqrt{5}}~(~\alpha^n~-~\beta^n)
=\alpha~+~\frac{(\alpha~-~\beta)\beta^2}{\alpha^n~-~\beta^n} (∵分子を分母で割った。\alpha^{n+1}-\beta^{n+1}~=~\alpha^{n+1}~+~\alpha~\beta^n~-~\alpha~\beta^n~-\beta^{n+1}~=~(\alpha^{n+1}~+~\alpha~\beta^n)~+~(\alpha~-~\beta)\beta^n
=\alpha~+~\frac{\alpha~-~\beta}{(\frac{\alpha}{\beta})^n~-~1}
=\alpha~+~\frac{\sqrt{5}}{(\frac{\alpha}{\beta})^n~-~1} (∵α-β=√5)
=\alpha~+~\frac{\sqrt{5}}{(-\alpha^2)^n~-~1} (∵\frac{\alpha}{\beta}~=~\frac{1+\sqrt{5}}{1-\sqrt{5}}=\frac{(1+\sqrt{5})^2}{(1-\sqrt{5})(1+\sqrt{5})}~=~\frac{(1+\sqrt{5})^2}{-4}~=~-(\frac{1+\sqrt{5}}{2})^2=-\alpha^2
=\alpha~+~(-1)^n\frac{\sqrt{5}}{\alpha^{2n}~-~1}
=\alpha (∵n→∞のとき、\alpha^{2n}~=~({\frac{1+\sqrt{5}}{2})^{2n}~\to~\infty) □

参考文献

  • 『なっとくするオイラーとフェルマー』