フィボナッチ数列

1. フィボナッチ数列

   1. 由来

      フィボナッチは12世紀後半のイタリアの数学者レオナルドのニックネームです。レオナルドはウサギの繁殖に関する問題としてこの数列を紹介しました。
      
      

   2. 定義

      フィボナッチ数列は次にように再帰的に定義されます。
      

      　Ｆib(1)＝Ｆib(2)＝１，
      　Ｆib(n)＝Ｆib(n-1)＋Ｆib(n-2)　　ｎ≧３の時、

      このＦ(n)の計算は、単純な繰り返しでは計算できません（後で計算式を紹介します）。
      
      

   3. プログラム（ANSI)

      再帰処理をするプログラムは簡単です。以下はJava言語で定義をそのままプログラムしています。
      

        long Fib(int N)
        {
          long L;
          //printf("in Fib(%d)\n",N);
          if (N==1 || N==2) return(1);
          else {
            L=Fib(N-1)+Fib(N-2);
           // printf("return Fib(%d)=%ld\n",N,L);
            return(L);
          }
        }

      
      

   4. 計算例

      1. n=4
         n=4の場合の処理の流れを見てみましょう。Fib(4)を計算するにはFib(3)とFib(2)の計算が必要です。このためには Fib(2)　と Fib(1)　が必要ですがこの値は１と定義されています。これで、Fib(3)の値が計算され、return Fib(3)=2　が記録されます。次にFib(2)の値を求め、この二つを合計して、return Fib(4)=3　が記録されます。
         　Fib(4)の計算のため、Fib()の呼び出しが5回起こっています。
         number:4
         in Fib(4)
         in Fib(3)
         in Fib(2)
         in Fib(1)
         return Fib(3)=2
         in Fib(2)
         return Fib(4)=3
         Fib(4)= 3
         
         
      2. n=5
         　同様に、Fib(5)　の計算課程を示します。
         in Fib(5)
         in Fib(4)
         in Fib(3)
         in Fib(2)
         in Fib(1)
         return Fib(3)=2
         in Fib(2)
         return Fib(4)=3
         in Fib(3)
         in Fib(2)
         in Fib(1)
         return Fib(3)=2
         return Fib(5)=5
         Fib(5)= 5
         
         

   5. 一般解

      フィボナッチ数の一般解は次のように計算できます。
      
      F(0)=0,F(1)=1;
      
      
      

   6. 証明

      数学的帰納法で証明します。
      n乗される項を　a,b とします。このとき、a・b=-1、a+b=1、となります。
      これを利用すると、以下のように証明出来ます。
      
      f(k+1) = f(k) + f(k-1)
      　=(a^k-b^k)/√5 + (a^k-1 -b^k-1)/√5
      　=(a^k-b^k)/√5 +(-ba^k + ab^k)/√5 (ab=-1)
      　=((1-b)a^k - (1-a)b^k)/)/√5
      　=(a^k+1 -b^k+1)/√5（a+b=1)）
      
      

2. フィボナッチ数列の実例

   
   

   1. 階段の昇り方

      　n段の階段を1段、または2段で上がる方法はフィボナッチ数になります。n段を上がるには、(n-1)段を上り最後に１段上るか、(n-2)昇り最後に2段を上ることになります。したがって、n段の上がり型は
      　　　Fib(n) = Fib(n-1) ＋ Fib(n-2)
      となります。これを、組み合わせで考えますと、全部1段づつ上る場合（2段とびなし）は1通りで _nC₀、一度だけ2段上がる場合は _n-1C₁、
      2度2段上がりする場合、_n-2C₂となります。
      　したがって、次の関係が成立します。
      　Fib(n)=Σ(p=0,(n-1)/2)_n-pC_p
      　たとえば、F(6) = ₆C₀ + ₅C₁ + ₄C₂ + ₃C₃ です。
      
      

   2. ウサギの繁殖

      ペアのウサギが2ヶ月後から毎月ペアのウサギを産むとする。1年後のウサギの数はいくらか？
      これは、前の世代が生き残り（ Fib(n-1) ）、かつ前の世代からの子供（Fib(n1-)）が増えますから、フィボナッチの数列になります。12ヶ月後には２３３になります。
      
      
      

   3. 黄金比（golden ratio）

      長方形の長さを a,b としたとき、1:1.1618 （約 5:8）がもっとも美しい長さの比といわれます。この比は、
      　a/b = b/(a+b)
      となる b/a の比率でもあり、　x² + x + 1 = 0 を満たし、（１ + √5)/２ =1.618 となります。
      　黄金比は次のように作図できます。正方形 abcd を作り、辺 bc の中点 o を中心に、線分 oa または od を半径とした円を書き、それと辺 bc の延長線との交点を e とすると、 ab : be が黄金比となリます。
      
      
      
      そして、フィボナッチ数列の隣り合う数の比は、nが十分大きいとき(第2項は0に近づくので)、黄金比になります。黄金比は多くの美術品や絵画に現れるそうです。
      　n が大きい時、フィボナッチ数列は fib(n) = （（１ + √5)/２)^n となります。
      
      

3. 演習、アンケート、

   
   

   1. 演習

      
      I（E）の一般解から　n=2,3 の場合で計算してください。
      
      フィボナッチ数を計算するプログラムを作成してください。
      
      

   2. アンケート

      
      黄金分割の名前は聞いたことがありましたか？
      　１　ある　　２聞いたような　　３覚えがない
      
      フィボナッチ数列の多様な例は理解できましたか？
      　１　出来た　　２　だいたい　　３ まだ