漸化式

数学における漸化式（ぜんかしき、テンプレート:Lang-en-short; 再帰関係式）は、各項がそれ以前の項の函数として定まるという意味で数列を再帰的に定める等式である。

ある種の漸化式はしばしば差分方程式 (difference equation) と呼ばれる。また、「差分方程式」という言葉を単に「漸化式」と同義なものとして扱うことも多い。

漸化式の例として、ロジスティック写像

<math>x_{n+1} = r x_n (1 - x_n)</math>

が挙げられる。このような単純な形の漸化式が、しばしば非常に複雑な（カオス的な）挙動を示すことがあり、このような現象についての研究は非線型解析学などと呼ばれる分野を形成している。

漸化式を解くとは、 添字 n に関する非再帰的な函数として、一般項を表す閉じた形の式を得ることをいう。

簡単な例

フィボナッチ数列は線型漸化式

<math>F_{n} = F_{n-1}+F_{n-2}</math>

に初期値、F₀ = 0, F₁ = 1 を与えて得られる。

この漸化式は、陽に書けば F₂ = F₁ + F₀, F₃ = F₂ + F₁, F₄ = F₃ + F₂, ... といった無限個の式と同じである。

こうして得られるフィボナッチ数列のはじめのほうを書けば

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

となる。後述するような方法で漸化式を解けば、特性多項式（固有多項式） t² + t + 1 の二つの根を用いたテンプレート:仮リンクが得られる。フィボナッチ数列の母函数は

<math>\frac{t}{1-t-t^2}</math>

という有理式である。

構造

定数係数斉次線型漸化式

定数係数の d-階斉次線型漸化式は、一般に

<math>a_n = c_1a_{n-1} + c_2a_{n-2}+\cdots+c_da_{n-d}</math>

の形に表される式で、d 個の係数 c_i はすべての i について定数となるものである。

