遞迴關係かんけい式しき

递推关系（英語えいご：Recurrence relation），在ざい數學すうがく上うえ也就是ぜ差分さぶん方かた程ほど（英語えいご：Difference equation），是ぜ一いち種しゅ递推地ち定義ていぎ一いち個こ序列じょれつ的てき方程式ほうていしき：序列じょれつ的てき每ごと一項目是定義為前若干項的函數かんすう。

像ぞう斐波那な契ちぎり数すう即そく為ため递推关系

$x_{n+2}=x_{n+1}+x_{n}$

某ぼう些簡單かんたん定義ていぎ的てき遞迴關係かんけい式しき可能かのう會かい表現ひょうげん出で非常ひじょう複雜ふくざつ的てき（混沌こんとん的てき）性質せいしつ，他た們屬於數學がく中ちゅう的てき非ひ線せん性せい分析ぶんせき領域りょういき。

所謂いわゆる解かい一いち個こ遞迴關係かんけい式しき，也就是ぜ求もとめ其解析かいせき解かい，即そく關せき於$n$的てき非ひ遞迴函數かんすう。

遞迴關係かんけい式しき的てき例れい子こ

等差とうさ數列すうれつ

$x_{0}=1,x_{n+1}=x_{n}+2$為ため等差とうさ數列すうれつ$1,3,5,7,.....$

一般いっぱん地ち，$x_{0}=a,\ x_{n+1}=x_{n}+d$為ため等差とうさ數列すうれつ，其中$a$為ため首くび項こう，$d$為ため公差こうさ。

等比とうひ數列すうれつ

$x_{0}=1,x_{n+1}=2x_{n}$為ため等比とうひ數列すうれつ$1,2,4,8,.....$

一般いっぱん地ち，$a\neq 0$且$r\neq 0$，$x_{0}=a,\ x_{n+1}=rx_{n}$為ため等比とうひ數列すうれつ，其中$a$為ため首くび項こう，$r$為ため公おおやけ比ひ。

階かい乘じょう

$0!=1$

$n!=n\times (n-1)!$

因いん此最小さいしょう的てき幾いく個こ階かい乘じょう為ため$1,1,2,6,24,120,720,5040,.....$、

倒たおせ数すう和わ

設しつらえ$x_{k}=x^{k}+x^{-k}$，則のり

$x_{1}=x_{1}$

$x_{2}=(x_{1})^{2}-2$

$x_{3}=x_{1}\cdot x_{2}-x_{1}$

$x_{4}=(x_{2})^{2}-2$

$x_{5}=x_{2}\cdot x_{3}-x_{1}$

$x_{6}=(x_{3})^{2}-2$

$x_{7}=x_{3}\cdot x_{4}-x_{1}$

$\cdots \cdots$

$x_{2k}=(x_{k})^{2}-2$

$x_{2k+1}=x_{k}\cdot x_{k+1}-x_{1}$

常つね係數けいすう線せん性せい齊ひとし次じ遞迴關係かんけい式しき

線せん性せい（英語えいご：Linear）的てき意思いし是ぜ序列じょれつ的てき每ごと一項目是被定義為前一項的一種線性函數。係數けいすう和わ常數じょうすう可能かのう視し$n$而定，甚至是非ぜひ線せん性せい地ち。

一種特別的情況是當係數並不依照$n$而定。

齊ひとし次つぎ（英語えいご：Homogenous）的てき意思いし為ため关系的てき常數じょうすう項こう為ため零れい。

為ため了りょう要よう得え到いた線せん性せい遞迴唯一ゆいいつ的てき解かい，必須ひっす有ゆう一いち些起始はじめ條件じょうけん，就是序列じょれつ的てき第だい一個數字無法依照該序列的其他數字而定時，且必須ひっす設定せってい為ため某ぼう些數值。

解かい線せん性せい遞迴關係かんけい式しき

線せん性せい遞迴關係かんけい式しき的てき解かい通常つうじょう是ぜ由よし系統けいとう的てき方法ほうほう中ちゅう找出來でき，通常つうじょう藉由使用しよう生成せいせい函數かんすう（形式けいしき冪べき級數きゅうすう）或ある藉由觀察かんさつ$r^{n}$是ぜ一いち種しゅ對たい$r$的てき特定とくてい數すう值之解かい的てき事實じじつ。且因關係かんけい式しき為ため線せん性せい方かた程ほど，另一種方法是以矩陣表示此一遞迴關係式，並なみ透過とうか矩のり陣じん對たい角かく化か等とう技巧ぎこう求もとめ出で關係かんけい式しき的てき通どおり項こう。

二に階かい遞迴關係かんけい式しき的てき形式けいしき：

