ゆめさくエンジニア研究所女性向けエンジニアスクール女性向けエンジニアスクール
ログイン

漸化式とシグマ

回 1-2　分野 1 数と式

漸化式は、数列の項を、その前の項から決める式です。ハノイの塔の手数は、1 枚増えるごとに「前の手数の 2 倍と 1」になるので a(n) = 2a(n−1) + 1、a(1) = 1 と書け、解くと a(n) = 2^n − 1 です。a(10) は 1023 です。プログラムでは、漸化式はループや再帰の 1 歩そのもので、Σ (シグマ) はループで足し合わせた合計を表す記号です。

目安 45 分1-2 (1-1〜1-3 の中)

読み終えたら二重ループの回数の合計を Σ で書ける

この頁の流れ

  1. 164 枚のハノイの塔は、何手で動かせるのか
  2. 2数列、一般項、Σ とは
  3. 3漸化式の型と解き方
  4. 4動かして確かめる
  5. 5漸化式とループはどこでずれるか
  6. 6仕事とコンテストでどう使うか
  7. 7よくある問い
  8. 8確認クイズ
  9. 9説明課題
  10. 10もっと深く
  11. 11一次資料
  12. 12次へ

Σ と漸化式を、ループの回数と再帰の呼び出しの数で数えて、式と同じ数になるかを確かめます。

文 ゆめさくコード編集部公開 2026年10月30日更新 2026年10月30日出典を確かめた日 2026年10月30日

64 枚のハノイの塔は、何手で動かせるのか

ハノイの塔は、大きさの違う円盤を、小さい物の上に大きい物を載せない決まりで、別の柱へ 1 枚ずつ移すパズルです。円盤が 1 枚なら 1 手、2 枚なら 3 手、3 枚なら 7 手かかります。

n 枚を動かすには、上の n−1 枚をよけて、一番下を 1 手で移し、よけた n−1 枚を上に戻します。ですから手数は「n−1 枚の手数の 2 倍と 1」です。この「前の数から次の数を決める式」が漸化式 (ぜんかしき) です。

a(n) = 2a(n−1) + 1、a(1) = 1 を解くと、a(n) = 2^n − 1 になります。64 枚なら 2^64 − 1 = 18446744073709551615 手です。1 秒に 1 手でも、5800 億年あまりかかります。

プログラムでは、漸化式はループや再帰の 1 歩そのものです。この回では、Σ (シグマ) の読み方と和の公式をそろえてから、漸化式の型ごとの解き方を、ループで数えた数と照らして確かめます。

数列、一般項、Σ とは

言葉を 5 つそろえます。

言葉意味例
数列数を順に並べた物1, 3, 7, 15, 31
項数列の 1 つ 1 つの数。n 番目を a(n) と書くa(3) = 7
一般項a(n) を n だけの式で書いた物a(n) = 2^n − 1
漸化式a(n) を前の項から決める式a(n) = 2a(n−1) + 1
Σ (シグマ)決まった範囲の項を全部足す記号Σ k (k = 1〜n)

漸化式だけでは数列は決まりません。最初の項 (初項) が要ります。a(1) = 1 と a(1) = 2 では、同じ式でも違う数列になります。

Σ の読み方

Σ k (k = 1〜n) は、「k を 1 から n まで 1 ずつ変えて、全部足す」と読みます。教科書では、k = 1 を Σ の下に、n を上に書きます。Python で書くと、次の 1 行と同じ意味です。

sum(k for k in range(1, n + 1))

Σ の後ろの式は k を使う式なら何でもよく、Σ k² (k = 1〜n) なら 1² + 2² + … + n² です。

よく使う和の公式

和公式n = 10 の値
Σ c (k = 1〜n)、c は定数c × nc が 3 なら 30
Σ k (k = 1〜n)n(n + 1) / 255
Σ k² (k = 1〜n)n(n + 1)(2n + 1) / 6385
Σ k³ (k = 1〜n)(n(n + 1) / 2)²3025
Σ r^k (k = 0〜n−1)、r ≠ 1(r^n − 1) / (r − 1)r が 2 なら 1023

1 から n までの和は、1 + n、2 + (n−1) と、前と後ろから組を作ると、どの組も n + 1 になり、組が n / 2 個できるので n(n + 1) / 2 です。Σ は足し算なので、Σ (2k + 3) = 2 Σ k + Σ 3 のように、分けて足せます。

漸化式の型と解き方

教科書に出る漸化式は、形でいくつかの型に分けられます。型が分かれば、解き方も決まります。

