漸化式のソースを表示

[[数学]]における'''漸化式'''（ぜんかしき、{{lang-en-short|''recurrence relation''}}; 再帰関係式）は、各項がそれ以前の項の[[函数]]として定まるという意味で[[数列]]を[[再帰|再帰的]]に定める等式である。

ある種の漸化式はしばしば'''差分方程式''' {{lang|en|(''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''<sub>0</sub> = 0, ''F''<sub>1</sub> = 1 を与えて得られる。

この漸化式は、陽に書けば ''F''<sub>2</sub> = ''F''<sub>1</sub> + ''F''<sub>0</sub>, ''F''<sub>3</sub> = ''F''<sub>2</sub> + ''F''<sub>1</sub>, ''F''<sub>4</sub> = ''F''<sub>3</sub> + ''F''<sub>2</sub>, ... といった無限個の式と同じである。

こうして得られるフィボナッチ数列のはじめのほうを書けば
: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

となる。後述するような方法で漸化式を解けば、特性多項式（固有多項式） ''t''<sup>2</sup> + ''t'' + 1 の二つの根を用いた{{仮リンク|ビネーの公式|label=閉じた式|en|Binet formula}}が得られる。フィボナッチ数列の[[母函数]]は
: <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''<sub>''i''</sub> はすべての ''i'' について定数となるものである。

一般に、''d''-階斉次線型漸化式の解は、異なる公比をもつ ''d''-個の[[幾何数列]]の和として表される。例外は、それらの幾何数列の公比を与える方程式の根が重根を持つ場合である<ref>{{cite book |
title= The Fibonacci Sequence and Beyond|last= Gilson|first= Bruce R.|year= 2009|publisher= CreateSpace|location= |isbn= 978-1449974114 |pages= 16 ff.}}</ref>。このように幾何数列の和として書かれた式を'''ビネーの公式''' {{lang|en|(Binet's formula)}} という<ref>[http://www.numericana.com/answer/numbers.htm#binet Discussion on s]</ref>（ただし「ビネーの公式」という名称は、フィボナッチ数列の一般項を二つの冪数列の和として表す式の意味で用いられることのほうが多い）。

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

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

:<math>p(t)= t^d - c_1t^{d-1} - c_2t^{d-2}-\cdots-c_{d}</math>
は、その ''d'' 個の根が漸化式を満たす数列を求め、理解するのにきわめて重要な役割を果たす。

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

もっとも単純なものは、''a''<sub>''n''</sub> = ''a''<sub>''n''&minus;''d''</sub> なる周期数列 ''a''<sub>0</sub>, ''a''<sub>1</sub>, ..., ''a''<sub>''d''&minus;1</sub>, ''a''<sub>0</sub>, ''a''<sub>1</sub>, ... の場合であり、この列の母函数は幾何数列の和
:<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''<sub>''d''</sub> 以降の係数を消去することができる。つまり、母函数に先の多項式を掛け合わせれば

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

が ''x''<sup>''n''</sup> の係数となり、これは特に ''n'' &ge; ''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''<sup>''d''</sup>''p''(1/''d'') は特性多項式を変換したもの（あるいは同じことだが、係数の順番を逆順にしたもの）である。これに何かを掛けたものを使うこともできるが、特性多項式から簡単に求められて、''b''<sub>0</sub> = ''a''<sub>0</sub> となるように正規化してある。

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

[[実数|実]][[数列]] (''a''<sub>''n''</sub>)<sub>''n''=1</sub><sup>&infin;</sup> が与えられたとき、この数列の'''第一階差''' {{lang|en|(''first difference'')}} &Delta;(''a''<sub>''n''</sub>) は

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

で与えられ、'''第二階差''' {{lang|en|(''second difference'')}} &Delta;<sup>2</sup>(''a''<sub>''n''</sub>) が

:<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''<sub>''n''</sub>) の'''第 ''k''-階差''' {{lang|en|(''k''<sup>th</sup> difference'')}} &Delta;<sup>''k''</sup>(''a''<sub>''n''</sub>) が

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

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

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

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

は、漸化式

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

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

このような[[微分方程式]]に対する微分方程式論の一意化については{{仮リンク|時間スケール微分積分学|en|time scale calculus}}を参照せよ。

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

==== 格子点と多重数列 ====
一変数（一元）漸化式は（一次元整格子点 {{lang|en|(grid)}} の上で定義される函数としての）数列について記述するものである。多変数（''n''-元）漸化式は同様に ''n''-次元整格子点 {{lang|en|(''n''-grid)}} 上で定まる概念であると理解することができる。''n''-次元整格子点上で定義される函数（''n''-重数列）についても'''偏差分方程式''' {{lang|en|(''partial difference equations'')}} を考えることができる<ref>[http://books.google.com/books?id=1klnDGelHGEC Partial difference equations], Sui Sun Cheng, CRC Press, 2003, ISBN 9780415298841</ref>。

== 漸化式の解法 ==
=== 一般的な方法 ===
一階の漸化式については特段の理論を要しない。漸化式
:<math>a_{n}=r a_{n-1}</math>
は明らかに初期値 ''a''<sub>0</sub> = 1 に対して ''a''<sub>''n''</sub> = ''r''<sup>''n''</sub><!-- 初項が 0 番目の項であることに注意。添字が 1 から始まるならば右辺の ''r'' の指数は ''n'' &minus; 1 である--> を解にもち、一般に ''a''<sub>0</sub> = ''k'' とすれば一般解 ''a''<sub>''n''</sub> = ''kr''<sup>''n''</sup> が得られる。この漸化式の特性多項式を 0 に等しいとおいて得られる[[特性方程式]]（固有方程式）は、単に ''t'' &minus; ''r'' = 0 で与えられることに注意。

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

たとえば
:<math>a_{n}=Aa_{n-1}+Ba_{n-2}</math>

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

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

が任意の ''n''(&gt; 1) について成り立たなければならないことがわかる。両辺を ''r''<sup>''n''&minus;2</sup> で割れば、意味はそのままに方程式 ''r''<sup>2</sup> &minus; ''Ar'' &minus; ''B'' = 0 に簡約することができる。これがこの漸化式の特性方程式である。これを ''r'' について解けば、二つの根 &lambda;<sub>1</sub>, &lambda;<sub>2</sub> が得られる。これらの根は、特性方程式あるいは漸化式の[[特性根]]あるいは'''固有値'''として知られるものである。異なる解が得られるかは特性根の様子に依存するが、二つの特性根が相異なるならば、一般解

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

が得られる。一方、特性根が重根 (''A''<sup>2</sup> + 4''B'' = 0) のとき、

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

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

特性根が複素数となる場合は（もちろん一般解のパラメータ ''C'', ''D'' も複素数値となるが）、三角函数を用いた形に書けば、複素数を使用しない形にすることができる。この場合は特性根を &lambda;<sub>''k''</sub> = &alpha; &plusmn; &beta;（各 ''k'' = 1, 2 に &plusmn; の何れか一方をそれぞれ割り当てる）の形に書いてやれば、たとえば ''a''<sub>''n''</sub> = ''C''&lambda;<sub>1</sub><sup>''n''</sup> + ''D''&lambda;<sub>2</sub><sup>''n''</sup> の形の一般解が

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

の形に書きなおせることが示せる<ref>Chiang, Alpha C., ''Fundamental Methods of Mathematical Economics'', third edition, McGraw-Hill, 1984.</ref>{{rp|576-585}}。ここで、各定数は
:<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'', &delta;）は初期条件から決まる実定数である。

注意すべきは、特性根が相異なる実根の場合も、実重根の場合も、互いに共軛な複素根の場合も、すべての場合で方程式が[[安定性理論|安定]]である（つまり、変数 ''a'' が特定の値（特に 0）に収束する）ための必要十分条件は二つの特性根の[[絶対値]]が「ともに」1 より小さいこと、となることである。今考えている二階漸化式の場合、特性根に関するこの条件は |''A''| &lt; 1 &minus; ''B'' &lt; 2 に同値であることが示せる<ref>Papanicolaou, Vassilis, "On the asymptotic stability of a class of linear difference equations," ''Mathematics Magazine'' 69(1), February 1996, 34-43.</ref>。

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

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

を考えよう。これは次のようにして斉次の場合に帰着することができる。[[不動点]] ''b''<sup>&lowast;</sup> は ''b''<sub>''n''</sub> = ''b''<sub>''n''&minus;1</sub> = ''b''<sub>''n''&minus;2</sub> = ''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''<sub>''n''</sub> = ''c''<sub>''d''&minus;1</sub>''T''<sup>''n''&minus;1</sup> + ''c''<sub>''d''&minus;2</sub>''T''<sup>''n''&minus;2</sup> + &hellip; + ''c''<sub>0</sub>''T''<sub>''n''&minus;''d''</sub> が与えられたとき、その特性多項式の[[コンパニオン行列]]の転置

: <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>

が成り立つ。固有値 &lambda;<sub>1</sub>, ..., &lambda;<sub>''d''</sub> に対応する[[固有基底]] ''v''<sub>1</sub>, ..., ''v''<sub>''d''</sub> を決めれば、線型再帰列の初期値を固有ベクトルの線型結合
:<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''-変換]]を用いて解くことができる。''z''-変換は[[積分変換]]の一種で代数的操作がしやすく、解がより容易に求まる。解が直接には、まったくというわけではないが不可能な場合でも、積分変換をうまく選べば容易に解けることもある。

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

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

とし、&lambda; を重複度 ''r'' の特性根とする（つまり (''t'' &minus; &lambda;)<sup>''r''</sub> が ''p''(''t'') を割り切る）。このとき、

: ''r'' 個の数列 &lambda;<sup>''n''</sup>, ''n''&lambda;<sup>''n''</sup>, ''n''<sup>2</sup>&lambda;<sup>''n''</sub>, ..., ''n''<sup>''r''&minus;1</sup>&lambda;<sup>''n''</sup> は与えられた漸化式をおのおの満たす。これを ''p''(''t'') の相異なる全ての根 &lambda; に亘って考えたものは、与えられた漸化式の任意の解を生成する。

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

# 漸化式の特性多項式 ''p''(''t'') を求める。
# ''p''(''t'') の根とその重複度を求める。
# ''a''<sub>''n''</sub> を未定係数 ''b''<sub>''i''</sub> を持つ（上で述べたように重複度を考慮した）全ての根の冪の線型結合<div style="margin: 1ex auto 1ex 2em"><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></div>として書く（''q'' は &lambda;<sub>&lowast;</sub> の重複度である）。これがもとの漸化式の一般解を与えるものとなる。
# 前段の一般解で ''n'' = 0, 1, ..., ''d'' として ''a''<sub>0</sub>, ''a''<sub>1</sub>, ..., ''a''<sub>''d''</sub> をもとの漸化式における（初期値として与えられている）既知の ''a''<sub>0</sub>, ''a''<sub>1</sub>, ..., ''a''<sub>''d''</sub> に一致させる。ただしここで、もとの漸化式の ''a''<sub>''n''</sub> の値として連続した番号のものでなくとも、どこでもいいから ''d'' 個わかってさえいればいいということには注意（つまり、考えている漸化式が三階であれば、たとえば ''a''<sub>0</sub>, ''a''<sub>1</sub> と ''a''<sub>4</sub> を使うことができる）。これにより、''d'' 個の未知数を含む ''d'' 本の連立一次方程式が得られる。これを一般解における未定係数 ''b''<sub>1</sub> , ''b''<sub>2</sub>, ..., ''b''<sub>''d''</sub> に対して解いて、一般解に代入してもとの漸化式の特殊解を得、それらがもとの漸化式の初期条件を満たす（したがって任意の ''a''<sub>0</sub>, ''a''<sub>1</sub>, ''a''<sub>2</sub>, ... についてもとの漸化式からえられる値に一致する）ことを確かめる。

興味深いのは、この方法が[[線型微分方程式]]の解法とよく似ていることである。定数係数線型微分方程式で用いられる解法では、&lambda; を複素数として ''e''<sup>&lambda;</sup> を解を求めたい方程式に代入し、方程式を満足する複素数 &lambda; を決定する（して &lambda;<sup>''i''</sub>''e''<sup>&lambda;</sup> の線型結合を考える）。

これは偶然の一致ではない。線型微分方程式の解の[[テイラー級数]]
:<math>\sum_{n=0}^{\infin} \frac{f^{(n)}(a)}{n!} (x-a)^{n}</math>

を考えれば、この級数の係数は ''f''(''x'') の ''n''-階導函数の ''x'' = ''a'' における値であることがわかる。与えられた微分方程式は、この級数の係数の間に成り立つ線型漸化式を導く。

この同値性は線型微分方程式の冪級数解の係数に対する漸化式を直ちに解くために利用できる。方程式は適当な多項式を掛けて点 0 における初項が 0 でないようにしておく。対応規則は

:<math>y^{(k)} \to  f(n+k)</math>
および一般に
:<math>x^m*y^{(k)} \to n(n-1)(n-m+1)f(n+k-m)</math>

で与えられる。
; 例: 方程式<div style="margin: 1ex auto 1ex 2em"><math>
 (x^2 + 3x -4)y''' -(3x+1)y'' + 2y = 0
</math></div>のテイラー級数解の係数の満たす漸化式は<div style="margin: 1ex auto 1ex 2em"><math> 
  n(n-1)f(n+1) + 3nf(n+2) -4f(n+3) -3nf(n+1) -f(n+2)+ 2f(n) = 0
</math></div>で与えられる。整理すると、<div style="margin: 1ex auto 1ex 2em"><math>
  -4f(n+3) +2nf(n+2) + n(n-4)f(n+1) +2f(n) = 0
</math></div>となる。この例は非常に簡単に解くことができるふつうのクラスの微分方程式でも、冪級数解を用いた解法ではなんとも扱いづらいものとなってしまうことがあることを示すものとなっている。
; 例: 微分方程式<div style="margin: 1ex auto 1ex 2em"><math>
  ay'' + by' +cy = 0</math>
</div>は ''y'' = ''e''<sup>''ax''</sup> を解に持つ。この微分方程式をテイラー係数の満たす漸化式に書き換えれば<div style="margin: 1ex auto 1ex 2em"><math>
  af(n+2) + bf(n+1) + cf(n) = 0
</math></div>となる。''e''<sup>''ax''</sup> の ''n''-階導函数の点 ''x'' = 0 における値が ''a''<sup>''n''</sup> であることをみるのは易しい。

=== 非斉次漸化式の解法 ===
漸化式が非斉次の場合、特殊解は[[未定係数法]]で求めることができて、一般の解は対応する斉次漸化式の一般解と先ほど得た特殊解の和として得られる。非斉次漸化式のほかの解法としては、'''記号微分''' {{lang|en|(''symbolic differentiation'')}} の方法がある。たとえば、次のような漸化式

:<math>a_{n+1} = a_{n} + 1</math>

を考える。これは非斉次の漸化式である。''n'' &rarr; ''n'' + 1 と置き換えれば、漸化式
:<math>a_{n+2} = a_{n+1} + 1</math>

を得る。もとの漸化式から辺々引いて整理すれば、

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

が得られる。これは斉次の漸化式であるから、既に述べた方法によって解くことができる。一般に、線型漸化式が

:<math> a_{n+k} = \lambda_{k-1} a_{n+k-1} + \lambda_{k-2} a_{n+k-2} + \cdots + \lambda_1 a_{n+1} + \lambda_0 a_{n} + p(n) </math>

という形（&lambda;<sub>0</sub>, &lambda;<sub>1</sub>, ..., &lambda;<sub>''k''&minus;1</sub> は定数の係数で、''p''(''n'') が非斉次成分）で与えられて、''P''(''n'') が ''r''-次の多項式ならば、記号微分の方法を ''r'' 回適用することにより、この非斉次漸化式を斉次漸化式に帰着することができる。

=== 一般の斉次線型漸化式 ===
多くの斉次線型差分方程式は{{仮リンク|一般化超幾何級数|en|generalized hypergeometric series}}を使って解くことができる。その特殊な場合として、差分方程式から[[直交多項式系]]や[[特殊函数]]が解として現れてくる。たとえば、

:<math>J_{n+1}=\frac{2n}{z}J_n-J_{n-1}</math>

の解は[[ベッセル函数]]

:<math>J_n=J_n(z) \,</math>,

によって与えられる。 一方、

:<math>(b-n)M_{n-1} +(2n-b-z)M_n - nM_{n+1}=0</math>

は{{仮リンク|合流型超幾何級数|en|confluent hypergeometric series}}

:<math>M_n=M(n,b;z)</math>

によって解ける。

=== 有理差分方程式の解法 ===
{{Main|有理差分方程式}}

有理差分方程式は
: <math>w_{t+1} = \frac{aw_t+b}{cw_t+d}</math>
というような形をしている。このような方程式は ''w''<sub>''t''</sub> を、それ自身は線型に増加する別の変数 ''x''<sub>''t''</sub> の非線型変換として書くことで解くことができる。したがって、''x''<sub>''t''</sub> に関する線型差分方程式を解くのに、標準的な方法が使える。

== 安定性 ==

=== 高階線型漸化式の安定性 ===

階数 ''d'' の線型漸化式

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

は特性方程式

:<math>\lambda^{d} - c_1 \lambda^{d-1} - c_2 \lambda^{d-2} - \dots - c_d \lambda^{0} = 0</math>

を持つ。この漸化式の再帰性が（反復適用によって一定の値に漸近的に収束するという意味で）[[安定性理論|安定]]であるための必要十分条件は、[[固有値]]（つまり特性方程式の根）の全てが（実数か複素数かに関わらず）1 よりも小さい[[絶対値]]を持つことである。

=== 一階線型漸化式の安定性 ===
{{main|線型差分方程式}}
状態ベクトル ''x'', 遷移行列 ''A'' をもつ一階の行列係数差分方程式

:<math>[x_t - x^*] = A[x_{t-1}-x^*]</math>

で、''x'' が定常状態ベクトル ''x''<sup>&lowast;</sup> に漸近的に収斂するための必要十分条件は、遷移行列 ''A'' の全ての固有値が（それが実数か複素数かに関わらず）1 より小さい絶対値を持つことである。

=== 一階非線型漸化式の安定性 ===
非線型一階漸化式

:<math>x_n=f(x_{n-1})</math>

を考える。この漸化式は（不動点 ''x''<sup>&lowast;</sup> の十分近くにある点は不動点 ''x''<sup>&lowast;</sup> に収斂するという意味で）[[安定性理論|局所安定]]であるための必要十分条件は、''x''<sup>&lowast;</sup> の近傍で ''f'' の傾きの絶対値が 1 よりも小さいこと、つまり

: <math>|f'(x^*)| < 1</math>

が成り立つことである。非線型漸化式は複数の不動点を持つことができ、ある不動点は局所安定だが別の不動点は局所安定でないということも起こりうることに注意。''f'' が連続なら隣接するふたつの不動点がともに局所安定となることはできない。

非線型漸化式は ''k'' &gt; 1 なる ''k'' を周期とするサイクルをもつこともありうる。そのようなサイクルが（測度正の初期条件集合を吸引するという意味で）安定となる十分条件は、''f'' の ''k'' 回合成
: <math>g(x) := f \circ f \circ \cdot \cdot \cdot \circ f(x)</math>
が上記と同様の判定条件

: <math>| g' (x^*) | < 1</math>

に従って局所安定となることである。ここで ''x''<sup>&lowast;</sup> はサイクルの任意の点。

[[カオス理論|カオス的]]漸化式においては、変数 ''x'' がある有界領域に留まるが不動点にも吸引的サイクルにも収束しない。そのような方程式において任意の不動点やサイクルは不安定である。 [[ロジスティック写像]]、{{仮リンク|二進変換|en|dyadic transformation}}、[[テント写像]]なども参照。

== 微分方程式との関連性 ==
[[常微分方程式]]を[[数値的常微分方程式|数値的]]に解く際には、典型的に漸化式が生じる。たとえば、[[初期値問題]]

:<math>y'(t) = f(t,y(t)),\quad y(t_0)=y_0</math>

を[[オイラー法]]で解くとき、刻み幅を ''h'' とすると

:<math>y_0=y(t_0),\quad y_1=y(t_0+h),\quad y_2=y(t_0+2h),\quad \ldots</math>

の値を漸化式

:<math>y_{n+1} = y_n + hf(t_n,y_n)</math>

から計算する。一階線型方程式系は{{仮リンク|離散化|en|discretization}}の項に示されるような方法を用いて完全に解析的に離散化することができる。

== 他分野での応用 ==
=== 生物学 ===

最もよく知られた差分方程式のいくつかは、集団動態モデルの研究に起源を持つ。たとえば、フィボナッチ数はうさぎの個体数の増加モデルとして使われたことがある。

[[ロジスティック写像]]は人口増加モデルに直接使われたり、より詳しいモデルの雛形として使われたりする。この文脈でいくつかの差分方程式はしばしば、二者あるいはもっと多くの人口の相互作用モデルとして用いられる。たとえば宿主・寄生生物相互作用に対するニコルソン-ベイリーモデルは

:<math>\begin{cases}
  N_{t+1} = \lambda N_t e^{-aP_t}\\
  P_{t+1} = N_t(1-e^{-aP_t})
\end{cases}</math>

で与えられる。''N''<sub>''t''</sub> は宿主、''P''<sub>''t''</sub> は寄生生物のそれぞれ時刻 ''t'' における個体数を表す。

[[積分差分方程式]]は空間的な生態学の重要な漸化式を形成する。このような、あるいはもっと他の差分方程式は[[化性|一化性]]動態のモデリンクに特に適している。

=== デジタル信号処理 ===

[[デジタル信号処理]]では、漸化式はある時点の出力が新たな時点の入力となるシステムのフィードバックをモデル化することができる。したがって、[[無限衝撃応答]] (IIR) [[デジタルフィルター]]などを考えることができる。たとえば、遅延時間 ''T'' の「フィードフォーワード」IIR [[櫛型フィルタ]]は

:<math>y_t = (1 - \alpha) x_t + \alpha y_{t - T}</math>

となる。ここで ''x''<sub>''t''</sub> は時刻 ''t'' における入力で、''y''<sub>''t''</sub> は時刻 ''t'' における出力、&alpha; はどの程度の遅延信号を出力へフィードバックするかを制御するものである。ここからわかることとして

:<math>y_t = (1 - \alpha) x_t + \alpha ((1-\alpha) x_{t-T} + \alpha y_{t - 2T})</math>
:<math>y_t = (1 - \alpha) x_t + (\alpha-\alpha^2) x_{t-T}  + \alpha^2 y_{t - 2T}</math>

などが挙げられる。

=== 経済学===

漸化式、とくに線型漸化式は、理論経済学と実証経済学の双方にわたって広く用いられている<ref>Sargent, Thomas J., ''Dynamic Macroeconomic Theory'', Harvard University Press, 1987.</ref>。特にマクロ経済学では、エージェントの活動が遅延変数に依存する経済のさまざまな幅広い分野（金融部門、商品部門、労働者市場など）のモデルが展開されている。したがって、このモデルは、[[外生変数]]や[[遅延外生変数]]を使って（金利や実質GDPなどの）鍵となる変数の現在値に関して解かれる必要がある。[[時系列分析]]も参照されたい。

== 関連項目 ==
{{colbegin}}
* [[反復関数]]
* {{仮リンク|線型差分方程式|en|Matrix difference equation}}
* [[直交多項式]]
* [[再帰]]
* [[再帰 (計算機科学)]]
* {{仮リンク|遅延フィボナッチ生成器|en|Lagged Fibonacci generator}}
* [[Master theorem]]
* [[Circle points segments proof]]
* [[連分数]]
* {{仮リンク|時間スケール微分積分学|en|time scale calculus}}
* [[積分差分方程式]]
* {{仮リンク|組合せ原理|en|Combinatorial principles}}
* [[無限インパルス応答]]
{{colend}}

== 参考文献 ==
{{reflist}}
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 1990. ISBN 0-262-03293-7. Chapter 4: Recurrences, pp.&nbsp;62–90.
* Ian Jacques. ''Mathematics for Economics and Business'', Fifth Edition. Prentice Hall, 2006. ISBN 0-273-70195-9. Chapter 9.1: Difference Equations, pp.&nbsp;551–568.
* Paul M. Batchelder, ''An introduction to linear difference equations'', Dover Publications, 1967.
* Kenneth S. Miller, ''Linear difference equations''. W.A. Benjamin, 1968.
* [http://eqworld.ipmnet.ru/en/solutions/fe.htm Difference and Functional Equations: Exact Solutions] at EqWorld - The World of Mathematical Equations.
* [http://eqworld.ipmnet.ru/en/education/edu-fe.htm Difference and Functional Equations: Methods] at EqWorld - The World of Mathematical Equations.
* [http://he-cda.wiley.com/WileyCDA/HigherEdTitle/productCd-0471230650.html  Applied Econometric time series], Second Edition. Walter Enders.
* [[Ronald L. Graham]], [[Donald E. Knuth]], and [[Oren Patashnik]]. ''[[Concrete Mathematics]]: A Foundation for Computer Science'', Second Edition. Addison-Wesley Professional, 1994. ISBN 0-201-55802-5.
* Cull, Paul; Flahive, Mary; and Robson, Robbie. ''Difference Equations: From Rabbits to Chaos'', Springer, 2005, chapter 7; ISBN 0387232346.


== 外部リンク ==
* {{MathWorld | urlname= RecurrenceEquation | title= Recurrence Equation}}
* [http://math.fullerton.edu/mathews/c2003/ZTransformDEMod.html Homogeneous Difference Equations by John H. Mathews]
* [http://books.google.com/books?id=pOBXUoVZ9EEC&pg=PA95&lpg=PA95&dq=%22difference+equation%22+%22recurrence+relation%22&source=web&ots=1kZStOrPh5&sig=VYKkC__C9AfmfrhjFhhLg_Q5YPk&hl=en&sa=X&oi=book_result&resnum=5&ct=result Introductory Discrete Mathematics]

{{DEFAULTSORT:せんかしき}}
[[Category:差分法]]
[[Category:数列]]
[[Category:計算理論]]
[[Category:数学に関する記事]]