$a_{n}=Aa_{n-1}+Ba_{n-2}\,$

我わが們擁有ゆう解かい為ため$r^{n}$：

$r^{n}=Ar^{n-1}+Br^{n-2}\,$

兩邊りょうへん除じょ以$r^{n-2}$我わが們可以得到いた：

$r^{2}=Ar+B\,$

$r^{2}-Ar-B=0\,$

這就是ぜ遞迴關係かんけい式しき的てき特徵とくちょう方かた程ほど。解かい出で$r$可か獲得かくとく兩個りゃんこ根ね（英語えいご：Roots）$\lambda _{1},\lambda _{2}$，且如果はて兩個りゃんこ根ね是ぜ不同ふどう的てき，我わが們可得え到いた解かい為ため

$a_{n}=C\lambda _{1}^{n}+D\lambda _{2}^{n}\,$

而如果はて兩個りゃんこ根ね是ぜ相しょう同どう的てき（當とう$A^{2}+4B=0$），我わが們得到いた

$a_{n}=C\lambda ^{n}+Dn\lambda ^{n}\,$

$C$和わ$D$都みやこ是ただし常數じょうすう。以上いじょう結果けっか皆みな可か由よし直接ちょくせつ代入だいにゅう得とく證しょう，或ある以矩陣じん對たい角かく化か的てき技巧ぎこう推導出どうしゅつ。

換かわ句く話はなし說せつ，將はた這種$a_{n}=Aa_{n-1}+Ba_{n-2}$形式けいしき的てき方程式ほうていしき，用よう$2$代入だいにゅう$n$後ご，就得到いた上述じょうじゅつ的てき$r^{2}=Ar+B$。常數じょうすう$C$和わ$D$可か以從"邊べ界かい條件じょうけん（side conditions）"中ちゅう得え到いた，通常つうじょう會かい像ぞう是ぜ「已やめ知ち$a_{0}=c_{1}$, $a_{1}=c_{2}$」。

範はん例れい：斐波那な契ちぎり数すう（英語えいご：Fibonacci Number）

斐波那な契ちぎり数すう是ぜ使用しよう一種線性遞迴關係式來定義：

$F_{0}=0\,$

$F_{1}=1\,$

$F_{n}=F_{n-1}+F_{n-2}\,$

設しつらえ若わか：$F_{n}/F_{n-1}\,$當とうn趨於無限むげん大だい之の極限きょくげん值存在そんざい，則のり其值為ため$1+{\sqrt {5}} \over 2\,$ $=\Phi$恰為黃金おうごん分割ぶんかつ值$1.618....$，另一值則為ため$0.618....$，兩りょう值互為ため倒たおせ數すう，也就是ぜ說せつ${\frac {1}{1.618....}}=0.618....$，反はん之これ亦また然しか。

$F_{n}={\Phi ^{n} \over {\sqrt {5}}}-{(1-\Phi )^{n} \over {\sqrt {5}}}$

起おこり始はじめ條件じょうけん為ため：

$F_{0}=0\,$

$F_{1}=1\,$

因いん此，斐波那な契ちぎり数すう的てき序列じょれつ為ため：

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

常つね系けい数すう非ひ齐次线性递推关系

对于常つね系けい数すう非ひ齐次线性递推关系，我わが们可以用待まち定じょう系けい数すう法ほう来らい求もとめ出で它的一いち个特解かい，而它的てき通どおり解かい就是这个特とく解かい与あずか对应的てき齐次递推关系的てき通どおり解かい的てき和わ。也可以使用しよう迭代法ほう求もとめ解かい，但ただし只ただ能のう得え到いた确切的てき数すう值解，不能ふのう直接ちょくせつ以解析かいせき式しき作さく答こたえ，该方法ほうほう可か利用りよう计算机つくえ求もとめ解かい。

时域经典法ほう求もとめ解かい

一般いっぱん情じょう况下，常つね系けい数すう线性差分さぶん方かた程ほど可か以写作さく：

$\sum _{k=0}^{N}a_{k}y(n-k)=\sum _{r=0}^{M}b_{r}x(n-r)$

则对应的齐次方かた程ほど形式けいしき为：

$\sum _{k=0}^{N}a_{k}y(n-k)=0$

则特征せい方かた程ほど为：

$\sum _{k=0}^{N}a_{k}\alpha ^{N-k}=0$

当とう特とく征せい根ね非ひ重根しこね时，齐次解かい为：

$y_{h}(n)=\sum _{i=1}^{N}C_{i}\alpha _{i}^{n}$

