数列と漸化式（フィボナッチと再帰）

Q: 数列と漸化式（フィボナッチと再帰）とは何ですか？

数列とは数を一列に並べたものであり、第 n 項を a_n と書く。項と項の関係を方程式で表したものを「漸化式（Recurrence Relation）」と呼ぶ。 - 等差数列: a_{n+1} = a_n + d（一般項 a_n = a_1 + (n-1)d） - 等比数列: a_{n+1} = r a_n（一般項 a_n = a_1 r^{n-1}） - フィボナッチ数列: a_{n+2} = a_{n+1} + a_n \quad (a_1 = 1, a_2 = 1)

Q: 数列と漸化式（フィボナッチと再帰）は社会やプログラミングでどのように使われていますか？

動的計画法（DP: メモ化再帰）によるフィボナッチ数列の超高速計算: 素朴な再帰関数でフィボナッチ数列を計算すると計算量は O(2^n)（指数時間）となり、n=50 でも天文学的な計算時間を要してフリーズする。漸化式の性質を利用し、過去の項をテーブルに保存（メモ化 / DP）することで計算量を O(n) の線形時間に劇的に短縮できる。

過去の状態から次の状態を紡ぎ出すルール。再帰・動的計画法（DP）と複利の数理

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: 数列は一定の規則で並んだ数の列であり、漸化式は「前の項から次の項をどう作るか」という関係式
2: 等比数列の和の公式は金融・資産運用の「複利計算（つみたて投資）」の基礎原理そのもの
3: プログラムにおける再帰関数（Recursion）や動的計画法（DP: Dynamic Programming）は漸化式の直接の実装である

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

過去の状態や直前の結果から、未来の数値を段階的に予測・計算する規則を体系化するために生まれた。

身につく武器・思考力

プログラミングの根幹である「再帰（Recursion）」や「動的計画法（DP）」を直感的に操り、複雑な問題を小さな漸化式に分割して解く思考力が身につく。

実社会・ITでの活躍現場

•資産運用のつみたて投資・年金・住宅ローンの複利計算
•アルゴリズムの動的計画法（フィボナッチ、最長共通部分列）
•自然界の植物の葉の並びやオウムガイの螺旋（黄金比）
•コンピュータのメモリ割り当てやパケット伝送のキュー制御

Layer 1 — 直感・シミュレーター

数列のタイプ（等差数列・等比数列・フィボナッチ数列）を切り替え、パラメータを動かしてみよう。各ステップの数値の推移がグラフで可視化され、特に等比数列での「複利効果（雪だるま式増加）」やフィボナッチ数列の比率が黄金比（約1.618）に収束していく様子を観察できる。

初項 a₁:2

公差 d (毎回の増分):+3

数列の第 1 項〜第 8 項の並び:総和 S_8 = 100

n = 12

n = 25

n = 38

n = 411

n = 514

n = 617

n = 720

n = 823

値の推移グラフ:

a_1

a_2

a_3

a_4

a_5

a_6

a_7

a_8

直感チェック！ミニクイズ

初項 1、漸化式 a_{n+1} = a_n + 3 で定まる等差数列の第 10 項 a_{10} はいくつか？

Layer 2 — 定義・受験・証明

定義

数列とは数を一列に並べたものであり、第 $n$ 項を $a_n$ と書く。項と項の関係を方程式で表したものを「漸化式（Recurrence Relation）」と呼ぶ。 - 等差数列: $a_{n+1} = a_n + d$ （一般項 $a_n = a_1 + (n-1)d$ ） - 等比数列: $a_{n+1} = r a_n$ （一般項 $a_n = a_1 r^{n-1}$ ） - フィボナッチ数列: $a_{n+2} = a_{n+1} + a_n \quad (a_1 = 1, a_2 = 1)$

公式・数理モデル

a_n = a_1 + (n-1)d, \quad a_n = a_1 r^{n-1}, \quad a_{n+2} = a_{n+1} + a_n

証明・導出

等比数列の和の公式の導出：初項 $a$ 、公比 $r \neq 1$ 、項数 $n$ の等比数列の和 $S_n = a + ar + ar^2 + \cdots + ar^{n-1}$ に対し、両辺に公比 $r$ を掛けると、

r S_n = ar + ar^2 + ar^3 + \cdots + ar^n

上の式から下の式を引くと、中間の項がすべて打ち消し合って最初と最後だけが残る：

(1 - r)S_n = a - ar^n = a(1 - r^n)

$r \neq 1$ であるため両辺を $1 - r$ で割ると、

S_n = \frac{a(1 - r^n)}{1 - r} = \frac{a(r^n - 1)}{r - 1}

この和の公式は、毎月一定額を複利で積み立てた場合の将来価値を計算する金融工学の根幹である。

押さえておきたいポイント

漸化式は「初期値（ベースケース）」と「遷移規則（ステップ）」の2つが揃うことで全項が一意に定まる
プログラミングの「再帰（Recursion）」は漸化式の数学的表現そのものである
フィボナッチ数列の隣接2項の比 $\lim_{n \to \infty} \dfrac{a_{n+1}}{a_n} = \dfrac{1 + \sqrt{5}}{2} \approx 1.618$ は「黄金比（Golden Ratio）」に収束する
動的計画法（DP）は、過去の漸化式の計算結果をキャッシュ（メモ化）して再計算を省く最適化技法である

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

動的計画法（DP: メモ化再帰）によるフィボナッチ数列の超高速計算

素朴な再帰関数でフィボナッチ数列を計算すると計算量は $O(2^n)$ （指数時間）となり、 $n=50$ でも天文学的な計算時間を要してフリーズする。漸化式の性質を利用し、過去の項をテーブルに保存（メモ化 / DP）することで計算量を $O(n)$ の線形時間に劇的に短縮できる。

1// 動的計画法（Bottom-Up DP / ループ）によるフィボナッチ数列の計算: O(n)
2function fibonacciDP(n: number): bigint {
3  if (n <= 0) return 0n;
4  if (n === 1) return 1n;
5
6  // 空間計算量 O(1) に最適化（直前2項のみを保持）
7  let prev2 = 0n; // a_{k-2}
8  let prev1 = 1n; // a_{k-1}
9  let current = 0n; // a_k
10
11  for (let k = 2; k <= n; k++) {
12    current = prev1 + prev2; // a_k = a_{k-1} + a_{k-2}
13    prev2 = prev1;
14    prev1 = current;
15  }
16
17  return current;
18}
19
20// 第 100 項をミリ秒未満で算出（素朴な再帰だと数万年かかる）
21const n = 100;
22const fib100 = fibonacciDP(n);
23console.log(`フィボナッチ第${n}項: ${fib100.toString()}`);
24// 354224848179261915075