型形解き方例の一般項
等差a(n+1) = a(n) + d毎回 d 足すa(1) = 2、d = 3 なら 3n − 1
等比a(n+1) = r a(n)毎回 r 倍a(1) = 3、r = 2 なら 3 × 2^(n−1)
階差a(n+1) = a(n) + f(n)f を Σ で足すa(1) = 1、f(n) = n なら n(n − 1)/2 + 1
1 次 (特性方程式)a(n+1) = p a(n) + q動かない数 α を引くと等比ハノイの塔なら 2^n − 1
指数を含むa(n+1) = p a(n) + q^(n+1)両辺を q^(n+1) で割ると上の型a(1) = 2、p = 3、q = 2 なら 2 × 3^n − 2^(n+1)
n の式を足すa(n+1) = p a(n) + f(n)f と同じ形の式を引いて 1 次の型にするa(1) = 1、p = 2、f(n) = n なら 3 × 2^(n−1) − n − 1
係数に na(n+1) = (n+1) a(n)掛ける数を全部掛ける (階比)a(1) = 1 なら n!
対数を取るa(n+1) = a(n)²log を取ると等比a(1) = 2 なら 2^(2^(n−1))
3 項間a(n+2) = a(n+1) + a(n)x² = x + 1 の 2 つの解の式フィボナッチ数
3 項間 (重解)a(n+2) = 4a(n+1) − 4a(n)x² = 4x − 4 の解が 2 だけなので (A + Bn) 2^na(1) = 2、a(2) = 8 なら n × 2^n
和を含むS(n) = (n の式)a(n) = S(n) − S(n−1)、n が 2 以上S(n) = n² なら 2n − 1
分数a(n+1) = a(n) / (a(n) + 1)逆数を取ると等差a(1) = 1 なら 1/n
連立a と b が互いの前の項で決まる足したり引いたりして 1 つの型にする下の例

どの型か見分けるときは、次の順に見ます。

  1. 前の項だけで決まるか、2 つ前まで使うか (使うなら 3 項間)
  2. S(n) が出てくるか (出てくるなら和を含む型)
  3. a(n) が分母にあるか (あるなら分数の型、逆数を取る)。a(n) の累乗だけで書けるか (書けるなら対数を取る。a(n)² + 1 のように数を足す形には使えない)
  4. a(n) の前に掛かる数が 1 か (1 なら等差か階差、1 でなければ等比か 1 次。n を含むなら階比)
  5. 足す数に n の式や累乗があるか (あるなら引いたり割ったりして 1 次の型に直す)

1 次の型と特性方程式

a(n+1) = p a(n) + q (p ≠ 1) の型は、a(n) が α のとき次も α のままになる数 α を探します。α = p α + q を解くと α = q / (1 − p) です。この式を特性方程式と呼びます。

元の式から α = p α + q を引くと、a(n+1) − α = p (a(n) − α) になります。b(n) = a(n) − α と置けば、b(n) は毎回 p 倍される等比数列です。

ハノイの塔の a(n+1) = 2a(n) + 1 なら、α = 2α + 1 から α = −1 です。b(n) = a(n) + 1 は、b(1) = 2 で毎回 2 倍なので b(n) = 2^n です。よって a(n) = 2^n − 1 です。

階差の型と Σ

a(n+1) = a(n) + f(n) なら、a(n) は a(1) に f(1) から f(n−1) までを足した数です。

a(n) = a(1) + Σ f(k) (k = 1〜n−1)、n が 2 以上

Σ の上が n ではなく n−1 なのは、a(1) から a(n) までの間の段の数が n−1 だからです。n = 1 のときは Σ が空 (足す物が無い) で 0 とし、a(1) のままです。f(n) = n なら、a(n) = 1 + (n − 1)n / 2 です。

3 項間の型とフィボナッチ数

a(n+2) = a(n+1) + a(n)、a(0) = 0、a(1) = 1 がフィボナッチ数です。x² = x + 1 の解 φ = (1 + √5) / 2 と ψ = (1 − √5) / 2 を使い、a(n) = (φ^n − ψ^n) / √5 と書けます。ψ^n は n が大きくなると 0 に近づくので、a(n) は φ^n / √5 を四捨五入した整数です。

一般に a(n+2) = p a(n+1) + q a(n) の型は、x² = px + q の 2 つの解 α と β を使い、α と β が違えば a(n) = A α^n + B β^n、解が 1 つだけ (重解) なら a(n) = (A + Bn) α^n の形になります。A と B は、最初の 2 項から決めます。