当とう特とく征せい根ね为重根ね时，若わか$\alpha _{1}$为特征せい方かた程ほど的てき$K$重根しこね，齐次解かい为：

$y_{h}(n)=\sum _{i=1}^{K}n^{K-i}\alpha _{1}^{n}$

特とく解かい$y_{p}(n)=D(n)$的てき形式けいしき由よし激励げきれい函数かんすう$x(n)$的てき形式けいしき决定。

一般いっぱん情じょう况，当とう激励げきれい函数かんすう$x(n)$代入だいにゅう方かた程ほど。

方かた程ほど右みぎ方かた出で现$n^{k}$的てき形式けいしき，则特解かい选择

$y_{p}(n)=A_{0}n^{k}+A_{1}n^{k-1}+\cdots +A_{k}$

当方とうほう程ほど右みぎ方かた出で现$a^{n}$的てき形式けいしき，则特解かい选择

当とう$a$不ふ是ぜ特とく征せい根ね时

$y_{p}(n)=Aa^{n}$

当とう$a$是ぜ特とく征せい根ね时

$y_{p}(n)=(A_{1}n+A_{0})a^{n}$

当とう$a$为$r$重根しこね时

$y_{p}(n)=(A_{r}n^{r}+A_{r-1}n^{r-1}+\cdots +A_{1}n+A_{0})a^{n}$

将はた特とく解かい带入原方はらかた程ほど，求もとめ出で待まち定じょう系けい数すう。根ね据すえ边界条件じょうけん，可か求もとめ出で齐次节待定じょう系けい数すう。

例れい子こ

我わが们用待まち定じょう系けい数すう法ほう来らい解かい以下いか的てき常つね系けい数すう非ひ齐次线性递推关系：

$a_{n+1}=2a_{n}+3^{n}+5n\,$

对应的てき齐次递推关系

$b_{n+1}=2b_{n}\,$

的てき齐次解かい是ぜ：

$b_{n}=c_{1}2^{n}\,$

我わが们猜测特解かい的てき形式けいしき为：

$a_{n}=c_{2}3^{n}+c_{3}n+c_{4}\,$

代入だいにゅう原げん递推关系中ちゅう，我わが们便得え到いた：

$c_{2}3^{n+1}+c_{3}(n+1)+c_{4}=2(c_{2}3^{n}+c_{3}n+c_{4})+3^{n}+5n\,$

比ひ较等式しき两端的てき$3^{n}$项的系けい数すう，可か得とく：

$3c_{2}=2c_{2}+1\,$

$c_{2}=1\,$

比ひ较等式しき两端的てき$n$项的系けい数すう，可か得とく：

$c_{3}=2c_{3}+5\,$

$c_{3}=-5\,$

比ひ较等式しき两端的てき常数じょうすう项，可か得とく：

$c_{3}+c_{4}=2c_{4}\,$

$c_{4}=c_{3}=-5\,$

因いん此原递推关系的てき通どおり解かい为：

$a_{n}=c_{1}2^{n}+3^{n}-5n-5\,$

與あずか微分びぶん方かた程ほど的てき關係かんけい

数かず值求もとめ解かい常微分じょうびぶん方かた程ほど时，经常会かい遇ぐう到いた递归关系。例れい如，求もとめ解かい如下初はつ值问题时

$y'(t)=f(t,y(t)),\qquad y(t_{0})=y_{0},\qquad \qquad$

如采用よう欧おう拉ひしげ法ほう和かず步あゆみ长h，可か以通过如下か递归关系计算$y_{0}=y(t_{0})$, $y_{1}=y(t_{0}+h),$ $y_{2}=y(t_{0}+2h),...$

$y_{n+1}=y_{n}+hf(t_{n},y_{n})$

线性一阶微分方程组可以用离散化か条目じょうもく中ちゅう介かい绍的方法ほうほう解析かいせき地ち精せい确离散化か。

參考さんこう

• 递归
• 差分さぶん
• 主しゅ定理ていり——分析ぶんせき算法さんぽう複雜ふくざつ度ど的てき方法ほうほう，從したがえ遞歸式しき得とく出で通どおり項こう的てき大小だいしょう估計
• 圆点段だん证明（英語えいご：Circle points segments proof）
• 母はは函数かんすう——形式けいしき冪べき級數きゅうすう，其系數すう隱かくれ含某數列すうれつ的てき資し訊

外部がいぶ連結れんけつ

• Difference and Functional Equations: Exact Solutions （页面存そん档备份，存そん于互联网档案あん馆） at EqWorld - The World of Mathematical Equations.
• Difference and Functional Equations: Methods （页面存そん档备份，存そん于互联网档案あん馆） at EqWorld - The World of Mathematical Equations.