1 漸化式の基本
漸化式は、数列の各項をそれ以前の項で表す関係式である。ある項が前の項や複数の先行項に依存して定まるため、離散的な変化や反復的な更新を記述するのに適している。数列そのものを直接与えるのではなく、生成規則を与える点に特徴がある。
1.1 漸化式の定義
漸化式とは、数列の第n項を、少なくとも一つ前の項を含む既知の項から定める式をいう。たとえば、次の項が前の項に一定の規則で依存する形や、過去の複数項をまとめて用いる形が含まれる。連続量を扱う微分方程式に対し、離散的な対象を扱う際の基本的な枠組みとみなされる。
1.2 初期条件
漸化式だけでは数列が一意に決まらないことが多く、最初のいくつかの項を与える初期条件が必要となる。初期条件は、計算の出発点を定める役割を持つ。これにより、漸化式で与えられた規則が具体的な数列として展開される。
1.3 数列との関係
数列は項の並びそのものを指し、漸化式はその並びを作る規則を表す。したがって、漸化式は数列の「生成法」であり、数列はその結果として得られる。一般項がすぐには見えない場合でも、漸化式によって各項を順次求められる。
1.4 漸化式の表現方法
漸化式は、添字を用いた記法、関係式の形、あるいは行列や写像として表されることがある。対象に応じて記法を使い分けることで、構造が見やすくなり、解法も整理しやすい。場合によっては、図式やアルゴリズムの形で更新規則を示すこともある。
2 漸化式の種類
漸化式は、項同士の結びつき方によっていくつかに分類される。線形か非線形か、係数が固定か変化するか、あるいは一つの数列か複数の数列が連動するかによって性質が大きく異なる。分類は、解法を選ぶうえでも重要である。
2.1 線形漸化式
線形漸化式は、未知の項が一次式の形で現れる漸化式である。各項が前の項の線形結合として表され、係数の扱いが比較的明確である。多くの基本的な数列はこの型に属する。
2.1.1 一次線形漸化式
一次線形漸化式は、直前の一項だけに依存する最も単純な形である。等比的な増減や、一定量を加える変化を表しやすい。代表的な例として、毎回一定倍率で増えるモデルや、一定額ずつ変化するモデルがある。
2.1.2 高階線形漸化式
高階線形漸化式では、二つ以上の過去項が用いられる。フィボナッチ数列のように、複数の先行項の組合せで次項が決まる場合が典型である。高階になるほど構造は複雑になるが、規則性の解析には有力である。
2.2 非線形漸化式
非線形漸化式は、未知項が積やべき、分数、その他の非線形な形で現れる漸化式である。振る舞いが直線的に追えないことが多く、解の挙動が多様になりやすい。単純な式でも、反復によって複雑な列を生むことがある。
2.2.1 乗法型漸化式
乗法型漸化式は、次の項が前の項に何らかの係数や別の項を掛けて得られる形である。比率を保った増減や、連鎖的な成長を表現しやすい。指数的な伸びを示す場合も多い。
2.2.2 置換を含む漸化式
置換を含む漸化式では、項の中に他の式を代入する操作が繰り返される。変数の置き換えによって見通しがよくなることがあり、複雑な式を単純な形へ移す手がかりとなる。反復合成の構造を持つ点に特徴がある。
2.3 連立漸化式
連立漸化式は、複数の数列が互いに影響し合いながら同時に定まる形である。一つの系列だけを独立に追うのではなく、複数の状態変数をまとめて扱う。工学や計算機科学で現れる状態遷移の記述に向いている。
2.4 定係数漸化式
定係数漸化式は、各項に掛かる係数が一定である漸化式である。係数が固定されているため、一般的な解法を適用しやすい。理論的にも扱いやすく、多くの標準問題で現れる。
2.5 非定係数漸化式
非定係数漸化式は、係数が項ごとに変化する漸化式である。時間や位置に応じて規則が変わるため、定係数型より柔軟な表現が可能である。一方で、解くには工夫が必要になることが多い。
3 漸化式の解法
漸化式の解法は、与えられた規則から一般項や性質を導くための手順である。型によって有効な方法が異なり、単純な代入から関数的な道具まで幅広い。解を得た後は、必ず元の式と初期条件に照らして確認する。
3.1 代入法
代入法は、漸化式を順に展開し、既知の項を繰り返し置き換えていく方法である。短い階数の式や、特定の規則が見えやすい場合に有効である。直接的で理解しやすいが、長い反復では計算が煩雑になりやすい。
3.2 差分法
差分法は、隣接する項の差に注目して式を変形する方法である。もとの漸化式を差の形に直すことで、和の形にまとめやすくなる。一定差や望ましい消去が現れると、解が簡潔になることがある。
3.3 特性方程式
特性方程式は、定係数線形漸化式を解くための代表的な手法である。指数型の解を仮定して代入すると、漸化式が多項式方程式に帰着する。根の性質によって解の形が決まる。
3.3.1 斉次形の解法
斉次形では、右辺に外部項がなく、同種の項だけで構成される。特性方程式の根を用いて、一般解を根の重複度に応じて組み立てる。基本形を押さえることで、より複雑な式への応用も可能になる。
3.3.2 非斉次形の解法
非斉次形では、外部からの入力や定数項が加わる。まず斉次解を求め、その後に特解を探して組み合わせるのが基本である。右辺の形に応じて、未定係数法などを併用することが多い。
3.4 母関数
母関数は、数列の各項を係数としてもつ形式的な冪級数である。漸化式を関数方程式に変換できるため、項の構造を一括して扱える。組合せ論とも相性がよく、数え上げ問題で特に有力である。
3.5 数学的帰納法による確認
数学的帰納法は、得られた一般式が正しいことを検証するためによく用いられる。初期段階を示し、仮定から次の段階が成り立つことを証明する。解の導出そのものというより、結論の妥当性を支える役割を担う。
3.6 変数変換による簡約
変数変換による簡約は、元の数列を別の変数で置き換えて、式を単純な形に直す方法である。たとえば、増加分や比率を新しい数列として見ることで、扱いが容易になる。適切な変換が見つかると、非線形の問題も線形的に処理できることがある。
4 漸化式の応用
漸化式は、抽象的な数列の道具にとどまらず、現実の反復過程を表す共通言語として用いられる。離散時間で進む現象や、段階的に更新される計算手順の解析に広く関わる。応用の範囲は数学内部に限られない。
4.1 数列の一般項の導出
漸化式の最も基本的な応用は、数列の一般項を求めることである。各項を順に計算する代わりに、nに直接依存する式が得られれば、任意の項を容易に評価できる。数列の性質を比較する際にも有用である。
4.2 組合せ論への応用
組合せ論では、ある配置や選び方の総数を漸化式で表すことが多い。問題を小さい場合へ分割し、その結果を積み上げると、数え上げの規則が明確になる。パズルや経路問題などでも頻繁に現れる。
4.3 アルゴリズム解析への応用
計算機科学では、漸化式はアルゴリズムの実行時間や処理量の解析に使われる。分割統治法や再帰的手続きでは、入力サイズの減少に伴う計算量が漸化式で記述される。これにより、成長の速さや効率の違いを比較しやすくなる。
4.4 自然現象のモデル化
自然現象の中には、時間を細かい段階に区切って捉えると漸化式で近似できるものがある。個体数の変化、物理量の反復更新、離散的な測定値の推移などが例に挙げられる。連続モデルの簡略化としても利用される。
4.5 経済・人口モデルへの応用
経済や人口の分野では、一定期間ごとの増減を表すのに漸化式が便利である。貯蓄、利子、需要、世帯数の変化など、時点ごとの更新が中心となる現象を表現しやすい。将来予測や政策シミュレーションの基礎としても用いられる。