フィボナッチ数を極める                 戻る

 フィボナッチ数は、およそ800年前に刊行された、「算盤の書」(1202年)の中の有名な
「兎の問題」から生まれた。

 この書は、通称 Fibonacci (filius Bonacci:ボナッチの子 を縮めたもの)といわれるイタリアの
数学者、ピサのレオナルドによるものである。

 兎の問題  1つがいの兎は、1年の間に何つがいの兎になるか?

  但し、1ヶ月経つと1つがいの兎は1つがいの兎を産み、産まれた兎は、2ヶ月目には
 子供を産むものとする。

 この兎の問題を図式化すると次のようになる。(→参考類題:受験の神様

0ヶ月   1ヶ月   2ヶ月  3ヶ月 ・・・    兎のつがいの増え方は、次の規則に従っている。

   n ヶ月後の兎のつがいの数を F(n) とすると、

F(n)={(n−2)ヶ月後のつがい数}+{(n−1)ヶ月後のつがい数
     2ヶ月後に子供を産む数

   =F(n−2)+F(n−1)

 月末の個数だけに注目して、次の数列を得る。

 2,3,5,8,13,21,34,55,89,144,233,377,・・・

従って、兎の問題の答は、377つがいとなる。


フィボナッチ数の定義

 a1=1、a2=1、a=an-1+an-2 (n=3,4,・・・)で定まる数列をフィボナッチ数列

 1 ,1 ,2 ,3 ,5 ,8 ,13 ,21 ,34 ,55 ,89 ,144 ,233 ,377 ,・・・

といい、数列の各項を、フィボナッチ数という。

 このページでは、フィボナッチ数の持つ面白い性質と応用を紹介していきたいと思う。

(次のホームページ(12さんすう34数学5Go!)のフィボナッチ数の項では、フィボナッチ数の性質を、楽しく、具
体的に紹介しているので、大いに参考になります。)


(性質1) 1+a2+・・・+a=an+2−1

    a1=a3−a2,a2=a4−a3,・・・,a=an+2−an+1 の各式を辺々加えればよい。

同様にして、次の性質2,3 も簡単に示すことができる。

(性質2) 1+a3+・・・+a2n-1=a2n

(性質3) 2+a4+・・・+a2n=a2n+1−1

 性質2 の式から性質3 の式を辺々引くことにより、次の大切な性質を得る。

(性質4) a1−a2+a3−a4+・・・+(−1)n+1=(−1)n+1n-1+1

(性質5) n+m=an-1+am+1

  証明は、m に関する数学的帰納法により、簡単に示すことができる。

実際に、m=1 のとき、右辺=an-11+a2=an-1+a=an+1=左辺

 m=2 のとき、右辺=an-12+a3=an-1+2a=an-1+a+a=an+2=左辺

 m=k、k+1(k≧1) のとき、成り立つと仮定する。

  即ち、an+k=an-1+ak+1 、 an+k+1=an-1k+1+ak+2

 このとき、

n-1k+2+ak+3

=an-1(ak+1+ak)+a(ak+2+ak+1

=(an-1+ak+1)+(an-1k+1+ak+2)

=an+k+an+k+1

=an+k+2

 よって、m=k+2 のときも成り立つので、全ての自然数に対して、与式は成り立つ。


(追記) 平成30年10月21日付けでHN「nya」さんより、(性質5)の別証明をいただいた。

(別証) まず次の等式を証明する。

  n-1+am+1n+1+am-1 ・・・(*)

 実際に、

左辺=an-1+a−a+am+1=(an-1+a)a+a(am+1−a

  =右辺 より明らか。

 さて、m=2k または m=2k+1 となるような整数kが存在する。(*)式をk回繰り返し
用いると、

 an-1+am+1

=an+1+am-1  (1回目)

=an+3+am-3  (2回目)

 ・・・・・・・・・・・・・・・・・・・・・

=an+2k−1+am-2k+1  (k回目)

=am-2k+1+an+2k−1  (項を入れ替える)

 m=2k のとき、さらに(*)式をk−1回繰り返し用いて、

m-2k+1+an+2k−1

=an+2m-2k+1+an+2k−1m-2  (1回目)

=an+4m-2k+1+an+2k−1m-4  (2回目)

  ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

=an+2k-2m-2k+1+an+2k−1m-2k+2  (k−1回目)

=an+m-21+an+m−12

=an+m-2+an+m−1

=an+m

 m=2k+1 のとき、さらに(*)式をk回繰り返し用いて、

m-2k+1+an+2k−1

=an+2m-2k+1+an+2k−1m-2  (1回目)

=an+4m-2k+1+an+2k−1m-4  (2回目)

  ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

=an+2km-2k+1+an+2k−1m-2k  (k回目)

=an+m-12+an+m−21

=an+m-1+an+m−2

=an+m

 したがって、所要の等式を得る。


(コメント) nya さん、別証明、ありがとうございました。


 性質5で、n=m のときを考えることにより、次の性質6,7 を得る。

(性質6) 2nは、aで割り切れる

(性質7) a2n=an+12−an-12

次の性質は、ビネ(Binet)の公式(1843)として有名である。

 (結果そのものは、その1世紀以上前にオイラー、ダニエル・ベルヌーイ、ド・モアブルなどには知られていた
  らしい!


(性質8) 1=1、a2=1、a=an−1+an−2 (n=3,4,・・・)で定まる数列の
     一般項は、

   

 但し、    とする。

(証明) α、βを用いて、an+2−αan+1=β(an+1−αa)

  an+2−βan+1=α(an+1−βa) と変形されるので、

  an+1−αa=(a2−αa1n-1=(1−α)βn-1=β

  an+1−βa=(a2−βa1n-1=(1−β)αn-1=α

 この連立方程式を解いて、ビネの公式を得る。 (証終)


 始めに「フィボナッチ数列ありき」でこのビネの公式を見ると、「a が自然数」であることは
疑うよしもない。しかし、始めに、このビネの公式で定まる数列が与えられるとき、各項は自
然数になると聞いて、「ホント?」と思う人は少なからず存在するだろう。
                 (→ 参考 : 「025 平成21年度後期 横浜国立大学 工学部」)

 証明はいくつか考えられる。

(証明その1)・・・数学的帰納法によるもの

 n=1 のとき、 a1=(α−β)//=1 で自然数。

   よって、n=1 のとき成り立つ。

 n≦k(k≧1)で成り立つと仮定する。すなわち、k 以下の自然数 m に対して、

  a=(α−β)/ は自然数

 n=k+1 のとき、 αk+1−βk+1=(α−β)(α+β)−αβ(αk-1−βk-1) より、

 (αk+1−βk+1)/=(α+β)・(α−β)/−αβ・(αk-1−βk-1)/

  ここで、 α+β=1 、 αβ=−1 と帰納法の仮定より、

  ak+1=(αk+1−βk+1)/ は自然数

 よって、n=k+1 のときも成り立つ。

 以上から、数学的帰納法により、

 すべての自然数 n に対して、 a=(α−β)/ は自然数である。 (証終)

(証明その2)

 α+β=1 、 αβ=−1 より、α、βは、2次方程式 x2−x−1=0 の解である。

このとき、 x2=x+1 より、 x=Mx+N (M、N は自然数)とおける。

 よって、 α=Mα+N 、 β=Mβ+N より、

 a=M(α−β)/=M/=M となり、a は自然数である。 (証終)


(コメント) 当HPがいつもお世話になっているS(H)さんによれば、数学的帰納法によるも
      の以外に、漸化式を変形したり、母関数を使って証明することが可能であるとの
      ことである。


 フィボナッチ数は、その定義から明らかなように、単調に増加する数である。果たして、
フィボナッチ数は、どのような速さで増加するのであろうか?この問いに対して、次の定
理がその答となる。

定理    に最も近い整数は、フィボナッチ数 aである。

 証明は、性質 8 のビネの公式より明らかである。

 この定理はまた、フィボナッチ数を求める新しい方法を我々に示唆している。


対数でフィボナッチ数を求める

 対数表では、有効桁数があまりに小さいので、ここでは、関数電卓(CASIO fx-7200G)を
用いて、求めてみよう。

例えば、n=14 のとき、  の常用対数を求めると、2.576341398 となるので、

その真数は、377.0000415である。よって、この数に一番近い整数は、377となる。
(この数は、先の兎の問題の答の数と一致する。)

 関数電卓もわずか10桁程度の有効数字にしか対応できないので、おのずと限界がある。
n の値が大きくなると、先頭の数桁程度しかその信頼度はない。

 表計算ソフト Microsoft Excel を用いると、フィボナッチ数は、容易に求められる。

(セルA1に1、セルA2に1、セルA3に=A1+A2を、それぞれ入力し、セルA3の右下隅にカー
ソルをあわせ、下方にドラッグすればよい。)

 ただ、この方法にも限界があって、n=54のときの 86,267,571,272 が、正しく
求められる最大のフィボナッチ数である。いろいろ工夫すれば、この記録はもっとのばせる
と思う。

 関数電卓(CASIO fx-7200G)で求められる最大のフィボナッチ数はいくつであろうか?
計算の結果、それは、n=40 のときで、その値は、102,334,155 であった。

 性質5や性質7などを用いると、人力でもっと大きい n に対するフィボナッチ数が求めら
れると思う。

(性質9) 2つのフィボナッチ数の最大公約数は、フィボナッチ数である

 実際に、a18=2584 と a12=144 の最大公約数は、a6=8である。

 この性質9を、さらに詳しく言及したのが次の定理である。

定理  (a,a)=a(m,n)  但し、(X,Y)は、X と Y の最大公約数を表す。

 この定理を証明するために、次の性質が用いられる。

(性質10) 隣り合うフィボナッチ数は、互いに素である

 証明は容易である。

(a,an+1)=d>1とすると、 an+1−a=an-1 は d で割り切れる。
このことから、帰納的に、a1=1 が d で割り切れることになり、矛盾。

(別証) 漸化式の形から明らかに、(an+2,an+1)=(an+1,a
    したがって、(an+1,a)=(a,an-1)=・・・=(a2,a1)=1
    よって、題意は示された。

 定理を一般的に証明することは難しいので、専門書に委ねる。ここでは、先ほどの例を
用いて、証明をなぞってみたい。

 ユークリッドの互除法により、18=1×12+6、12=2×6 だから、18と12の最大公
約数は、6である。

 このとき、(a18,a12

=(a1×12+6,a12

=(a1×12-16+a1×126+1,a12) (←性質5より)

=(a116+a127,a12

=(a116,a12) (←性質Bより)

=(a6,a12) (←性質10と性質Dより)

=(a6,a6+6

=(a6,a56+a67) (←性質5より)

=(a6,(a5+a7)a6

=(1,a5+a7)a6 (←性質Cより)

=a6


上記の計算では、最大公約数に関する次の性質A、B、C、Dが用いられた。

(性質A) (a,b)は(ac,b)の約数

 証明は、明らかであろう。

(性質B) c が b で割り切れるとき、(a+c,b)=(a,b)

(証明)  c=bc’、a=bq+r より、a+c=b(q+c’)+r となるので、ユークリッドの互除
     法の原理から明らかである。

(性質C) (ac,bc)=(a,b)c

 証明は、明らかであろう。

(性質D) (b,c)=1 のとき、(ac,b)=(a,b)

(証明)  性質Aより、(ac,b)は(ac,ab)の約数である。

  性質Cより、(ac,ab)=(c,b)a=a なので、(ac,b)はaの約数となる。

  (ac,b)はbの約数でもあるので、(ac,b)は(a,b)の約数である。

   性質Aより、(a,b)は(ac,b)の約数なので、(ac,b)=(a,b)となる。  (証終)


 上の定理から、次の事実が成り立つ。これも、フィボナッチ数の面白い特性であろう。

系  m が n で割り切れるとき、a は aで割り切れる
  この逆もまた成り立つ


 証明は、定理から明らかであろう。

例  54は18で割り切れる。このとき、

 a18=2584
 a54=86267571272 =33385283×2584=33385283×a18

 確かに、a54はa18で割り切れる。

 この系により、性質6は、明らかに成り立つ。

(参考文献:ヴォロビェフ 著 筒井孝胤 訳 フィボナッチ数(東京図書))


(追記)フィボナッチ数列は、いろいろな問題に現れる。例えば、次のような問題である。

  n段の階段がある。1段ずつでも2段ずつでも、また1段ずつと2段ずつをとりまぜ
て登ってもよいとして、何通りの登り方があるか。


 階段が1段のとき、登り方は、1通り

 階段が2段のとき、登り方は、1段ずつと一気に2段の2通り

 階段が3段のとき、登り方は、1段ずつ・1段と2段・2段と1段の3通り

 階段が4段のとき、登り方は、1段ずつ・1段ずつで最後に2段・1段と2段と1段・最初に

  2段で残り1段ずつ・2段が2回の5通り

 ・・・・・・・・・・・

 このように実験してみると、登り方の数列は、1,2,3,5,・・・ となり、なんとなくフィボ
ナッチ数が見えてくる。

 実際に、n段の階段のときの登り方の総数を、b (=an+1)とすると、漸化式

  b1 =1、b2 =2、 b=bn−1+bn−2 (n=3,4,・・・)

が成り立つ。漸化式の作り方は、

 最初に1段登ったとき、残りのn−1段の登り方 bn−1 通り
 最初に2段登ったとき、残りのn−2段の登り方 bn−2 通り

から和の法則を用いて明らかでしょう。

 建物の中の階段は、9、11、13段などが多い。
                       (因みに、我が家の階段は、13段です...f(^_^) )
階段を誰かと一緒に登る時の話題の一つとしていかがでしょうか?

階段の段数 11 13
登り方の総数 55 144 377
 (覚えやすい数字ですね! )


(追記) 令和3年8月7日付け

 上記の階段の登り方で、フィボナッチ数が現れることを見た。最近たまたまパズルを考察
していたら、やはり、フィボナッチ数が現れたのだが、よくよく考えてみたら、階段の場合の
文言の言い換えに過ぎないことに気づき、がっかりした覚えがある。

 1×n (nは自然数) のマス目がある。このマス目を、1×1、1×2の長方形で埋め
尽くす方法は何通りあるか。


 埋め尽くす方法の数を F と置く。

例 明らかに、 F1=1 である。

 F2=2 である。実際に、1×1の長方形を2個 または、1×2の長方形1個の2通りある。

 F3=3 である。

  実際に、1×1の長方形を3個 または、1×1の長方形1個と1×2の長方形1個の順列
 も考えて、合計3通りある。

 F4=5 である。

  実際に、1×1の長方形を「1」、1×2の長方形を「2」で表すことにすると、その場合は、
   1111、211、121、112、22 の5通りある。

 一般に、1×(n+2)のマス目に対して、

  最初に、1×1の長方形を埋める場合(残りは、1×(n+1)のマス目)

  最初に、1×2の長方形を埋める場合(残りは、1×nのマス目)

 の何れかがあり得るので、漸化式 Fn+2=Fn+1+F が成り立つ。

  これは、フィボナッチ数の漸化式そのものである。

 従って、後は機械的に、

  F5=8 、F6=13 、F7=21 、F8=34 、F9=55 、F10=89 、・・・

が得られる。

 読者のために、パズル問題を1題残しておこう。

問題  1×10のマス目がある。

 
 
                   
 
 このマス目を、 1×1の長方形 1×2の長方形
 
 
 
   

をいくつか用いて埋め尽くす。埋め尽くし方は全部で何通りあるか?


(解) F10=89(通り) である。  (終)


(追記) 次の性質が成り立つ。

(性質11) 12+a22+・・・+a2=an+1   (Sum of squares)

 証明は、n に関する数学的帰納法により、簡単に示すことができる。

実際に、n = 1 のとき、右辺=a12=a12=左辺 (← a1=a2

 n=k (k≧1)のとき、成り立つと仮定する。即ち、a12+a22+・・・+a2=ak+1

 このとき、

12+a22+・・・+a2+ak+12

=ak+1+ak+12=ak+1(a+ak+1)=ak+1k+2

 よって、n=k+1 のときも成り立つので、全ての自然数に対して、与式は成り立つ。


 さて、フィボナッチ数列

 1 ,1 ,2 ,3 ,5 ,8 ,13 ,21 ,34 ,55 ,89 ,144 ,233 ,377 ,・・・

について、当HPの掲示板「出会いの泉」に、平成21年5月17日付けで、HN「tetsuya」
さんが次のような書き込みを残された。

 フィボナッチ数列の1つおきの項

 1 , ,2 , ,5 , ,13 ,21 ,34 ,55 ,89 ,144 ,233 ,377 ,・・・

について、例えば、( 1 ,3 ,8 )や( 21 ,55 ,144 ) などについて、

  相異なる2数を掛けて、1 を足す

という操作をすると平方数になる。

 実際に、 1×3+1=4=22 、 3×8+1=25=52 、 1×8+1=9=32

  21×55+1=1156=342 、 55×144+1=7921=892

  21×144+1=3025=552

しかも、すべてフィボナッチ数列に現われる数の平方になっている。

(コメント) とても美しく面白い性質ですね。tetsuya様に感謝します。

 tetsuya様の書き込みによれば、一般に、「相異なる2数を掛けて、1 を足す」という操作

を施して平方数になる n 個の数の組は、Diophantine n-tuple と言われるという。

 上記の計算から、( 1 ,3 ,8 )や( 21 ,55 ,144 ) などは、Diophantine 3-tuple
である。

 Andrej Dujella :「The problem of Diophantus and Davenport」 によれば、

ギリシャの数学者 Diophantus of Alexandria は、Diophantine 4-tuple として

 ( 1/16 、33/16 、17/4 、105/16 )

を得ていたという。 フェルマーは、4つの数がすべて自然数という条件で、

 ( 1 ,3 ,8 ,120 )

というDiophantine 4-tuple を見出した。

 ところで、Baker と Davenportの結果(1969)によれば、

 ( 1 ,3 ,8 ,d )が、Diophantine 4-tuple である自然数 d の値は、d=120

しかないようだ。 さらに、Euler は、

  a 、 b 、 a+b+2r 、 4r(r+a)(r+b)   ただし、 ab+1=r2

という解を与えている。 ( 1 ,3 ,8 ,120 )は、 a=1、b=3、r=2 の場合である。

 上記の計算で、フィボナッチ数から得られる Diophantine 3-tuple において、「相異な
る2数を掛けて、1 を足す」という操作を施すと、フィボナッチ数の平方になるという現象に
遭遇したが、このことを整理すると、次の(性質12)が得られる。


(性質12) n+12−an+2=(−1)

 証明は、n に関する数学的帰納法により、簡単に示すことができる。

実際に、n = 1 のとき、左辺=a22−a13=1−2=−1=左辺

 n=k (k≧1)のとき、成り立つと仮定する。即ち、ak+12−ak+2=(−1)

 このとき、

k+22−ak+1k+3

=ak+22−ak+1(ak+1+ak+2)

=(ak+2−ak+1)ak+2−ak+12=ak+2−ak+12=−(−1)=(−1)k+1

 よって、n=k+1 のときも成り立つので、全ての自然数に対して、与式は成り立つ。


(追記) 令和3年8月16日付け

 (性質12) n+12−an+2=(−1) は、非常に有名な恒等式で、カッシーニの公式
と言われる。

 この公式を用いると、 (性質10) 隣り合うフィボナッチ数は、互いに素である の別
証が得られる。

(別証) a、an+1 に1以外の公約数dがあるとすると、

 an+12−an+2=(−1) から、(−1)がdで割り切れることになるが、これは矛盾。

 よって、隣り合うフィボナッチ数は、互いに素である。  (別証終)


 カッシーニの公式絡みで、次の文献に興味を引かれた。

(参考) 城野真民・北山秀隆 著 「フィボナッチ数を背景とする教材の考察」(和歌山大学)


 (性質12)の証明では、数学的帰納法を用いたが、もちろん直接的に示す方法もある。

 (性質8)で示したビネの公式を用いればよい。

 a1=1、a2=1、a=an-1+an-2 (n=3,4,・・・)で定まる数列の一般項は       
     但し、  

で与えられるので、

 

 ここで、 α+β=1 、αβ=−1 なので、 (α−β)2=(α+β)2−4αβ=5

 よって、 an+12−an+2=(1/5)(−1)・5=(−1) が成り立つ。


 さらに、次のような証明法があることを、zk43さんより、ご教示いただいた。
                                  (平成21年5月19日付け)
 漸化式 an+2=an+1+a より、

  an+1=a(an+2−a)=an+2−a2

 同様に、漸化式 an+1=a+an-1 より、

  an+1=(an+1−an-1)an+1=an+12−an-1n+1

よって、 an+2−a2=an+12−an-1n+1 より、 an+12−an+2=−(a2−an-1n+1

したがって、 an+12−an+2=(−1)n-1(a22−a13)=(−1)n-1(12−1・2)=(−1)

(コメント) う〜む、なるほど!上手い証明ですね。

 zk43さんは、さらに、行列で考えた方が、構造が分かりやすい感じがするとのこと。

すなわち、
         、  

とおくと、 A=BAn-1 が成り立つので、 A=Bn-11

 よって、 det(A)=det(B)n-1・det(A1)=(−1)n-1(1・2−12)=(−1)n-1 より、

   an+2−an+12=(−1)n-1

 すなわち、 an+12−an+2=(−1) が成り立つ。


(コメント) 計算がスッキリしました...! zk43さんに感謝します。


(追記) 平成21年3月27日付け

 数列 { a } がフィボナッチ数列であるとき、(性質12)が成り立つわけであるが、逆に、
(性質12)がなりたつような数列 { a } はフィボナッチ数列であることを問う入試問題が
あることを、当HPがいつもお世話になっているS(H)さんより伺った。


横浜国立大学 後期工学部(2001)

 数列 { a } は、 a1=1 、a2=1 、an+2−an+12=(−1)n+1 (n=1、2、3、・・・)
により定まる。次の問いに答えよ。

 (1) an+2=an+1+a (n=1,2,3,・・・) が成り立つことを証明せよ。
 (2) m を自然数とするとき、a6m は8の倍数であることを示せ。


(解) (1) a13−a22=(−1)2 より、a3−1=1 なので、a3=2

 n=1 のとき、 左辺=a3=2 、右辺=a2+a1=2 なので、

 an+2=an+1+a は、n=1 のとき成り立つ。

 n≦k (k≧1) のとき成り立つと仮定する。即ち、

 a3=a2+a1 、a4=a3+a2 、・・・ 、ak+2=ak+1+a

 a1=1 、a2=1 より、 a3>0 、a4>0 、・・・ 、ak+2>0 である。

 ここで、与えられた漸化式より、

 ak+2−ak+12=(−1)k+1

 ak+1k+3−ak+22=(−1)k+2=−(−1)k+1

2式を辺々加えて、 ak+2−ak+12+ak+1k+3−ak+22=0

 このとき、 (a−ak+2)ak+2−ak+12+ak+1k+3=0 において、

  a−ak+2=−ak+1 より、 −ak+1k+2−ak+12+ak+1k+3=0

 よって、 ak+1(−ak+2−ak+1+ak+3)=0 において、ak+1>0 より、

  −ak+2−ak+1+ak+3=0 すなわち、 ak+3=ak+2+ak+1 が成り立つ。

 よって、n=k+1 のときも成り立つので、全ての自然数に対して、与式は成り立つ。

(2) a6=a5+a4=2a4+a3=2(a3+a2)+a3=3a3+2a2=3・2+2・1=8 で、

(a6m,a6)=a(6m,6)=a6=8 より、自然数 m に対して、 a6m は8の倍数である。(終)


(コメント) (1)がこの問題の眼目で、(2)はサービス問題ですね!


 FNさんからのコメントです。(平成23年11月19日付け)

 上記の(2)の解答で、(性質9)の下の定理を使っています。

(2)は、「amnはaの倍数である。・・・(*)」が、n=6で成り立つことの証明を要求するもので、

(*)よりかなり強い定理を引用するのは(入試問題の解答としては)駄目でしょう。

 具体的に調べるのがいいと思います。

 aを8で割った余りをbとすると、m=1、2、・・・、12 のときのbは次のようになる。
10 11 12

 m=13以降は、これを繰り返すから、mが6の倍数のとき、b=0

 よって、a6mは8の倍数である。

 表から逆も言えてるので、「aが8の倍数 ⇔ nが6の倍数」が成り立ちます。

 同様にして、次のような関係も成り立ちます。

  「aが2の倍数 ⇔ nが3の倍数」

  「aが3の倍数 ⇔ nが4の倍数」

  「aが5の倍数 ⇔ nが5の倍数」

 大学入試に出題するのに、どのあたりが適当かということでしょう。


(コメント) FNさん、ありがとうござます。


 FNさんからの続報です。(平成23年11月23日付け)

 上記を、次の形に一般化した場合の証明は難しいだろうと思っていたのですが、それほど
でもありませんでした。

  が a の倍数 ⇔ n が m の倍数

が a の倍数 ⇔ n が m の倍数

 合同式を使って書けば、 ≡0 (mod a) ⇔ n≡0 (mod m) です。これを

証明するのにキーになるのは、次の性質です。

 ≡0 (mod a) ⇔ an+m≡0 (mod a)

例 フィボナッチ数列:1 ,1 ,2 ,3 ,5 ,8 ,13 ,21 ,34 ,55 ,89 ,144,・・・ に
  おいて、

 a6=8≡0 (mod a3=2) であるのに対して、a9=34≡0 (mod a3=2)

 a8=21≡0 (mod a4=3) であるのに対して、a12=144≡0 (mod a4=3)

(証明) (性質5)より、n+m=an-1+am+1 であるから、

  an+m=am+1 (mod a) ・・・ (*)

よって、 a≡0 (mod a) ⇒ an+m≡0 (mod a)

 (性質10)より、a と am+1 は互いに素であるから、am+1 は、mod a で逆元を持つ。

 即ち、am+1・k≡1 (mod a) となる k が存在する。
    (am+1・k+a・l=1 を満たす整数 k、l が存在するということ)

 (*)の両辺に k をかけて、 an+m・k≡a (mod a

 よって、 an+m≡0 (mod a) ⇒ a≡0 (mod a

 したがって、 a≡0 (mod a) ⇔ an+m≡0 (mod a)  (証終)


 これを使って、 「 a が a の倍数 ⇔ n が m の倍数」、即ち、

   ≡0 (mod a) ⇔ n≡0 (mod m)

を証明します。

(証明) n を m で割ったときの商を q、余りを r とする。 n=mq+r (0≦r<m)

  a≡0 (mod a) ⇔ an-m≡0 (mod a) を繰り返し使って、

  a≡0 (mod a) ⇔ an-m≡0 (mod a) ⇔ an-2m≡0 (mod a)

  ・・・・ ⇔ an-qm≡0 (mod a) ⇔ a≡0 (mod a)

  0≦r<m より、 a<a なので、

   a≡0 (mod a) ⇔ a=0 ⇔ r=0 ⇔ n≡0 (mod m)

 以上より、 a≡0 (mod a) ⇔ n≡0 (mod m)  (証終)

 これは、(性質9)の下にある定理の系ですが、系から定理も容易に出ます。

これを書き直せば、  が a の約数 ⇔ d が n の約数

 これから、  が、a、a の公約数 ⇔ d が m、n の公約数

         が、a、a の最大公約数 ⇔ d が m、n の最大公約数

これが定理です。


(性質13) (a123+(a233+・・・+(an+13=(an+1n+2)2/4

 この性質は、大塚秀幸先生(元文教大付属高)が見出されたものである。

 フィボナッチ数の定義 =an-1+an-2 (n=2,3,・・・) を用いて容易に示すこと
が出来る。ただし、 a0=0 、a1=1 とする。

(証明) 任意の k に対して、

  (ak+1k+2)2−(ak-1k+1)2

 =(ak+1)2(ak+22−ak-12

 =(ak+1)2(ak+2+ak-1)(ak+2−ak-1

 =(ak+1)2(ak+1+a+ak-1)(ak+1+a−ak-1

 =(ak+1)2(ak+1+ak+1)(a+ak-1+a−ak-1

 =(ak+1)2(2ak+1)(2a

 =4(ak+1)3

 すなわち、 4(ak+1)3=(ak+1k+2)2−(ak-1k+1)2

 上式に、k=1、2、・・・、n を代入して、辺々加えると、

   4{(a123+(a233+・・・+(an+13}=(an+1n+2)2−(a012)2

 ここで、 a0=0 、a1=1 から、 a2=1 なので、 a012=0

 よって、 4{(a123+(a233+・・・+(an+13}=(an+1n+2)2 より、

     (a123+(a233+・・・+(an+13=(an+1n+2)2/4  (証終)

(コメント) この(性質13)を用いると、

    a0=0 、a1=1 から、

   a2=1 、a3=2 、a4=3 、a5=5 、a6=8 、a7=13 、・・・

 なので、 

    (a123+(a233+(a343+(a453+(a563=(a567)2/4

 すなわち、 3+23+63+153+403=2602  となる。

 何か、パズルに使えそうですね!


 当HPがいつもお世話になっているHN「攻略法」さんから新しい性質をご教示いただいた。
                                       (平成23年8月9日付け)

(性質14) n-1n+2=an+12−a2

(証明) an+12−a2=(an+1−a)(an+1+a)=an-1n+2  (証終)

(性質15) 2n+1=an+12+a2

(証明) 数学的帰納法による。

 n=1 のとき、 a3=a1+a2=1+1=2 、 a22+a12=1+1=2

  よって、 a3=a22+a12 なので、n=1のとき、命題は成り立つ。

 n=2 のとき、 a5=a3+a4=2+3=5 、 a32+a22=4+1=5

  よって、 a5=a32+a22 なので、n=2のとき、命題は成り立つ。

 n=k、k+1(k≧1)のとき、命題が成り立つと仮定する。

  すなわち、 a2k+1=ak+12+a2 、a2k+3=ak+22+ak+12

 このとき、

k+32+ak+22

=ak+32+a2k+3−ak+12

=a2k+3+(ak+3−ak+1)(ak+3+ak+1

=a2k+3+ak+2(ak+3+ak+1

=a2k+3+ak+2k+3+ak+2k+1

ここで、(性質5) n+m=an-1+am+1 より、

 ak+2k+3+ak+2k+1=ak+1k+2+ak+2k+3=a2k+4

なので、 ak+32+ak+22=a2k+3+a2k+4=a2k+5

 これより、命題は、n=k+2のときも成り立つ。

したがって、すべての自然数 n に対して、命題は成り立つ。  (証終)


 FNさんからのコメントです。(平成23年11月19日付け)

 (性質15) 2n+1=an+12+a2 は、

(性質5)  n+m=an-1+am+1 のnをn+1に、mをnにした式です。

(性質7) a2n=an+12−an-12 と並ぶ式です。

(コメント) 確かに並べると、関連性が浮き彫りになりますね!FNさんに感謝します。


 ところで、フィボナッチ数列1=1、a2=1、an+2=a+an+1 (n=1,2,・・・)で、

  a=an-1n+2 、b=2an+1 、c=a2n+1 とおけば、 2+b2=c2 が成り立つ。

(→ 参考:「ピタゴラス数の発見」)

(証明)  (性質14) n-1n+2=an+12−a2

   (性質15) 2n+1=an+12+a2

より、 a=an-1n+2=an+12−a2 、 a2n+1=an+12+a2 なので、

 an+1=s 、a=t とすると、a=s2−t2 、 b=2st 、 c=s2+t2 なので、

 a2+b2=c2 が成り立つ。  (証終)


 攻略法さんから新しい性質をご教示いただいた。(平成23年8月16日付け)

(性質16) n+2+an-2=3a

(証明) an+2+an-2=(an+1+a)+(a−an-1)=an+1−an-1+2a=3a  (証終)

(性質17) n+1−an-1=a2

(証明) an+1−an-1=a(an+1−an-1)=a2  (証終)

(性質18) n+13+a3−an-13=a3n

(証明)

3n=an+2n

  =an-12n+a2n+1  (← (性質5) n+m=an-1+am+1

  =an-1(an+12−an-12)+a(an+12+a2
   (← (性質7) a2n=an+12−an-12 、(性質15) 2n+1=an+12+a2

  =an+12(a+an-1)+a3−an-13

  =an+13+a3−an-13  (証終)

(性質19) 12+a23+・・・+a2n-12n=a2n2

(証明) n=1 のとき、 左辺=a12=1・1=1 、右辺=a22=12=1 なので、

  左辺=右辺 となり、n=1 のとき成り立つ。

n=k(k≧1)のとき成り立つと仮定する。すなわち、a12+a23+・・・+a2k-12k=a2k2

 n=k+1 のとき、帰納法の仮定より、

 a12+a23+・・・+a2k+12k+2

=a2k2+a2k2k+1+a2k+12k+2

=a2k(a2k+a2k+1)+a2k+12k+2

=a2k2k+2+a2k+12k+2

=(a2k+a2k+1)a2k+2

=a2k+22

 よって、n=k+1 のときも成り立つ。

 したがって、すべての自然数 n に対して成り立つ。  (証終)


(性質20) 12+a23+・・・+a2n2n+1=a2n+12−1

(証明) n=1 のとき、左辺=a12+a23=1・1+1・2=3、右辺=a32−1=22−1=3

 なので、左辺=右辺 となり、n=1 のとき成り立つ。

 n=k(k≧1)のとき成り立つと仮定する。すなわち、

  a12+a23+・・・+a2k2k+1=a2k+12−1

 n=k+1 のとき、帰納法の仮定より、

12+a23+・・・+a2k+22k+3

=a2k+12−1+a2k+12k+2+a2k+22k+3

=a2k+1(a2k+1+a2k+2)+a2k+22k+3−1

=a2k+12k+3+a2k+22k+3−1

=(a2k+1+a2k+2)a2k+3−1

=a2k+32−1

 よって、n=k+1 のときも成り立つ。

 したがって、すべての自然数 n に対して成り立つ。  (証終)


 攻略法さんから新しい性質をご教示いただいた。(平成23年8月21日付け)

 性質5などを用いると、人力でもっと大きいnに対するフィボナッチ数が求められる。

 ここで、(性質15) 2n+1=an+12+a2 ←式1 とする。

(性質21) 2n=a(2an-1+a)=a(2an+1−a

(証明) (性質5) n+m=an-1+am+1

 より、 a2n=an-1+an+1=a(an-1+an+1)=a(2an-1+a) なので、

 a2n+2=an+1(2a+an+1) ←式2

同様にして、

 a2n=an-1+an+1=a(an-1+an+1)=a(2an+1−a) ←式3  (証終)


 例 たとえば、a40 は次のようにして求められる。

  40を2で割って、商20、余り0となる。
  式3より、a40=a20(2a21−a20)  実際の値 102334155
  式1より、a41=a212+a202      実際の値 165580141

  先の商20を2で割って、商10、余り0
  式3より、a20=a10(2a11−a10)  実際の値 6765
  式1より、a21=a112+a102      実際の値 10946

  先の商10を2で割って、商5、余り0
  式3より、a10=a5(2a6−a5)    実際の値 55
  式1より、a11=a62+a52       実際の値 89

  先の商5を2で割って、商2、余り1
  式1より、a5=a32+a22        実際の値 5
  式2より、a6=a3(2a2+a3)     実際の値 8

  先の商2を2で割って、商1、余り0
  式3より、a2=a1(2a2−a1)     実際の値 1
  式1より、a3=a22+a12        実際の値 2

  先の商1を2で割って、商0、余り1
  式1より、a1=a12+a02        実際の値 1
  式2より、a2=a1(2a0+a1)     実際の値 1

のように計算手順を組み立てると、

  商を 「漸化式のn」 、余りを 「式の選択」

に対応させて、手順を遡ると、 a0=0 、a1=1 から算出できる。


<計算手順> a を求める場合、m を2進法展開する。

 a0=0 、a1=1 として、最上位から順に

   ビットが「1」なら、式1と式2   ビットが「0」なら、式3と式1

を計算していく。


 当HP読者のK.S.さんより、フィボナッチ数列の新たな視点をご教示頂いた。
                                      (平成23年10月9日付け)

(性質22) フィボナッチ数列:

 1 ,1 ,2 ,3 ,5 ,8 ,13 ,21 ,34 ,55 ,89 ,144 ,233 ,377 ,・・・

において、

 3番目ごとに、2の倍数
 4番目ごとに、3の倍数
 5番目ごとに、5の倍数
 8番目ごとに、7の倍数
10番目ごとに、11の倍数

が現れる。


 FNさんからのコメントです。(平成23年11月15日付け)

 (性質22)について、ちょっとわかりにくい表現ですが、「3番目、6番目、9番目、・・・ は、2
の倍数である」等々の意味でしょう。次の性質の系になります。

 mn は、a の倍数である。(または、amn は、a および a の倍数である)

 これは、(性質6)の一般化です。証明は、(性質5)を使って数学的帰納法でできます。これ
はまた、(性質9)の下の定理の系の前半部分でもあります。


 当HP読者のK.S.さんより、フィボナッチ数列の新たな視点をご教示頂いた。
                                     (平成23年11月11日付け)

(性質23) 全ての自然数は、異なるいくつかのフィボナッチ数の和として表すことが
      できる。


 一見すると「本当?」と思いたくなるような事実に対しても、数学的帰納法は強力な武器と
なる。

(証明) n=1 のときは、明らか。

 n=2 のとき、 2=1+1 なので、 n=2 のときも成り立つ。

 n=3 のとき、 3=2+1 なので、 n=3 のときも成り立つ。

 n=4 のとき、 4=3+1=2+1+1 なので、 n=4 のときも成り立つ。

 今、任意の自然数を N とし、N未満の自然数については、異なるいくつかのフィボナッチ

数の和として表すことができるものと仮定する。ここで、Nを超えない最大のフィボナッチ数

を a とおく。このとき、 N<an+1 が成り立つ。

 an+1=a+an-1 なので、 0≦N−a<an-1

 an-1<a≦N より、帰納法の仮定から、N−a は異なるいくつかのフィボナッチ数の和

として表せる。すなわち、Nは、異なるいくつかのフィボナッチ数の和として表せる。

 以上から、

  全ての自然数は、異なるいくつかのフィボナッチ数の和として表すことができる。(証終)


 攻略法さんが(性質23)に注目され、1から100までのうち個数が最多と最少のものを調査
されました。(平成23年11月14日付け)

 「連続するフィボナッチ数の和」も多々あるとのことです。

(フィボナッチ数)
  1 ,1 ,2 ,3 ,5 ,8 ,13 ,21 ,34 ,55 ,89 ,144,233 ,377 ,・・・
1=1 1+1=2←※
2=2
1+2=3←※
3=3
1+1+2=4←※
1+3=4
1+1+3=5
2+3=5←※
5=5
1+2+3=6←※
1+5=6
1+1+2+3=7←※
2+5=7
1+2+5=8
3+5=8←※
8=8
1+1+2+5=9
1+8=9
1+1+3+5=10
2+3+5=10←※
2+8=10
1+2+3+5=11←※
3+8=11
1+1+2+3+5=12←※
1+3+8=12
1+1+3+8=13
5+8=13←※
13=13
1+2+3+8=14
1+13=14
1+1+2+3+8=15
2+13=15
1+2+5+8=16
3+5+8=16←※
3+13=16
1+1+2+5+8=17
1+3+13=17
1+1+3+5+8=18
2+3+5+8=18←※
5+13=18
1+2+3+5+8=19←※
1+5+13=19
1+1+2+3+5+8=20←※
2+5+13=20
1+2+5+13=21
8+13=21←※
21=21
1+1+2+5+13=22
1+21=22
1+1+3+5+13=23
2+21=23
1+2+3+5+13=24
3+21=24
1+1+2+3+5+13=25
1+3+21=25
1+1+3+8+13=26
5+8+13=26←※
5+21=26
1+2+3+8+13=27
1+5+21=27
1+1+2+3+8+13=28
2+5+21=28
1+2+5+8+13=29
3+5+8+13=29←※
8+21=29
1+1+2+5+8+13=30
1+8+21=30
1+1+3+5+8+13=31
2+3+5+8+13=31←※
2+8+21=31
1+2+3+5+8+13=32
1+2+3+5+8+13=32←※
3+8+21=32
1+1+2+3+5+8+13=33
1+1+2+3+5+8+13=33←※
1+3+8+21=33
1+1+3+8+21=34
13+21=34←※
34=34
1+2+3+8+21=35
1+34=35
1+1+2+3+8+21=36
2+34=36
1+2+5+8+21=37
3+34=37
1+1+2+5+8+21=38
1+3+34=38
1+1+3+5+8+21=39
5+34=39
1+2+3+5+8+21=40
1+5+34=40
1+1+2+3+5+8+21=41
2+5+34=41
1+2+5+13+21=42
8+13+21=42←※
8+34=42
1+1+2+5+13+21=43
1+8+34=43
1+1+3+5+13+21=44
2+8+34=44
1+2+3+5+13+21=45
3+8+34=45
1+1+2+3+5+13+21=46
1+3+8+34=46
1+1+3+8+13+21=47
5+8+13+21=47←※
13+34=47
1+2+3+8+13+21=48
1+13+34=48
1+1+2+3+8+13+21=49
2+13+34=49
1+2+5+8+13+21=50
3+5+8+13+21=50←※
3+13+34=50
1+1+2+5+8+13+21=51
1+3+13+34=51
1+1+3+5+8+13+21=52
2+3+5+8+13+21=52←※
5+13+34=52
1+2+3+5+8+13+21=53
1+2+3+5+8+13+21=53←※
1+5+13+34=53
1+1+2+3+5+8+13+21=54
1+1+2+3+5+8+13+21=54←※
2+5+13+34=54
1+2+5+13+34=55
21+34=55←※
55=55
1+1+2+5+13+34=56
1+55=56
1+1+3+5+13+34=57
2+55=57
1+2+3+5+13+34=58
3+55=58
1+1+2+3+5+13+34=59
1+3+55=59
1+1+3+8+13+34=60
5+55=60
1+2+3+8+13+34=61
1+5+55=61
1+1+2+3+8+13+34=62
2+5+55=62
1+2+5+8+13+34=63
8+55=63
1+1+2+5+8+13+34=64
1+8+55=64
1+1+3+5+8+13+34=65
2+8+55=65
1+2+3+5+8+13+34=66
3+8+55=66
1+1+2+3+5+8+13+34=67
1+3+8+55=67
1+1+3+8+21+34=68
13+21+34=68←※
13+55=68
1+2+3+8+21+34=69
1+13+55=69
1+1+2+3+8+21+34=70
2+13+55=70
1+2+5+8+21+34=71
3+13+55=71
1+1+2+5+8+21+34=72
1+3+13+55=72
1+1+3+5+8+21+34=73
5+13+55=73
1+2+3+5+8+21+34=74
1+5+13+55=74
1+1+2+3+5+8+21+34=75
2+5+13+55=75
1+2+5+13+21+34=76
8+13+21+34=76←※
21+55=76
1+1+2+5+13+21+34=77
1+21+55=77
1+1+3+5+13+21+34=78
2+21+55=78
1+2+3+5+13+21+34=79
3+21+55=79
1+1+2+3+5+13+21+34=80
1+3+21+55=80
1+1+3+8+13+21+34=81
5+8+13+21+34=81←※
5+21+55=81
1+2+3+8+13+21+34=82
1+5+21+55=82
1+1+2+3+8+13+21+34=83
2+5+21+55=83
1+2+5+8+13+21+34=84
3+5+8+13+21+34=84←※
8+21+55=84
1+1+2+5+8+13+21+34=85
1+8+21+55=85
1+1+3+5+8+13+21+34=86
2+3+5+8+13+21+34=86←※
2+8+21+55=86
1+2+3+5+8+13+21+34=87←※
3+8+21+55=87
1+1+2+3+5+8+13+21+34=88←※
1+3+8+21+55=88
1+1+3+8+21+55=89
34+55=89←※
89=89
1+2+3+8+21+55=90
1+89=90
1+1+2+3+8+21+55=91
2+89=91
1+2+5+8+21+55=92
3+89=92
1+1+2+5+8+21+55=93
1+3+89=93
1+1+3+5+8+21+55=94
5+89=94
1+2+3+5+8+21+55=95
1+5+89=95
1+1+2+3+5+8+21+55=96
2+5+89=96
1+2+5+13+21+55=97
8+89=97
1+1+2+5+13+21+55=98
1+8+89=98
1+1+3+5+13+21+55=99
2+8+89=99
1+2+3+5+13+21+55=100
3+8+89=100


 攻略法さんからの続報です。(平成23年11月16日付け)

 個数が最少のものについての考察です。

(考察1)
・1個目  Nを超えない最大のフィボナッチ数(n番目)を、a とする。すなわち、a ≦N

  N=a+(N-a)

・2個目  これを繰り返して、

  N-a を超えない最大のフィボナッチ数を a とする。すなわち、a≦N-a 、m<n

  N=a+a+(N-(a+a))

・3個目

 ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

 残りの数 (N-(a+a+…)) がフィボナッチ数になるまで繰り返すことで、最少の個数を求
めることができる。

 また、m は、n-1ではなく、m≦n-2 となる。すなわち、隣り合うフィボナッチ数を使わない
ことがわかる。したがって、その個数が最多になる場合は、

 N=1+2+5+ … +an-2+a または、 N=1+3+8+ … +an-2+a

 n/2個と考えられる。n がある程度以上のとき、これより少なくなる。
(参考 1から100までの検証)

(考察2) 「碁石並べ」より、●を 1、○を 0 として、2進法 n 桁で、ビット列が、1が2つ以上
     並んではいけない(0は2つ以上並んでもかまわない)とする。

 各桁の重みは、n+1 番目のフィボナッチ数 an+1 で、

     …、144、89、55、34、21、13、8、5、3、2、1

とする。

6桁の場合、a6k=0〜[(6+1)/2]{6-k+1}=70+61+52+43=1+6+10+4=21(通り)

000000 = 0
000001 = 1
000010 = 2
000100 = 3
000101 = 3 + 1 = 4
001000 = 5
001001 = 5 + 1 = 6
001010 = 5 + 2 = 7
010000 = 8
010001 = 8 + 1 = 9
010010 = 8 + 2 = 10
010100 = 8 + 3 = 11
010101 = 8 + 3 + 1 = 12
100000 = 13
100001 = 13 + 1 = 14
100010 = 13 + 2 = 15
100100 = 13 + 3 = 16
100101 = 13 + 3 + 1 = 17
101000 = 13 + 5 = 18
101001 = 13 + 5 + 1 = 19
101010 = 13 + 5 + 2 = 20

 攻略法さんからの続報です。(平成23年11月17日付け)

 1が重複しないようにするには、

・2進法 n が偶数なら、2倍(2n)と2倍して+1した数(2n+1)を2つ生成する
・2進法 n が奇数なら、2倍の数(2n)を1つ生成する

とする。重複することなく自然数が生成されて、その数の個数はフィボナッチ数となる。

1(1) ※括弧内は対応する自然数

10(2)
├─────────────────────────────┐
100(3)                           101(4)
├─────────────────┐           │
1000(5)               1001(6)        1010(7)
├───────────┐     │           ├───────────┐
10000(8)        10001(9)  10010(10)        10100(11)       10101(12)
├─────┐     │     ├─────┐     ├─────┐     │
100000(13) 100001(14) 100010(15) 100100(16) 100101(17) 101000(18) 101001(19) 101010(20)



同様に、n=1 から、次の規則で数を順次生成していくこともできる。

・n が偶数なら、2倍(2n)と+1した数(n+1)を2つ生成する
・n が奇数なら、2倍の数(2n)を1つ生成する

重複することなく自然数が生成されて、その数の個数はフィボナッチ数となる。

1

2
├───────────────┐
4                3
├─────────┐     │
8          5     6
├─────┐   │     ├─────┐
16     9    10     12     7
├───┐ │   ├───┐ ├───┐ │
32   17 18   20   11 24   13 14
├─┐ │ ├─┐ ├─┐ │ ├─┐ │ ├─┐
64 33 34 36 19 40 21 22 48 25 26 28 15



 FNさんからのコメントです。(平成23年11月15日付け)

 (性質23)について、「フィボナッチ数とはフィボナッチ数列にあらわれる数」だから、「1」
はフィボナッチ数で、すべての自然数が「1」の何個かの和で表されるのは当たり前である。
だから、「異なる」を書いておくべきでしょう。
→ FNさんのご指摘ごもっともなので、文言を修正させていただきました。

 また、「いくつかの」ではあまり面白くないので、「いくつかの」がどの程度に押さえられるか
を考えるのが面白そうに思います。

 n がある程度以上のとき、「いくつかの」は、「[log2 n ]-1個以下の」ぐらいにできそうな気
がします。攻略法さんが調べられている範囲(n≦100)では、n≦4、n=6、7、12 を除いて成
り立っています。ただし、log2 n は、2を底とする対数、[x]は、x を越えない最大の整数。


(性質24) n+10n-11n-22+・・・+n-r (ただし、r≦n/2)

 パスカルの三角形で、左側の1を揃えて書くと、斜めの和がフィボナッチ数列となる。

  

 当HP読者で岩手県在住のK.Y.さんから、(性質24)を直接、数学的帰納法で証明され
たとのことで、その証明をメールにていただきました。(平成29年5月1日付け)

 2項係数 nk (0≦n、0≦k≦n) とフィボナッチ数列 {Fn} (0≦n) は、漸化式を用いて、
それぞれ次のように定義される。

 nkn-1kn-1k-1 ただし、n0nn=1

 Fn=Fn-1+Fn-2 ただし、F0=F1=1

 このとき、フィボナッチ数列の一般項 Fn は、2項係数nk を用いて次のように表される。

(*)  Fn=Σ k=0〜[n/2] n-kn-2k  (ただし、[x] はx を越えない最大の整数)

 この Fn と(性質24)における a との関係は、 Fn=an+1 である。

例 Fn=Σ k=0〜[n/2] n-kn-2k

   =nnn-1n-2n-2n-4+・・・+n-rn-2r ただし、r≦n/2

   =n0n-11n-22+・・・+n-r


 式(*)が正しいことを数学的帰納法を用いて証明する。

(証明) n=0 のとき、 左辺=F0=1 で、右辺=00=1 より、 左辺=右辺

 n=1 のとき、左辺=F1=1 で、右辺=11=1 より、 左辺=右辺

 以上から、命題は、n=0、1のときに成り立つ。

 r≧n≧0 のき、命題が成り立つと仮定する。すなわち、 Fn=Σ k=0〜[n/2] n-kn-2k

(イ) r が奇数のとき、 r=2m+1 (mは自然数) と表される。

  このとき、 r+1r+1=1、0m+10=1、r+1=2(m+1) に注意すると、

 Fr+1=Fr+Fr-1

    =Σ k=0〜m r-kr-2k+Σ k=0〜m r-1-kr-1-2k

    =r-1r-2+・・・+r-mr-2mr-1r-1r-2r-3+・・・+r-1-mr-1-2m

    =+(r-1r-2r-1r-1)+・・・+(r-mr-2mr-mr-2m+1)+m0

    =r-1+・・・+r-m+1r-2m+1m+10

    =r+1r+1r+1-1r+1-2+・・・+r+1-mr+1-2mr+1-(m+1)r+1-2(m+1)

    =Σ k=0〜m+1 r+1-kr+1-2k

 となり、命題は、n=r+1(r が奇数)のときも成り立つ。

(ロ) r が偶数のとき、 r=2m (mは自然数) と表される。

 このとき、 r−1=2(m−1)+1 に注意すると、

 Fr+1

=Fr+Fr-1

=Σ k=0〜m r-kr-2k+Σ k=0〜m-1 r-1-kr-1-2k

r-1r-2+・・・+r-mr-2mr-1r-1r-2r-3+・・・+r-mr+1-2m

+(r-1r-2r-1r-1)+・・・+(r-mr-2mr-mr-2m+1)

r-1+・・・+r-m+1r-2m+1

r+1r+1r+1-1r+1-2+・・・+r-m+1r-2m+1

r+1r+1r+1-1r+1-2+・・・+r+1-mr+1-2m

=Σ k=0〜m r+1-kr+1-2k

 となり、命題は、n=r+1(r が偶数)のときも成り立つ。

 以上から、命題(*)は、すべての整数n(n≧0)について成り立つ。  (証終)


(コメント) 久々にフィボナッチ数列に触れる機会をいただいたK.Y.さんに感謝します。


 攻略法さんが(性質24)について考察されました。(平成23年11月14日付け)

 (性質24)の組合せ論的解釈を得るために、次の問題を考える。

問題 碁石は○と●の2種類ある。10個の碁石を、●が隣り合わないように一列に並べる
   並べ方は何通りあるか。

(解) 碁石が1個のときは、 ○ または ● の通り

 碁石が2個のときは、 ○○ 、 ●○ 、 ○● の通り

 碁石が3個のときは、 ○○○ 、●○○ 、○●○ 、○○● 、●○● の通り

 碁石が4個のときは、 ○○○○ 、●○○○ 、○●○○ 、○○●○ 、○○○● 、
               ●○●○ 、●○○● 、○●○● の通り

 碁石が5個のときは、 ○○○○○ 、●○○○○ 、○●○○○ 、○○●○○ 、
               ○○○●○ 、○○○○● 、●○●○○ 、●○○●○ 、
               ●○○○● 、○●○●○ 、○●○○● 、○○●○● 、
               ●○●○● の13通り

  ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

 n個の碁石を、●が隣り合わないように並べる並べ方の総数を、an+2 通りであるとする。

 n≧3 のとき、 a1、 a2、・・・、an-2、an-1 が定まったとする。

 1つ目の石が○の場合、残りの n-1個の並べ方は、an+1 通りである。

 1つ目の石が●の場合、2つ目は、○でなければならず、残りの n-2個の並べ方は、a
通りである。

 ゆえに、 an+2=an+1+a が成り立つ。  (終)

 このことから、

(性質24) n+10n-11n-22+・・・+n-r (ただし、r≦n/2)

において、左辺は、碁石が n−1個ある場合に、●が隣り合わないように並べる並べ方の
総数である。上記の証明から、数列{a}は、フィボナッチ数列となる。

 右辺の n-k (k=0、1、2、・・・、r)は、n−1個の碁石のうち、●が k 個あるときに、

 ○の n−1−k+1=n−k 個の隙間に k 個の●を挿入する場合の数に等しい。

○の隙間の数 n−k が、●の個数 k 以上であることは自明だろう。

 この組合せ論的解釈を攻略法さんが詳細に調べられました。

(組合せ論的解釈) ●の個数で考える。●と○で計n個並べるとする。

●が0個のとき、 n個すべてが○の1通り

●が1個のとき、 (n-1)個の○、1個の●の並べ方なので、 1=n (通り)

●が2個のとき、2個ある●の間に○が1個以上

 例 n=6 の場合

  ●○●○○○ 、●○○●○○ 、●○○○●○ 、●○○○○● 、○●○●○○
  ○●○○●○ 、○●○○○● 、○○●○●○ 、○○●○○● 、○○○●○●

 これは、○○…○の間および両端を合わせて((n-3)+2)箇所から、2個の●を選び1個ずつ
入れることなので、 n-3+22=n-12 (通り)

●がk個のとき、すべての●と●の間に○が1個以上。これは、○○…○の間および両端を
合わせて、((n-(k+1))+2)箇所からk個の●を選び1個ずつ入れることなので、n-k+1 (通り)

 ここで、kの範囲は、すべての●と●の間(k-1)箇所に○が1個は必要なので、○の個数を
mとすると、k-1≦m で、k+m=n より、0≦k≦n-k+1 となる。

 以上から、●が0個のとき、 n+10 と表して合計すると、an+2=Σ0≦k≦n-k+1n-k+1


 実際に計算してみると、

 a1=1、 a2=1、 a3k=0〜12-k)=20+11=1+1=2、

 a4k=0〜13-k)=30+21=1+2=3、 a5k=0〜24-k)=40+31+22=1+3+1=5、

 a6k=0〜25-k)=50+41+32=1+4+3=8、

 a7k=0〜36-k)=60+51+42+33==1+5+6+1=13、

   ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

 また、●と○のn個の列は、(n+1)段の階段の上り方で、各段を踏むか踏まないかの状態
(足跡、○は踏む)を具体的に示している。(→ 参考:「階段」)

(コメント) 攻略法さん、組合せ論的解釈に感動しました!証明はどうするのだろうと思案
      していました。感謝いたします。なお、一部文言等を修正させていただきました。
      ご了承ください。同趣旨のことをK.S.さんからもメールで頂きました。K.S.さん
      に感謝いたします。


 K.S.さんからの続報です。(平成23年11月11日付け)

 N試合で連敗しないような試合のあり方は、階段で踏まなかったところが負けた意味となり、
連続して踏まないことはないので、同じ数になる。

 また、1×2のタイルを、2×Nに敷き詰める方法の数について、

 N=1 のとき、明らかに、1通り

 N=2 のとき、横2列 または 縦2列 の2通り

 N=3 のとき、最初に、縦1列のとき、その右隣は、横2列 または 縦2列 の2通り

          最初に、横2列のとき、その右隣は、縦1列のみ

     以上から、場合の数は、3通り

 N=4 のとき、最初に、縦1列のとき、その右隣は、2×3 なので、敷き詰め方は、3通り

          最初に、横2列のとき、その右隣は、2×2 なので、敷き詰め方は、2通り

     以上から、場合の数は、3+2=5通り

  ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

 したがって、敷き詰め方の場合の数は、フィボナッチ数となる。

 また、次の性質も成り立つ。

(性質25)  

 これは、ビネの公式から明らかだろう。

(コメント) フィボナッチ数列の種々の視座を与えていただいて、K.S.さんに感謝します。


 攻略法さんが、いろいろな問題に現れるフィボナッチ数列について考察されました。
                                     (平成23年11月18日付け)

例1 黄金比φとして、1,φ,φ2,φ3,φ4, … という等比数列を考えたとき、1+φ=φ2
  利用すると
φ = φ
φ2 = φ + 1
φ3 = 2φ + 1
φ4 = 3φ + 2
φ5 = 5φ + 3
φ6 = 8φ + 5
φ7 = 13φ + 8   
 :


   1次式の係数や定数項にフィボナッチ数が現れる。


(追記) 令和3年6月28日付け

 攻略法さんの上記の式を変形すると、フィボナッチ数は黄金比の累乗で表せる。これは、
ビネ(Binet)の公式(1843)からも推察されることだろう。

 1=φ0+0/φ2

 2=φ1+1/φ2 ・・・ φ1+1/φ2=(φ3+1)/φ2=2(φ+1)/φ2=2

 3=φ2+1/φ2 ・・・ φ2+1/φ2=(φ4+1)/φ2=3(φ+1)/φ2=3

 5=φ3+2/φ2

 8=φ4+3/φ2

 13=φ5+5/φ2

 21=φ6+8/φ2

 ・・・・・・・・・・・・・・

 リュカ数についても同様の表現が可能である。

 1=φ−1/φ ・・・ φ−1/φ=(φ2−1)/φ=φ/φ=1

 3=φ2+1/φ2 ・・・ φ2+1/φ2=(φ4+1)/φ2=3(φ+1)/φ2=3

 4=φ3−1/φ3 ・・・ φ3−1/φ3=(2φ+1)−1/(2φ+1)=4(2φ+1)/(2φ+1)=4

 7=φ4+1/φ4

 11=φ5−1/φ5

 18=φ6+1/φ6

 ・・・・・・・・・・・・・・


例2 2倍取りゲーム (→ 参考:「ニムゲームの話題」)

 1つの山にいくつかの石がある。次のルールで、2人が交互に石を取っていき、最後の石
を取った方が勝ちというゲームをする。

・先手は第1手では1個以上何個取ってもよい。ただし、山全部の石を取ってはいけない。

・先手の第1手以外では、1個以上直前の相手の取った石の個数の2倍以下の石を取って
よい。

 たとえば、最初に20個の石があったなら、先手の第1手では1個から19個まで取れる。仮
に3個取ったとすると、後手は1個から6個まで取れる。

 このゲームの必勝法を考えよ。

(解) 最初の石の数がフィボナッチ数でない限り先手必勝となる。

 石が20個の場合、20=13+5+2のように、より大きなフィボナッチ数(隣接するフィボナッチ

数ではない)を用いて石の個数を分解し、そのうち最小のフィボナッチ数の個数の石を取

ればよい。実際に、

(a) この条件でのフィボナッチ数への分解は一意である。

(b) 分解した数の比は2倍よりも大きい。なぜならば、n≧m+2 なら、a>2・a

  ルールから最小のフィボナッチ数を取った次の手では、その次のフィボナッチ数を取れ

ない。よって、和の中のフィボナッチ数の個数を減らせない。  (終)


例 石の個数が3個のとき、先手の第1手は、1個または2個取れる。

  先手の取った石が1個のとき、残りは2個。後手は、1×2=2個以下の石が取れるの
  で、2個全部取って、後手の勝利!

  先手の取った石が2個のとき、残りは1個。後手は、2×2=4個以下の石が取れるの
  で、1個全部取って、後手の勝利!

例 石の個数が4個のとき、先手の第1手は、1個または2個または3個取れる。
  先手の取った石が1個のとき、残りは3個。後手は、1×2=2個以下の石しか取れな
  いので、残りは、1個または2個。何れにしても次の先手が残り全部の石を取れるので、
  先手の勝利!

  先手の取った石が2個のとき、残りは2個。後手は、2×2=4個以下の石が取れるの
  で、残り全部取って、後手の勝利!

  先手の取った石が3個のとき、残りは1個。後手は、3×2=6個以下の石が取れるの
  で、残り全部取って、後手の勝利!

  以上から、先手必勝のためには、先手が第1手で、1個取ればよい。

  この戦略は次の事実に基づいている。
   4=3+1 と、より大きなフィボナッチ数に分解するとき最小のフィボナッチ数は1

例 石の個数が6個のとき、6=5+1 なので、先手が第1手で石を1個取れば必勝であ
 る。実際に、残りは5個で、後手が取れる石の個数は2個以下。

  後手の取る石が1個のとき、残りは4個で、
      4=3+1 より、先手が1個取って、先手の勝利。

  後手の取る石が2個のとき、残りは3個で、
      先手が3個全部取って、先手の勝利。

例 石の個数が7個のとき、7=5+2 なので、先手が第1手で石を2個取れば必勝であ
 る。実際に、残りは5個で、後手が取れる石の個数は4個以下。

  後手の取る石が1個のとき、残りは4個で、
      4=3+1 より、先手が1個取って、先手の勝利。

  後手の取る石が2個のとき、残りは3個で、先手が3個全部取って、先手の勝利。

  後手の取る石が3個のとき、残りは2個で、先手が2個全部取って、先手の勝利。

  後手の取る石が4個のとき、残りは1個で、先手が1個全部取って、先手の勝利。


(追記) 令和2年12月12日付け

 上記で、

(性質23) 全ての自然数は、異なるいくつかのフィボナッチ数の和として表すことが
      できる。


の話題が取り上げられたが、もっと強い事実があることをDD++さんよりご教示いただいた。

ゼッケンドルフの定理

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

 フィボナッチ数は、

 1 ,1 ,2 ,3 ,5 ,8 ,13 ,21 ,34 ,55 ,89 ,144 ,233 ,377 ,・・・

という数であるが、「連続しない」ということを考慮すると、次のように一意に表現できる。
1=1 2=2 3=3 1+3=4  
5=5 1+5=6 2+5=7 8=8  
1+8=9 2+8=10 3+8=11 1+3+8=12  
13=13 1+13=14 2+13=15 3+13=16 ・・・・・・


 攻略法さんからの続報です。(平成23年11月18日付け)

例3 x を x2-x-1 で割ったとき、商や余りの係数にフィボナッチ数が現れる。

例 x10÷(x2-x-1) の商は、x8+x7+2x6+3x5+5x4+8x3+13x2+21x+34、余りは、55x+34

(証明) x=(x2-x-1)(a1n-2+a2n-3+ … +an-k-1k+ … +an-32+an-2x+an-1) + anx+an-1

    両辺の係数を比較して、

  x の係数から、 a1=1

  xn-1 の係数から、 a2-a1=0  なので、 a2=1

  xn-2 の係数から、 a3-a2-a1=0  なので、 a3=a2+a1=2

  :

  x の係数 a-an-1-an-2=0  なので、 a=an-1+an-2

  定数項 an-1-an-1=0  (証終)

 ここで、例1は、x=φ として、余りに着目したもの。

例4 数理マジック「17番目の不思議」 ・・・ 任意の3桁の数の各桁の和を計算する。

 724
+ 111 ← 最初は111との和
-----
+ 835
----- + 111
+ 946 ← 2回目以降は、1つ上の数(ここでは、111)との和
----- + 835
+ 771 ← 5+6=11、8+9=17のように10を超える場合は、1位の数のみ。桁上りはしない。
----- + 946
+ 617
----- + 771
+ 388
----- + 617
+ 995
----- + 388
+ 273
----- + 995
+ 168
----- + 273
+ 331
----- + 168
+ 499
----- + 331
+ 720
----- + 499
+ 119
----- + 720
+ 839
----- + 119
+ 948
----- + 839
+ 777 ← 17番目の数

(証明) 最初の2つの数を、a、b=111 とする。

a+b、a+2b、2a+3b、3a+5b、5a+8b、8a+13b=8a+3b、13a+11b=3a+b、
                                      … 、4a+3b、3a+7b、7a、7b

 a (mod 10)に着目して、 1、1、2、3、5、8、…、4、3、7、0、7  (証終)


(追記) 当HPがいつもお世話になっているHN「空舟」さんより、平成25年4月16日付けで
    「フィボナッチ数をpで割った余りについて」と題して投稿頂いた。

 [行列によって示されること]

 A=(0,1 ; 1,1) によって[";"は改行を表す]、A2=(1,1 ; 1,2)、A3=(1,2 ; 2,3)、A4=(2,3 ; 3,5) ・・が
得られる。

 pを素数とする時、Am≡(1,0 ; 0,1) (mod p) となるmを見つけることは、フィボナッチ数列
をpで割った余りの周期がmとなることを意味する。

 (a,b ; b,c) (a,b,c∈Z/pZ) の形の"剰余類"は、p3個ある。そのうち、行列式≡0 となるもの
を除いた"既約剰余類"は、p3−p個ある。

 既約剰余類は乗法群をなすので、群論のラグランジュの定理により、Ap3-p≡(1,0 ; 0,1) が
得られた。すなわち、フィボナッチ数をpで割った余りは周期 p3−p を持つ。

 以上の議論は簡単だが、結果の精度は悪い。(anを15で割った余りが周期φ(p)=8を持つ
という主張と似ている。)実際、整数論的な考察をすると、さらに強い結果が得られる。
(剰余体Z/pZにおける(x2-x-1)の根の様子によって分類される)

 その結果は大変興味深いと思うので紹介したい:

p=2 では、周期は3である。
p=5 では、周期は20である。(実際 F[n]≡2n*3n (mod 5) が成り立つ)
p=5N±1型素数のときは、F[n]をpで割った余りは周期 p-1 を持つ。
p=5N±2型素数のときは、F[n]をpで割った余りは周期 2(p+1)を持つ。
(ただしこれらが最短周期かどうかは分からない。)

 F[0]=0であるから、その周期に対してF[n]がpで割り切れることが従うが、pを4で割った余
りによりもう一歩踏み込める。

 複号は、p=5N±1型の時マイナス、p=5N±2型のときプラスとする。

p=4N±1型のときは、 F[(p±1)/2]がpで割り切れる。
p=4N±3型のときは、 F[(p±1)]はpで割り切れるがF[(p±1)/2]はpで割り切れない。

 素数のべきについては次が成り立つ。

 pを素数、q≧1とすると、

 F[n]がpq で割り切れる ⇒ F[np]は pq+1 で割り切れる

(p=q=2を除けば、逆もたぶん成り立つと思います。)


(追記) 平成25年12月14日付け

 「フィボナッチでの新たな驚き」と題して、当HPがいつもお世話になっているHN「GAI」さん
からの投稿です。

 フィボナッチ数列には、いろいろな性質があることは、上記でも数多く紹介されているとは
思いますが、次のことを計算していて気づいたことがありました。

 a0=1、a1=1、an+2=an+1+a (n=0,1,・・・)で定まるフィボナッチ数列の母関数とし
て( → 参考:「不思議な分数」)

 

    =a0+a1X+a22+・・・+an+an+1n+1+an+2n+2+・・・

が決められるが、この関数から、

 F(0/1)=1(=1^2) 、F(1/2)=4(=2^2) 、F(3/5)=25(=5^2) 、F(8/13)=169(=13^2)

 F(21/34)=1156(=34^2) 、F(55/89)=7921(=89^2) 、F(144/233)=54289(=233^2)

   ・・・・・・・・・・・

と一般に、F(an-1/a)=a2 が成立していく。(右辺の値→整数列大辞典「A081068」)

また、a1=1、a2=1、an+2=an+1+a (n=1,2,・・・)で定まるフィボナッチ数列の母関数
として、
     G(X)=X/(1−X−X2)=a1X+a22+・・・+an+・・・

が決められるが、この関数から、

 G(1/2)=2(=1・2) 、G(3/5)=15(=3・5) 、G(8/13)=104(=8・13) 、G(21/34)=714(=21・34)

 G(55/89)=4895(=55・89) 、G(144/233)=33552(=144・233) 、G(377/610)=229970(=377・610)

   ・・・・・・・・・・

と一般に、G(an-1/a)=an-1・a が成立していく。(右辺の値→整数列大辞典「A081018」)

 こんな法則が潜んでいることにびっくりしました。


(コメント) 母関数って、不思議ですね!大変美しい性質だと思います。GAI さんに感謝し
      ます。


 カルピスさんからのコメントです。(平成25年12月15日付け)

 私も、数日前に知ったことですが、フィボナッチ数列は、隣同士が、どんどん黄金比に近
づいていくことを初めて知って感動しました。(参考 → (性質25))


(追記) 平成26年8月24日付け

 当HP読者のHN「Fibo」さんから、フィボナッチ数の性質についてコメントを頂いた。

 フィボナッチ数列は、一般に、「前々項+前項=自項」となる数列ですので、

 (1)前々項と前項  (2)前々項と自項  (3)前項と自項

の三つのうちどれか一つの組み合わせが判れば、三数のうちの残りの数値を求める事がで
きます。

(例) (1) Fn-2+Fn-1=Fn  (2) Fn-Fn-2=Fn-1   (3) Fn-Fn-1=Fn-2

(A) FnとFn+3を使って、Fn+1を導く事ができます。 →  (Fn+3/2 - Fn/2)  =Fn+1
(B) 同じく、FnとFn+3を使って、Fn+2を導く事ができます。 → (Fn+3   + Fn)/2  =Fn+2

(実例に用いる表)
項数  1  2  3   4   5  6   7   8   9   10  11   12
fib数 1   1  2  3  5  8  13   21  34  55  89   144
Fn    -5   -4   -3   -2   -1  Fn  +1   +2   +3   +4    +5   +6


(A) Fnが第1項の時 (  3/2=1.5  - 1/2 =0.5 ) = 1=Fn+1
   Fnが第2項の時 (  5/2=2.5  - 1/2 =0.5 ) = 2=Fn+1
    Fnが第3項の時 (  8/2=4    -  2/2=1   ) = 3=Fn+1
   Fnが第4項の時 ( 13/2=6.5  -  3/2=1.5 ) = 5=Fn+1
   Fnが第5項の時 ( 21/2=10.5 -  5/2=2.5 ) = 8=Fn+1  (以下略)

 ここで、お気付きになられたと思いますが、上記のカッコ内の「-」符号を「+」に替えた場合、
Fn+2が求まる事がお解かりになられると思います。

 (B)の式も順を追って検証して頂ければ納得して頂けると思います。


(コメント) 
Fiboさん、投稿ありがとうございます。堪能させていただきました。


(追記) 平成27年3月1日付け

 平成27年度入試 東京大学 前期理系 で次のような問題が出題された。数学的帰納法
の適当な練習となろう。

問題 数列{p}を次のように定める。

     p1=1、p2=2、pn+2=(pn+12+1)/p  (n=1,2,3,・・・)

(1) (pn+12+p2+1)/(pn+1)がnによらないことを示せ。

(2) すべてのn=2,3,4,・・・に対し、pn+1+pn-1をpのみを使って表せ。

(3) 数列{q}を次のように定める。

     q1=1、q2=1、qn+2=qn+1+q  (n=1,2,3,・・・)

   すべてのn=1,2,3,・・・に対し、p=q2n-1を示せ。

(解)(1) (pn+22+pn+12+1)/(pn+2n+1

 =({(pn+12+1)/p2+pn+12+1)/({(pn+12+1)/p}pn+1

 =((pn+12+1)2+(pn+12+1)p2)/{(pn+12+1)pn+1

 =(pn+12+p2+1)/(pn+1

 よって、(pn+12+p2+1)/(pn+1)はnによらず一定である。

(2) (1)より、 (pn+12+p2+1)/(pn+1)=(p22+p12+1)/(p21)=6/2=3

  よって、 pn+12+p2+1=3pn+1

  また、 pn+12+1=pn+2 なので、 p2+pn+2=3pn+1

  p≠0 なので、 p+pn+2=3pn+1 より、 pn-1+pn+1=3p

(3) 自然数nについての数学的帰納法により、命題「p=q2n-1」が成り立つことを示す。

n=1のとき、左辺=p1=1、右辺=q1=1 より、左辺=右辺で、n=1のとき成り立つ。

n=2のとき、左辺=p2=2、右辺=q3=q1+q2=2 より、左辺=右辺で、n=2のとき

成り立つ。

n=k、k+1(k≧1)のとき成り立つと仮定する。すなわち、 p=q2k-1、pk+1=q2k+1

このとき、

2k+3=q2k+2+q2k+1

   =q2k+1+q2k+q2k+1=2q2k+1+q2k=2q2k+1+q2k+1−q2k-1=3q2k+1−q2k-1

において、(2)より、3pk+1=p+pk+2 なので、 3q2k+1=q2k-1+pk+2 すなわち、

k+2=3q2k+1−q2k-1 より、 pk+2=q2k+3

 よって、命題は、n=k+2のときも成り立つ。

 したがって、すべての自然数nに対して、命題は成り立つ。  (終)


(コメント) 標準的な数学的帰納法の問題でした。合格のためには落とせない問題ですね。


 とるえんさんからのコメントです。(平成28年6月13日付け)

 n番目のフィボナッチ数を F(n) と表すことにします。

 F(n2)がF(n)2で割り切れるようなF(n)は無数に存在するのでしょうか?

 自分で見つけられたのは、n=1、2、5のときだけでした。もっとも、プログラムの関係で
n=22までしか調べられていないのですが・・・。どなたかご教示ください。


(コメント) F(n2) がF(n)で割り切れることは明らかなので、さらに、その商F(n2) /F(n)が
      F(n) で割り切れることが無限にあるかということ。


 Seiichi Manyamaさんからのコメントです。(平成28年6月14日付け)

 F(nk) が F(n)k で割り切れるような例を(Ruby)によるプログラムで見つけました。ちなみに
調べる範囲を狭めているので実行時間は1分くらいでしょう。

(実行結果) k=2、3、4、5、6、7、8、9、10 について、n=1、2、5 のみ

 そこで、すこし強引ですが、次の予想をしてみました。

(予想) k を2以上の整数とする。F(nk) が F(n)k で割り切れるとき、n=1、2、5 に限る。

 n=1、2 は自明ですね。


 Seiichi Manyamaさんからのコメントです。(平成28年6月15日付け)

 「A128935」のコメントを読むと、F(5n) / F(5)n = m * 1000 + 1 と書けるらしい。


(コメント) F(5n) / 5n=F(5n) / F(5)n≡1 (mod 1000) ということですね。


 at さんからのコメントです。(平成28年6月19日付け)

 数学サイト「数学の部屋」の「フィボナッチ数列の性質」によれば、F(m) が F(n)2 で割り切
れるような m の最小値は、m=n*F(n)であるようです。

 そうすると、n>6 のときには、 n*F(n)>n2 ですから、F(n2) が F(n)2 で割り切れるような
n は、n=1、2、5 のみ ということになりますね。


 Seiichi Manyamaさんからのコメントです。(平成28年6月19日付け)

 k = 2 のときについて、F(nk) が F(n)k で割り切れるような n は、n=1、2、5 のみということ
みたいですね。素晴らしいです!


 とるえんさんからのコメントです。(平成28年6月21日付け)

 皆様ご回答ありがとうございます。

 興味深い性質ですが、このことの証明は易しくないようですね・・・。フィボナッチ数の神秘を
また一つ垣間見た気分です。


 空舟さんからのコメントです。(平成28年6月25日付け)

 いくつかの性質を既知とすると見通し良いと思います

[結論] F[n]が2または5以外の奇素数で割り切れる時、F[nk]はF[n]kで割り切れ得ない。

(そうでないnが、n=1、2、5に限ることを示すのは難しくないと思います。)

 断らない変数は(文脈に応じて正の)整数とする。

[場合1] F[n]が2で割り切れる場合

  Xが2で割り切れる回数を v(X) とおく。

[補題1-1] F[n]が2で割り切れる時、n=3j とおける。

[補題1-2] j が奇数のとき、v(F[3j])=1

       j が偶数のとき、v(F[3j])=2+v(j) が成り立つ。

[議論]

・j が奇数のとき、v(F[n]k)=k 、v(F[nk])=1

・j が偶数のとき、v(F[n]k)=k*{2+v(j)} 、v(F[nk])=2+v(3k-1*jk) = 2 + k*v(j)

 [nk=3J による J=3k-1*jk を j として補題1-2に適用]

 比較により、k≧2 のとき、F[nk]はF[n]kで割り切れ得ないことが言える。


[場合2] F[n]が奇素数pで割り切れる場合

  Xがpで割り切れる回数をv(X)とおく。

[補題2-1] F[n]がpで割り切れる時、F[n]がpで割り切れる最小の正の整数nをmとおくと、
      n=mj とおける。

[補題2-2] このmによって、v(F[mj])=v(F[m])+v(j) が成り立つ。

[補題2-3] p=5N±1型素数のとき、mはp-1の約数
       p=5N±2型素数のとき、mはp+1の約数

 従って、p≠5ならば、mとpは互いに素である。これを v(mk-1)=0 として後で使う。

[議論]

v(F[n]k)=k*{v(F[m])+v(j)}

v(F[nk])=v(F[m])+v(mk-1*jk) = v(F[m]) + k*v(j)

 比較により、k≧2 のとき、F[nk]はF[n]kで割り切れ得ないことが言える。


 因みに、この設定でのv(F[m])は大抵の素数pに対して1となりますが、1にならないようなp
が存在するかどうかは未解決のようです。
(→ 参考)(→ 補題の周辺)(→ 素数ベキによる整除に関する定理
 x,yの範囲を非整数x={(1+√5)/2}^m, y={(1-√5)/2}^mに形式的に拡張した形。


 GAI さんからのコメントです。(平成29年5月3日付け)

 一連のフィボナッチ数列に関する話題の中に、逆数や積のことが入ってなかったので、そ
れに関することで、次のことが成り立つことを読んだのでメモしておきます。

 フィボナッチ数列 a[1]=1、a[2]=1、a[n+2]=a[n]+a[n+1] (n=1,2,・・・)であるとき、

(イ) Σn=1〜∞ 1/a[n]=Σn=0〜∞ (-1)n/(φ2n+1-(-1)n)=3.3598856662・・・

(ロ) Σn=0〜∞ 1/a[2n]=4-φ=2.38196601125・・・

(ハ) Πk=1〜n a[k]〜C*φ^(n(n+1)/2)/5^(n/2)

 ただし、φ=(1+)/2=1.6180339887・・・ (黄金比)
       C=Πn=1〜∞ (1-(-1)n2n)=1.2267420107・・・ なる定数とする。

 フィボナッチ数列には黄金比が深く関わっていることが見てとれます。


(追記) 「フィボナッチ数のべき乗数」と題して、GAI さんからご投稿いただきました。
                                      (令和2年12月13日付け)

 フィボナッチ数 {F(n)}:0,1,1,2,3,5,8,13,21,35,・・・ に関して、必ず示される漸化式が

  F(n+2)=F(n+1)+F(n)

 そこで、このフィボナッチ数のm乗数:F(n)^mについて調べると、

F(n+3)^2=2*F(n+2)^2+2*F(n+1)^2-F(n)^2

F(n+4)^3=3*F(n+3)^3+6*F(n+2)^3-3*F(n+1)^3-F(n)^3

F(n+5)^4=5*F(n+4)^4+15*F(n+3)^4-15*F(n+2)^4-5*F(n+1)^4+F(n)^4

  ・・・・・・・・・・・・・・・

が成立しています。

 m=5、6、・・・ に挑戦してほしい。


(コメント) 少し気になったので計算してみました。

F(n+3)^2=(F(n+2)+F(n+1))^2=F(n+2)^2+2*F(n+2)F(n+1)+F(n+1)^2

=F(n+2)^2+2*(F(n+1)+F(n))F(n+1)+(F(n+2)-F(n))^2

=F(n+2)^2+2*F(n+1)^2+2*F(n) F(n+1)+F(n+2)^2-2*F(n+2)F(n)+F(n)^2

=2*F(n+2)^2+2*F(n+1)^2+2*F(n) (F(n+1)-F(n+2))+F(n)^2

=2*F(n+2)^2+2*F(n+1)^2-2*F(n)^2+F(n)^2

=2*F(n+2)^2+2*F(n+1)^2-F(n)^2

 他も同様かな?でも大変そう...。


 at さんからのコメントです。(令和4年7月31日付け)

 m=5、6、・・・ に挑戦してほしい。

 (F(n+6))^5、(F(n+7))^6 は、次のようになります。

(F(n+6))^5=8*(F(n+5))^5+40*(F(n+4))^5-60*(F(n+3))^5-40*(F(n+2))^5+8*(F(n+1))^5+(F(n))^5

(F(n+7))^6=13*(F(n+6))^6+104*(F(n+5))^6-260*(F(n+4))^6
                     -260*(F(n+3))^6+104*(F(n+2))^6+13*(F(n+1))^6-(F(n))^6

 一般には、次のようになります。

 mを正整数、s、t を実数(ただし、t^2+4*s≠0、t≠0)とするとき、漸化式

  a(n+2)=s*a(n)+t*a(n+1)

を満たす数列 {a(n)} に対して、等式

(a(n+m+1))^m
=Σ[k=1〜m+1](a(n+m+1-k))^m*((-1)^(k+1))*((-s)^(k*(k-1)/2))*(Π[j=1〜k]A(m+2-j)/A(j))

が成り立ちます。ここで、{A(n)}は以下で定まる数列です。

 A(0)=0 、A(1)=1 、A(n+2)=s*A(n)+t*A(n+1) (n≧0)

(証明) α=(t+√(t^2+4*s))/2、β=(t-√(t^2+4*s))/2 とします。

 a(n)=v*α^n+w*β^n (v,wは定数) と表せます。G(z)=Σ[n≧0](a(n))^m*z^n とおくと、

G(z)
=Σ[n≧0](v*α^n+w*β^n)^m*z^n
=Σ[n≧0]z^n*(Σ[j≧0]comb(m,j)*(v*α^n)^j*(w*β^n)^(m-j))
=Σ[n≧0]z^n*(Σ[j≧0]comb(m,j)*(v^j*w^(m-j))*((α/β)^j*β^m)^n)
=Σ[n≧0]Σ[j≧0]comb(m,j)*(v^j*w^(m-j))*(z*(α/β)^j*β^m)^n
=Σ[j≧0]comb(m,j)*(v^j*w^(m-j))*(Σ[n≧0](z*(α/β)^j*β^m)^n)
=Σ[j≧0]comb(m,j)*(v^j*w^(m-j))*(1/(1-z*(α/β)^j*β^m)).

よって、 G(z/(β^m))=Σ[j≧0]comb(m,j)*(v^j*w^(m-j))*(1/(1-z*(α/β)^j)).

両辺に、Π[j=0〜m](1-z*(α/β)^j) をかけると、

 G(z/(β^m))*Π[j=0〜m](1-z*(α/β)^j)=(zについてのm次以下の多項式)

となります。両辺の z^(n+m+1) の係数を比較して、

 [z^(n+m+1)](G(z/(β^m))*Π[j=0〜m](1-z*(α/β)^j))=0

 [z^(n+m+1)](G(z/(β^m))*Π[j=0〜m](1-z*(α/β)^j))
=Σ[k=0〜m+1]([z^(n+m+1-k)]G(z/(β^m)))*([z^k]Π[j=0〜m](1-z*(α/β)^j)))

ここで、[z^(n+m+1-k)]G(z/(β^m))=(a(n+m+1-k))^m*(1/β)^(m*(n+m+1-k))

また、[z^k]Π[j=0〜m](1-z*(α/β)^j) は少々厄介ですが、

[z^k]Π[j=0〜m](1-z*(α/β)^j)
=((-1)^k)*((α/β)^(k*(k-1)/2))*Π[j=1〜k](1-(α/β)^(m+2-j))/(1-(α/β)^j)

となります。

(一般に、

[z^k](Π[j=0〜m](1-z*γ^j))=((-1)^k)*(γ^(k*(k-1)/2))*Π[j=1〜k](1-γ^(m+2-j))/(1-γ^j))

となります。このことは後に証明します。)

よって、

[z^(n+m+1)](G(z/(β^m))*Π[j=0〜m](1-z*(α/β)^j))
=Σ[k=0〜m+1](a(n+m+1-k))^m*(1/β)^(m*(n+m+1-k))*((-1)^k)*((α/β)^(k*(k-1)/2))
                           *Π[j=1〜k](1-(α/β)^(m+2-j))/(1-(α/β)^j)
=Σ[k=0〜m+1](a(n+m+1-k))^m*((-1)^k)*((α*β)^(k*(k-1)/2))
            *(Π[j=1〜k](β^(m+2-j)-α^(m+2-j))/(β^j-α^j))*(1/β)^(m*(n+m+1))
=Σ[k=0〜m+1](a(n+m+1-k))^m*((-1)^k)*((-s)^(k*(k-1)/2))
                          *(Π[j=1〜k]A(m+2-j)/A(j))*(1/β)^(m*(n+m+1))

 これが 0 に等しいので、

(a(n+m+1))^m
= Σ[k=1〜m+1](a(n+m+1-k))^m*((-1)^(k+1))*((-s)^(k*(k-1)/2))*(Π[j=1〜k]A(m+2-j)/A(j)).


[z^k](Π[j=0〜m](1-z*γ^j))=((-1)^k)*(γ^(k*(k-1)/2))*Π[j=1〜k](1-γ^(m+2-j))/(1-γ^j)

であることの証明:

 G(γ,z)=Π[j=0〜m](1-z*γ^j) とおき、G(γ,z)を展開したときの z^k の係数を U(γ,k) とし
ます。

 そうすると、G(γ,z)=Σ[k=0〜m+1]U(γ,k)*z^k

 等式 (1-z*γ^(m+1))*G(γ,z)=(1-z)*G(γ,z*γ) が成り立ちます。

 この等式の両辺のz^kの係数を比較して、

  U(γ,k)-U(γ,k-1)*γ^(m+1)=U(γ,k)*γ^k-U(γ,k-1)*γ^(k-1)

よって、

U(γ,k)=((γ^(m+1)-γ^(k-1))/(1-γ^k))*U(γ,k-1)
    =((γ^(m+1)-γ^(k-1))*(γ^(m+1)-γ^(k-2))/((1-γ^k)*(1-γ^(k-1))))*U(γ,k-2)
    =…
    =(Π[j=1〜k](γ^(m+1)-γ^(k-j))/(1-γ^j))*U(γ,0)
    =Π[j=1〜k](γ^(m+1)-γ^(k-j))/(1-γ^j)
    =((-1)^k)*(γ^(k*(k-1)/2))*Π[j=1〜k](1-γ^(m+2-j))/(1-γ^j)


 GAI さんからのコメントです。(令和4年8月1日付け)

 2年前の投稿だったので忘れていました。ちなみに10乗までの式を置いておきます。

F(n+8)^7=21*(F(n+7))^7+273*(F(n+6))^7-1092*(F(n+5))^7-1820*(F(n+4))^7
                     +1092*(F(n+3))^7+273*(F(n+2))^7-21*(F(n+1))^7-(F(n))^7

F(n+9)^8=34*(F(n+8))^8+714*(F(n+7))^8-4641*(F(n+6))^8-12376*(F(n+5))^8
         +12376*(F(n+4))^8+4641*(F(n+3))^8-714*(F(n+2))^8-34*F(n+1))^8+(F(n))^8

F(n+10)^9=55*(F(n+9))^9+1870*(F(n+8))^9-19635*(F(n+7))^9-85085*(F(n+6))^9+136136*(F(n+5))^9
             +85085*(F(n+4))^9-19635*(F(n+3))^9-1870*(F(n+2))^9+55*(F(n+1))^9+(F(n))^9

F(n+11)^10=89*(F(n+10))^10+4895*(F(n+9))^10-83215*(F(n+8))^10-582505*(F(n+7))^10
              +1514513*(F(n+6))^10+1514513*(F(n+5))^10-582505*(F(n+4))^10
               -83215*(F(n+3))^10+4895*(F(n+2))^10 +89*(F(n+1))^10-(F(n))^10

 なお、10乗の式を構成するには、プログラム的に

gp > A(n)=matrix(n,n,i,j,binomial(i-1,n-j));
gp > charpoly(A(11),x)
%150 =x^11 - 89*x^10 - 4895*x^9 + 83215*x^8 + 582505*x^7 - 1514513*x^6
               - 1514513*x^5 + 582505*x^4 + 83215*x^3 - 4895*x^2 - 89*x + 1

 なお、

gp > A(11)
%151 =
[0  0  0   0   0   0   0   0   0  0 1]
[0  0  0   0   0   0   0   0   0  1 1]
[0  0  0   0   0   0   0   0   1  2 1]
[0  0  0   0   0   0   0   1   3  3 1]
[0  0  0   0   0   0   1   4   6  4 1]
[0  0  0   0   0   1   5  10  10  5 1]
[0  0  0   0   1   6  15  20  15  6 1]
[0  0  0   1   7  21  35  35  21  7 1]
[0  0  1   8  28  56  70  56  28  8 1]
[0  1  9  36  84 126 126  84  36  9 1]
[1 10 45 120 210 252 210 120  45 10 1]


の行列を意味する。(パスカルの三角形を右詰めで作る。) この行列の特性方程式を導くの
がcharpolyコマンドです。

 この式から、%150=0 と置いて、一気に

x^11=89*x^10 + 4895*x^9 - 83215*x^8 - 582505*x^7 + 1514513*x^6
               + 1514513*x^5 - 582505*x^4 - 83215*x^3 + 4895*x^2 + 89*x - 1

の表示が入手でき、これを元に組み立てられる。


 GAI さんからのコメントです。(令和4年8月5日付け)

 x^n を x^2-x-1 で割った商と余りにはフィボナッチ数が密接に関わってくる。

x^2 = (x^2 - x - 1)*(1) + (x + 1)
x^3 = (x^2 - x - 1)*(x + 1) + (2*x + 1)
x^4 = (x^2 - x - 1)*(x^2 + x + 2) + (3*x + 2)
x^5 = (x^2 - x - 1)*(x^3 + x^2 + 2*x + 3) + (5*x + 3)
x^6 = (x^2 - x - 1)*(x^4 + x^3 + 2*x^2 + 3*x + 5) + (8*x + 5)
x^7 = (x^2 - x - 1)*(x^5 + x^4 + 2*x^3 + 3*x^2 + 5*x + 8) + (13*x + 8)
x^8 = (x^2 - x - 1)*(x^6 + x^5 + 2*x^4 + 3*x^3 + 5*x^2 + 8*x + 13) + (21*x + 13)
x^9 = (x^2 - x - 1)*(x^7 + x^6 + 2*x^5 + 3*x^4 + 5*x^3 + 8*x^2 + 13*x + 21) + (34*x + 21)
x^10 = (x^2 - x - 1)*(x^8 + x^7 + 2*x^6 + 3*x^5 + 5*x^4 + 8*x^3
                                 + 13*x^2 + 21*x + 34) + (55*x + 34)
x^11 = (x^2 - x - 1)*(x^9 + x^8 + 2*x^7 + 3*x^6 + 5*x^5 + 8*x^4
                            + 13*x^3 + 21*x^2 + 34*x + 55) + (89*x + 55)
x^12 = (x^2 - x - 1)*(x^10 + x^9 + 2*x^8 + 3*x^7 + 5*x^6 + 8*x^5
                     + 13*x^4 + 21*x^3 + 34*x^2 + 55*x + 89) + (144*x + 89)
x^13 = (x^2 - x - 1)*(x^11 + x^10 + 2*x^9 + 3*x^8 + 5*x^7 + 8*x^6
              + 13*x^5 + 21*x^4 + 34*x^3 + 55*x^2 + 89*x + 144) + (233*x + 144)
x^14 = (x^2 - x - 1)*(x^12 + x^11 + 2*x^10 + 3*x^9 + 5*x^8 + 8*x^7
       + 13*x^6 + 21*x^5 + 34*x^4 + 55*x^3 + 89*x^2 + 144*x + 233) + (377*x + 233)
x^15 = (x^2 - x - 1)*(x^13 + x^12 + 2*x^11 + 3*x^10 + 5*x^9 + 8*x^8 + 13*x^7
       + 21*x^6 + 34*x^5 + 55*x^4 + 89*x^3 + 144*x^2 + 233*x + 377) + (610*x + 377)
    ・・・・・・・・・・・・・・・・・・



  以下、工事中!



(付記) 当ページは、NICER(教育情報ナショナルセンター(国立教育政策研究所))に、
     平成16年10月22日付けで登録されました。当HPは、NICERの趣旨に賛同し、
     参画しております。

(追記) 国の事業仕分けにより、「教育情報ナショナルセンター」は平成23年4月以降運
    用終了とされ、公益財団法人学習ソフトウェア情報研究センターに移管された模
    様です。検索機能が追加され、使い勝手は向上したかもしれません。
     その中に、「フィボナッチ数を極める」が登録されているのを確認しました。登録番
    号は「719」です。(平成23年5月29日付け)