連立の型

a(n+1) = a(n) + 2b(n)、b(n+1) = 2a(n) + b(n)、a(1) = 1、b(1) = 0 の組を考えます。2 つを足すと a(n+1) + b(n+1) = 3(a(n) + b(n))、引くと a(n+1) − b(n+1) = −(a(n) − b(n)) です。足した方は公比 3、引いた方は公比 −1 の等比数列なので、a(n) = (3^(n−1) + (−1)^(n−1)) / 2 と出ます。

動かして確かめる

1 本目は、二重ループの内側が何回動くかを数え、Σ の公式と照らします。内側は i 回動くので、合計は Σ i (i = 0〜n−1) = n(n − 1)/2 です。

動かす 二重ループの回数を Σ と照らす

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

1 0 0
2 1 1
10 45 45
100 4950 4950
1000 499500 499500

どの n でもループで数えた数と公式が同じです。n = 1 のときは内側が 1 回も動かず 0 で、公式の 1 × 0 / 2 = 0 とも合います。1000 件の総当たりの組は 499500 組で、n² のおよそ半分です。

2 本目は、ハノイの塔を再帰で解き、実際に動かした手数を数えます。

動かす ハノイの塔の手数を数える

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

1 1 1
2 3 3
3 7 7
4 15 15
5 31 31
6 63 63
7 127 127
8 255 255
9 511 511
10 1023 1023
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

数えた手数と 2^n − 1 が、10 枚まで全部同じです。a(10) = 1023 で、漸化式 a(n) = 2a(n−1) + 1、a(1) = 1 の 10 番目の項と一致します。3 枚の 7 手も並べました。

3 本目は、上の型の表のうち 6 つの型の一般項が正しいかを、漸化式をそのまま 1 歩ずつ回した数と、n = 1 から 12 まで照らします。

動かす 型の表の一般項をループと照らす

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

等差 [2, 5, 8, 11, 14] True
等比 [3, 6, 12, 24, 48] True
階差 [1, 2, 4, 7, 11] True
1次 [1, 3, 7, 15, 31] True
指数 [2, 10, 38, 130, 422] True
分数 1 1/2 1/3 True

6 つの型とも、12 項目まで一般項がループの数と一致しました (True)。分数の型は、小数の誤差が入らないよう Fraction (分数をそのまま持つ型) で計算しています。

4 本目は、和を含む型と連立の型です。和を含む型は、n = 1 だけ別に扱う所が境目です。

動かす 和を含む型と連立の型

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

a [2, 3, 5, 7, 9, 11]
和 37 37
1 1 1
2 1 1
3 5 5
4 13 13
5 41 41
6 121 121
7 365 365

S(n) = n² + 1 のとき、n が 2 以上の項は 2n − 1 ですが、a(1) は S(1) = 2 で、2 × 1 − 1 = 1 とは違います。a(1) を S(1) から別に出さないと、和が 1 つずれます。連立の型は、7 項まで式と同じ数が出ました。

5 本目は、フィボナッチ数を 3 つの書き方で出し、手間を比べます。

動かす フィボナッチ数を 3 通りで出す

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

75025 呼出 242785
75025 75025
70 190392490709135
  190392490709135
71 308061521170129
  308061521170130

素直な再帰は、F25 = 75025 を出すのに (出力の「呼出」は呼び出しの回数) 242785 回も自分を呼びます。同じ値を何度も計算し直すからです。一度出した値を覚えておく (メモ化) か、ループで前の 2 つだけ持てば、25 回ほどで済みます。これが動的計画法の考え方です。

一般項の φ^n / √5 は、71 番目で小数の誤差が出て、1 つずれました。一般項があっても、大きな n では整数のループの方が正確です。

漸化式とループはどこでずれるか

番号を 0 から数えるか 1 から数えるか

数学の数列は a(1) から、Python のリストは 0 番から数えることが多いです。フィボナッチ数も、F0 = 0 から数える本と、F1 = 1 から数える本があります。式とコードの番号が 1 つずれていないかを、最初の 3 項を手で書き出して確かめます。

初項と n = 1 の境目

漸化式は、初項が違うと全部の項が変わります。和を含む型の a(n) = S(n) − S(n−1) は、n が 2 以上でしか使えません。階差の型の Σ も、上が n−1 です。n = 1 のときにも式が合うかを、別に確かめます。

再帰の深さ