一般に、d-階斉次線型漸化式の解は、異なる公比をもつ d-個の幾何数列の和として表される。例外は、それらの幾何数列の公比を与える方程式の根が重根を持つ場合である。このように幾何数列の和として書かれた式をビネーの公式 (Binet's formula) という（ただし「ビネーの公式」という名称は、フィボナッチ数列の一般項を二つの冪数列の和として表す式の意味で用いられることのほうが多い）。

もう少し詳しく言えば、この線型漸化式は各 n(> d − 1) に対する無限本の線型方程式に関する連立方程式であり、この形の漸化式を満たす列は線形回帰数列 (linear recursive sequence) と呼ばれ、あるいは短く "LRS" とも呼ばれる。d-階の線型再帰列は初期値 a₀, ..., a_d−1 を任意に選ぶ分だけの自由度 d を持ち、それら初期値に対して一意に決定される。

この形の線型漸化式と同じ係数を持つ、漸化式の固有多項式または特性多項式 (characteristic polynomial) あるいは補助多項式 (auxiliary polynomial) と呼ばれる多項式

<math>p(t)= t^d - c_1t^{d-1} - c_2t^{d-2}-\cdots-c_{d}</math>

は、その d 個の根が漸化式を満たす数列を求め、理解するのにきわめて重要な役割を果たす。

有理母函数

線型再帰列は、その母函数が有理函数となるような数列として特徴付けられる。母函数の分母は（適当な変換をうける違いを除いて）特性多項式であり、分子は初期値から決まる。

もっとも単純なものは、a_n = a_n−d なる周期数列 a₀, a₁, ..., a_d−1, a₀, a₁, ... の場合であり、この列の母函数は幾何数列の和

<math>\begin{align}

&\frac{a_0 + a_1 x^1 + \cdots + a_{d-1}x^{d-1}}{1-x^d} \\[9pt] &= \left(a_0 + a_1 x^1 + \cdots + a_{d-1}x^{d-1}\right) \\ & \qquad + \left(a_0 + a_1 x^1 + \cdots + a_{d-1}x^{d-1}\right)x^d \\ & \qquad + \left(a_0 + a_1 x^1 + \cdots + a_{d-1}x^{d-1}\right)x^{2d} + \cdots \end{align}</math>

として表される。もっと一般に、漸化式

<math>a_n = c_1a_{n-1} + c_2a_{n-2}+\cdots+c_da_{n-d}</math>

と母函数

<math>a_0 + a_1x^1 + a_2 x^2 + \cdots</math>

が与えられたとき、多項式

<math>1- c_1x^1 - c_2 x^2 - \cdots - c_dx^d</math>

を使って、母函数級数の a_d 以降の係数を消去することができる。つまり、母函数に先の多項式を掛け合わせれば

<math>b_n = a_n - c_1 a_{n-1} - c_2 a_{n-2} - \cdots - c_d a_{n-d}</math>

が xⁿ の係数となり、これは特に n ≥ d のとき（漸化式によって）0 となる。したがって、

<math>(a_0 + a_1x^1 + a_2 x^2 + \cdots {} ) (1- c_1x^1 - c_2 x^2 - \cdots - c_dx^d) = (b_0 + b_1x^1 + b_2 x^2 + \cdots + b_{d-1} x^{d-1})</math>

が成立し、両辺を割り算すれば

<math>a_0 + a_1x^1 + a_2 x^2 + \cdots =

\frac{b_0 + b_1x^1 + b_2 x^2 + \cdots + b_{d-1} x^{d-1}}{1- c_1x^1 - c_2 x^2 - \cdots - c_dx^d}</math>

という母函数の有理式表示を得る。

分母 x^dp(1/d) は特性多項式を変換したもの（あるいは同じことだが、係数の順番を逆順にしたもの）である。これに何かを掛けたものを使うこともできるが、特性多項式から簡単に求められて、b₀ = a₀ となるように正規化してある。

狭義の差分方程式との関係

実数列 (a_n)_n=1^∞ が与えられたとき、この数列の第一階差 (first difference) Δ(a_n) は

<math>\Delta(a_n) = a_{n+1} - a_n</math>.

で与えられ、第二階差 (second difference) Δ²(a_n) が

<math>\Delta^2(a_n) = \Delta(a_{n+1}) - \Delta(a_n)</math>

あるいは簡約化して

<math>\Delta^2(a_n) = a_{n+2} - 2a_{n+1} + a_n</math>

で与えられる。もっと一般に、数列 (a_n) の第 k-階差 (k^th difference) Δk(an) が

<math>\Delta^k(a_n) = \Delta^{k-1}(a_{n+1}) - \Delta^{k-1}(a_n)</math>

で帰納的に定義される。狭い意味での差分方程式とは数列 (a_n) およびその各階の階差数列との間に成り立つ等式のことをいう。広い意味では「差分方程式」を「漸化式」と同義に用いる（たとえば有理差分方程式および線型差分方程式を参照）。

線型漸化式は狭い意味での差分方程式であり、逆もいえる。それはこれらが単純かつ共通した形の再帰性をもつからであり、文献によっては両者を逆に呼んでいるものもある。たとえば差分方程式

<math>3\Delta^2(a_n) + 2\Delta(a_n) + 7a_n = 0</math>

は、漸化式

<math>3a_{n+2} = 4a_{n+1} - 12a_n</math>

と同値である。よって、多くの漸化式は差分方程式として読み替えて解くことができるし、差分方程式ならば常微分方程式の解法と類似の手法で解くことができる。しかし、アッカーマン数などは差分方程式に直すことが非常に困難であり、微分方程式の観点から得られるものは少ない。

このような微分方程式に対する微分方程式論の一意化についてはテンプレート:仮リンクを参照せよ。

微分方程式に対をなすように積分方程式が考えられるのと同様、差分方程式の対となる和分方程式が考えられる。

格子点と多重数列

一変数（一元）漸化式は（一次元整格子点 (grid) の上で定義される函数としての）数列について記述するものである。多変数（n-元）漸化式は同様に n-次元整格子点 (n-grid) 上で定まる概念であると理解することができる。n-次元整格子点上で定義される函数（n-重数列）についても偏差分方程式 (partial difference equations) を考えることができる。

漸化式の解法

一般的な方法

一階の漸化式については特段の理論を要しない。漸化式

<math>a_{n}=r a_{n-1}</math>

は明らかに初期値 a₀ = 1 に対して a_n = r^{n</sub> を解にもち、一般に a₀ = k とすれば一般解 a_n = krn が得られる。この漸化式の特性多項式を 0 に等しいとおいて得られる特性方程式（固有方程式）は、単に t − r = 0 で与えられることに注意。}

高階の漸化式の解は、しばしば a_n = rⁿ がちょうど t = r が特性多項式の根となるような漸化式の解となるという事実を用いて、機械的に求めることができる。方法としては直接、あるいは母函数（形式冪級数）、行列などを用いる。

たとえば

<math>a_{n}=Aa_{n-1}+Ba_{n-2}</math>

という形の漸化式を考えよう。この漸化式が a_n = r^{n</sub> と同じ形の解の一般形をもつのはどのようなときだろうか。実際に代入してみれば}

<math>r^{n}=Ar^{n-1}+Br^{n-2}</math>

が任意の n(> 1) について成り立たなければならないことがわかる。両辺を rⁿ⁻² で割れば、意味はそのままに方程式 r² − Ar − B = 0 に簡約することができる。これがこの漸化式の特性方程式である。これを r について解けば、二つの根 λ₁, λ₂ が得られる。これらの根は、特性方程式あるいは漸化式の特性根あるいは固有値として知られるものである。異なる解が得られるかは特性根の様子に依存するが、二つの特性根が相異なるならば、一般解

<math>a_n = C\lambda_1^n+D\lambda_2^n</math>

が得られる。一方、特性根が重根 (A² + 4B = 0) のとき、

<math>a_n = C\lambda^n+Dn\lambda^n</math>

が一般解を与える。これらは今考えている漸化式の解を全て尽くしており、二つの定数 C, D は初期条件 a₀, a₁ の選び方に依存して一意に決まり、これにより解がひとつに特定される。

特性根が複素数となる場合は（もちろん一般解のパラメータ C, D も複素数値となるが）、三角函数を用いた形に書けば、複素数を使用しない形にすることができる。この場合は特性根を λ_k = α ± β（各 k = 1, 2 に ± の何れか一方をそれぞれ割り当てる）の形に書いてやれば、たとえば a_n = Cλ₁ⁿ + Dλ₂ⁿ の形の一般解が

<math>a_n = 2 M^n(E\cos(n\theta) + F\sin(n\theta)) = 2GM^{n}\cos(n\theta - \delta)</math>

の形に書きなおせることが示せるテンプレート:Rp。ここで、各定数は

<math>\begin{align}

 & M = \sqrt{\alpha^2+\beta^2},\quad \cos(\theta) = \frac{\alpha}{M},\quad \sin(\theta) = \frac{\beta}{M}, \\
 & C,D = E \mp F i,\\
 & G = \sqrt{E^2+F^2},\quad \cos(\delta) = \frac{E}{G},\quad \sin(\delta) = \frac{F}{G}

\end{align}</math> で与えられるものである。E, F（あるいは同じことだが G, δ）は初期条件から決まる実定数である。

注意すべきは、特性根が相異なる実根の場合も、実重根の場合も、互いに共軛な複素根の場合も、すべての場合で方程式が安定である（つまり、変数 a が特定の値（特に 0）に収束する）ための必要十分条件は二つの特性根の絶対値が「ともに」1 より小さいこと、となることである。今考えている二階漸化式の場合、特性根に関するこの条件は |A| < 1 − B < 2 に同値であることが示せる。

上記の例は定数項の無い斉次の場合であった。定数項 K を加えて、非斉次の場合の漸化式

<math>b_{n}=Ab_{n-1}+Bb_{n-2}+K \,</math>

を考えよう。これは次のようにして斉次の場合に帰着することができる。不動点 b^∗ は b_n = b_n−1 = b_n−2 = b* と置くことによって、

<math> b^{*} = \frac{K}{1-A-B}</math>

と求められる。これにより、先ほどの非斉次漸化式は

<math>[b_{n}-b^{*}]=A[b_{n-1}-b^{*}]+B[b_{n-2}-b^{*}]</math>

なる形の斉次漸化式に書き直すことができる（これは上述のように解くことができる）。

二階の場合に特性根の言葉で述べた安定性条件は、一般の n-階でもやはり有効であることに注意。つまり漸化式の解が安定であるための必要十分条件は、漸化式の特性多項式の全ての根が 1 より小さい絶対値を持つことである。

線型代数を用いた解法

線型漸化式 T_n = c_d−1Tⁿ⁻¹ + c_d−2Tⁿ⁻² + … + c₀T_n−d が与えられたとき、その特性多項式のコンパニオン行列の転置

<math>\begin{pmatrix}

0 & 1 & 0 & \cdots & 0\\ 0 & 0 & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & 0 & \cdots & 1\\ -c_0 & -c_1 & -c_2 & \cdots & -c_{d-1} \end{pmatrix}</math>

を C とすると、明らかに

<math>\begin{pmatrix}a_n\\ \vdots\\ a_{n+(d-1)}\end{pmatrix} = C^n \begin{pmatrix} a_0 \\ \vdots \\ a_{d-1} \end{pmatrix}</math>

が成り立つ。固有値 λ₁, ..., λ_d に対応する固有基底 v₁, ..., v_d を決めれば、線型再帰列の初期値を固有ベクトルの線型結合

<math>\begin{pmatrix} a_0 \\ \vdots \\ a_{d-1} \end{pmatrix} = b_1v_1 + \cdots + b_dv_d</math>

として表せるので、結局

<math>\begin{pmatrix} a_n \\ \vdots \\ a_{n+(d-1)}\end{pmatrix} = C^n \begin{pmatrix} a_0 \\ \vdots \\ a_{d-1}\end{pmatrix} = C^n (b_1v_1 + \cdots + b_dv_d) = \lambda_1^nb_1v_1 + \cdots + \lambda_d^n b_dv_d</math>

となることがわかる。行列を用いたこの記述は、本質的には既に述べた一般的方法となんらかわるものではないが、より簡潔である。また、行列を用いた記述は

<math>\begin{cases} a_n = a_{n-1}-b_{n-1}\\ b_n=2a_{n-1}+b_{n-1}\end{cases}</math>

のような連立漸化式に対してもなお有効である。

z-変換による解法

ある種の差分方程式、とくに定数係数線型差分方程式は、z-変換を用いて解くことができる。z-変換は積分変換の一種で代数的操作がしやすく、解がより容易に求まる。解が直接には、まったくというわけではないが不可能な場合でも、積分変換をうまく選べば容易に解けることもある。

定理

階数 d の定数係数斉次線型漸化式が与えられたとき、p(t) をその特性多項式

<math>t^d - c_1t^{d-1} - c_2t^{d-2}-\cdots-c_{d}</math>

とし、λ を重複度 r の特性根とする（つまり (t − λ)^{r</sub> が p(t) を割り切る）。このとき、}

r 個の数列 λⁿ, nλⁿ, n²λ^{n</sub>, ..., nr−1λn は与えられた漸化式をおのおの満たす。これを p(t) の相異なる全ての根 λ に亘って考えたものは、与えられた漸化式の任意の解を生成する。}

この定理の帰結として、定数係数斉次線型漸化式は次の手順に従って解くことができる。

1. 漸化式の特性多項式 p(t) を求める。
2. p(t) の根とその重複度を求める。
3. a_n を未定係数 b_i を持つ（上で述べたように重複度を考慮した）全ての根の冪の線型結合
   <math> \begin{align} a_n =

 &(b_1\lambda_1^n + b_2n\lambda_1^n + \cdots + b_{r}n^{r-1}\lambda_1^n)\\
 & \quad + \cdots +(b_{d-q+1}\lambda_{*}^n + b_{d-q+2}n\lambda_{*}^n + \cdots + b_{d}n^{q-1}\lambda_{*}^n) 

\end{align}</math>