数列と漸化式とは？

数列と漸化式の意味

項が規則的に並ぶ列と、前の項から次の項を定める式。等差・等比のほか、フィボナッチのように直前2項で決まるものもある。応用情報では、ループ回数の見積り、再帰処理の計算量、複利計算の基礎として使う。

数列と漸化式の具体例

等比数列の和の公式は、複利の元利合計や、リトライ間隔を倍にする指数バックオフの総待ち時間の計算に使える。再帰の漸化式 T(n)＝2T(n/2)+n を解くと O(n log n) となり、マージソートに一致する。

数列と漸化式は試験でどう引っ掛けられる？

等差と等比の取り違えのほか、和の項数の数え間違いが多い（初項a・末項l・項数nの和は n(a+l)/2）。指数的に増える漸化式はnが少し増えるだけで爆発するため、線形の感覚で見積もると外す。

数列と漸化式と関連する用語

• 対数と指数の応用
• 再帰と末尾再帰
• 計算量（オーダー記法）

数列と漸化式が出た過去問

• 次の数式は，ある細菌の第n世代の個数f(n)が1世代後にどのように変化するかを表現したものである。この漸化式の解釈として，1世代後の細菌の個数が，第n世代と比較…

  正解：1世代後の個数は，第n世代の個数の1.8倍に増える。

  要点：漸化式は移項して1世代あたりの倍率の形に直して読む

  与式を整理するとf(n+1) = 2×f(n) − 0.2×f(n) = 1.8×f(n)となる。すなわち1世代後の個数は第n世代の1.8倍である。左辺にあった0.2×f(n)を右辺へ移項する点がポイントで、増殖分から一定割合が差し引かれる形になっている。

  出典：平成29年度 春期 応用情報技術者試験 午前 問5（IPA）

• 非線形方程式f(x)=0の近似解法であり、次の手順によって解を求めるものはどれか。ここで、y=f(x)には接線が存在するものとし、(3)でx0と新たなx0の差の…

  正解：ニュートン法

  要点：接線とx軸の交点を繰り返し取る根の求解法がニュートン法

  接線を引いてそのx軸との交点を次の近似値にする、という反復を繰り返す非線形方程式の解法はニュートン法（ニュートン・ラフソン法）である。漸化式は x1 = x0 - f(x0)/f'(x0) で表され、まさに接線とx軸の交点を求める式になっている。収束が速い（2次収束）一方、初期値が解から遠いと発散することがある。

  出典：令和3年度 秋期 応用情報技術者試験 午前 問1（IPA）