1.問題

　　　15段の階段があります。階段を一段づつ上ってもOK、一段飛ばしで上ってもOKとして、
　　　この階段の上り方が何通りあるか答えなさい。 　　



2.解説

      まず少ない階段から具体的に計算して、法則を推測してみましょう。
　　　Ｆ(ｎ)：ｎ段の階段の上り方

　　　１．階段が1段の場合
　　　　　Ｆ(1)＝1　　
             
      ２．階段が２段の場合
　　　　　Ｆ(2)＝2　　        
                                                 
      ３．階段が３段の場合
　　　　　�@．最初に1段上る場合
　　　　　　　残り2段を上る方法はＦ(2)となる。

　　　　　�A．最初に２段上る場合
　　　　　　　残り１段を上る方法はＦ(1)となる。
　　　　　従って、Ｆ(3)＝Ｆ(1)＋Ｆ(2)＝３

　　　４．階段がｎ段の場合
　　　　　�@．最初に1段上る場合
　　　　　　　残りn-1段を上る方法はＦ(n-1)となる。

　　　　　�A．最初に２段上る場合
　　　　　　　残りn-2段を上る方法はＦ(n-2)となる。
　　　　　従って、Ｆ(ｎ)＝Ｆ(n-1)＋Ｆ(n-2)　                                            

     さて、ここまで計算してF(n)はフィボナッチ数を表していることに気が付いたと思います。
     実際に計算して見ましょう。
　　F(15)=987なので、従って問題の答えは、９８７通りとなります。
　
     F(1)=1
     F(2)=2
     F(3)=3
     F(4)=5
     F(5)=8
     F(6)=13
     F(7)=21
     F(8)=34
     F(9)=55
     F(10)=89
     F(11)=144
     F(12)=233
     F(13)=377
     F(14)=610
     F(15)=987
     


　　一般に、フィボナッチ数はF(1)=1,F(2)=1,F(3)=2,F(4)=3,F(5)=5,F(6)=8,....と定義されているので
　　今回の階段数列の場合は、番号が１つずれています。　
　　フィボナッチ数はビネの公式で計算する事ができます。
　　
    ビネの公式

　　　　　　F(n)=1/sqrt(5)*(((1+sqrt(5))/2)^n-((1-sqrt(5))/2)^n)

   ビネの公式でで計算すると、F(16)=987となります。

　1/sqrt(5)≒0.4472135956,  1/2+1/2*sqrt(5)≒1.618033989,  1/2-1/2*sqrt(5)≒-0.6180339890

　F(n)は整数になることが分かっているので、近似計算して整数にすればF(n)が求められる。

　すなわち、F(n)≒0.4472135956*1.618033989^n（近似計算用公式）

  F(16)を近似計算するとF(16)≒987.0002051となる。

　次に、フィボナッチ数の数論的性質を調べてみましょう。

3.フィボナッチ数の数論的性質

  １００以下のフィボナッチ数を計算してみました。
　F(n)の横にあるＰは、F(n)が素数である事を表しています。

       n     F(n)    n       F(n)         n        F(n)            n       F(n)

　　　 1     1       26      121393       51      20365011074      76      3416454622906707
       2     1       27      196418       52      32951280099      77      5527939700884757
       3     2 p     28      317811       53      53316291173      78      8944394323791464
       4     3 p     29      514229 p     54      86267571272      79     14472334024676221
       5     5 p     30      832040       55     139583862445      80     23416728348467685
       6     8       31     1346269       56     225851433717      81     37889062373143906
       7    13 p     32     2178309       57     365435296162      82     61305790721611591
       8    21       33     3524578       58     591286729879      83     99194853094755497p
       9    34       34     5702887       59     956722026041      84    160500643816367088
      10    55       35     9227465       60    1548008755920      85    259695496911122585
      11    89 p     36    14930352       61    2504730781961      86    420196140727489673
      12   144       37    24157817       62    4052739537881      87    679891637638612258
      13   233 p     38    39088169       63    6557470319842      88   1100087778366101931
      14   377       39    63245986       64   10610209857723      89   1779979416004714189
      15   610       40   102334155       65   17167680177565      90   2880067194370816120
      16   987       41   165580141       66   27777890035288      91   4660046610375530309
      17  1597 p     42   267914296       67   44945570212853      92   7540113804746346429
      18  2584       43   433494437 p     68   72723460248141      93  12200160415121876738
      19  4181       44   701408733       69  117669030460994      94  19740274219868223167
      20  6765       45  1134903170       70  190392490709135      95  31940434634990099905
      21 10946       46  1836311903       71  308061521170129      96  51680708854858323072
      22 17711       47  2971215073 p     72  498454011879264      97  83621143489848422977
      23 28657 p     48  4807526976       73  806515533049393      98 135301852344706746049
      24 46368       49  7778742049       74 1304969544928657      99 218922995834555169026
      25 75025       50 12586269025       75 2111485077978050     100 354224848179261915075

     
　　　数論的性質
     
     (1). F(n*m)=0 mod F(n)

          式の解釈は、kがnの倍数である時、F(k)は、F(n)の倍数となる。
　　　　　例えば、F(14)=0 mod F(7),F(21)=0 mod F(7),F(28)=0 mod F(7)となっている。

     (2). F(p-1)=0 mod p 　但し、pは素数で　p=1 mod 5, p=-1 mod 5　とする。

　　　　　全ての素数pについてF(p-1)はpの倍数となる。
　　　　　例えば、F(10)=0 mod 11, F(28)=0 mod 29

     (3). F(p+1)=0 mod p 　但し、pは素数で　p=2 mod 5, p=-2 mod 5　とする。
          例えば、F(18)=0 mod 17, F(14)=0 mod 13

     (4). F(p)が素数になるためには、pは素数でなければならない。

　　　　　しかし、pは素数であってもF(p)が素数になるとはかぎらない！
　　　　　F(11),F(13),F(17)は素数でもF(19)は素数ではない。
          フィボナッチ数列の中に、素数が無限に現れるかどうかは、証明されていないようです。