コマネチ大学 : PamGau

見逃しちまいました。残念。

問題:

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

上記「階段の登り方の場合の数を問う問題」は、参考書なんかにそのまま三項漸化式に関する章の"Hello, World"として使われる頻出例題でした。だから、それを思い出せるかどうかという知識問題になってしまいます。特にオッサンの場合…。

この問題はついでにフィボナッチ数列にも言及できるので数学教師にとっては便利なんですね。赤チャートにもそのまま載っていたように記憶しているので、たけしが出来て、現役の学生が出来ないことに時の流れを感じます。

たけしの世代の大学入試数学の花形分野は、戦前からの流れを汲んでやっぱり「漸化式」。出題されつくしたおかげでその下の私らオッサンらの世代以降ではあらかたの形式の漸化式の一般解法は周知されることになりました。

まあ、一般解法を知っていたからといってただ漸化式を解くだけの問題が出題されることは少ないし、証明なしに下記に示す「特性方程式」なんかを使うと減点必至なのは今と変わらない状況でしょう。ただ、知っていれば、アレンジした出題に出会ったときでも見通しが付くという利点はありました。

この際だから、紙の上で手を動かしてみました。

n段の階段の登り方の場合の数を、p_nとすると、題意は下記(1a),(1b)で表される三項漸化式で表すことができます。

p₁ = 1, p₂ = 2 … (1a)

p_n=p_n-1 + p_n-2 (n > 2)… (1b)

上記三項漸化式の特性方程式は(2)の通り。

x² - x - 1 = 0 … (2)

よって、(2)の実数解と初期条件(1a)に基づいて、p_nの一般解は(3)のように求まります。

p_n = (1/10)(5 - √5){(1/2)(1 - √5)}ⁿ + (1/10)(5 + √5){(1/2)(1 + √5)}ⁿ … (3)

フィボナッチ数列は整数解なのに、一般式に表すと無理数が出てくるところが、オイラーの公式の美しさにも通じて粋です。

参考資料

漸化式と特性方程式に関する考察

回答フォーム

漸化式だからと効率の悪い再帰を使うと30を超えたあたりでスタックーオーバーフローします。いや、しますってば…(笑)。

<script type=text/javascript><!--

function fibo(n){

  if(n < 1 || n > 99){ return "undef";}

  if(n < 3){ return n;}

  var retval;

  var val1 = 1;

  var val2 = 2;

  for(;n>2;n--){

    retval = val1 + val2;

    val1 = val2;

    val2 = retval;

  }

  return retval;

}

//--></script>

<form name="fiboform" >

<label for="fiboval">段数：</label>

<input type="text" name="fiboval" value="" />

<input type="button" value="submit"

onclick="fiboform.answer.value = fibo(fiboform.fiboval.value)"/><br />

<label for="answer">回答：</label>

<input type="text" name="answer" value="" />

</form>