漸化式をそのまま再帰で書くと、a(5000) を求めるには 5000 段の呼び出しが要ります。Python の再帰の深さの上限は、既定で 1000 前後です (sys.getrecursionlimit() で見られます)。深い漸化式はループで書きます。

小数で計算する

一般項に √5 や割り算があると、小数の誤差が出ます。5 本目のように、整数で答えが出る数列は、整数のままループで計算するか、Fraction を使います。

仕事とコンテストでどう使うか

Σ と漸化式が出てくる場面は、次の通りです。

  • ループの回数の見積もり。二重ループで内側が i 回なら、合計は Σ i で約 n² / 2。1 万件の総当たりは約 5000 万回
  • 再帰の計算量。マージソートの手間 T(n) = 2T(n/2) + n のように、再帰の手間は漸化式で書け、解くと n log n の形になる
  • 動的計画法。「i 段目までの最小の手間」を「i−1 段目と i−2 段目の答え」から出す式は、漸化式そのもの。競技プログラミングの DP の問題は、漸化式を立てる所が本題
  • お金と残高。毎月 1% 増えて 1 万円返す残高は a(n+1) = 1.01 a(n) − 10000 で、1 次の型
  • ほかの分野。ウサギの数の増え方 (フィボナッチ数)、音声や画像の信号処理の差分方程式、経済の成長の式など、時間で 1 歩ずつ進む物の多くは漸化式で書ける

よくある問い

漸化式とは、ひと言で何ですか

数列の項を、その前の項から決める式です。「次の数は、今の数の 2 倍と 1」のように、1 歩ずつの決まりを書いた物で、初項と合わせて数列が 1 つに決まります。プログラムでは、ループの中の 1 行や、再帰の式に当たります。

一般項を求めると何が嬉しいのですか

n 番目を 1 回の計算で出せます。漸化式のままだと、a(1000000) を出すには 100 万回ループします。一般項 2^n − 1 があれば 1 回です。ただし、5 本目のように小数が入る一般項は大きな n で誤差が出るので、整数で計算できる式かを見ます。

特性方程式は、なぜ使えるのですか

特性方程式の解 α は、a(n) が α なら次も α のまま動かない数です。a(n) から α を引くと、足す数 q が消えて、ただの等比数列になります。特性方程式は、その α を探す計算です。答案に書く式ではなく、α を見つけるための下書きです。

Σ の上と下には何を書きますか

下に変える文字と始まりの値 (k = 1)、上に終わりの値 (n) を書きます。Python の range(1, n + 1) と同じ範囲です。range の終わりは含まないので、n まで足すときは n + 1 と書く所が、ずれやすい所です。

確認クイズ

答えだと思う選択肢を押すと、その場で正誤と理由が開きます。3 問すべてに正しく答えると、この回は修了で、石が緑に変わります (この端末のブラウザに残ります)。間違えた問いは、あとから解き直せます。

1 問目

a(1) = 1、a(n) = 2a(n−1) + 1 (n が 2 以上) のとき、a(10) はいくつですか。

2 問目

次のループで、c += 1 は全部で何回動きますか。n は 100 です。

c = 0
for i in range(100):
    for j in range(i, 100):
        c += 1

3 問目

S(n) = n² + 1 を初項から n 項までの和とする数列 a(n) について、正しいのはどれですか。

説明課題

「ハノイの塔の手数が a(n) = 2a(n−1) + 1 になる理由」を、円盤の動かし方から 3 文で説明してください。書いたら、下の模範解答を開いて比べてください。

模範解答

自分の説明を書いてから開いて、比べてください。

この回の先の一歩

ループの回数を Σ で、再帰の手間を漸化式で書けると、遅い処理がどこで増えるかを式で言えます。いまの自分が転職までの道のどの段にいるかは、転職診断で確かめられます。

もっと深く

この回の続きを、ゆめさくのコースの章や道具で深められます。頁の中の確認クイズに答えたあと、手を動かす量を増やしたいときに使ってください。

一次資料

どれも 2026年10月30日に開いて、題と中身を確かめました。

次へ

前の回 1-1数の表し方2 進数と 16 進数、桁の重み次の回 1-3集合と必要十分かつ、または、でない、ド・モルガン

分野 1 数と式の回

  1. 1-1数の表し方2 進数と 16 進数、桁の重み頁で読む
  2. 1-2シグマと漸化式Σ の読み方、和の公式、漸化式とループこの回
  3. 1-3集合と必要十分かつ、または、でない、ド・モルガン頁で読む

分野 1 の頁へ戻るほかの分野を見る