# 遞迴關係

order-r recurrence以明示initial values與total single-valued state update逐項決定sequence。

mko-recurrence-relation · definition · v0.10.0



## 數學敘述

令A_n=(a_{n-r+1},...,a_n)為order-r state vector；initial_values[j]=a_j，coefficients[j]乘a_{n-r+j}，新項為constant+sum_{j=0}^{r-1}coefficients[j]a_{n-r+j}。F先shift-left再append該new scalar term。必須明示order r、適用n≥r與全部r個初值。缺一初值、多值rule或未定義分母不得稱unique。有限生成只驗prefix，不證closed form、convergence或asymptotics。





## 代表公式（精確 TeX）

A_n=F(A_{n-1})





## 成立條件


- 正向families使用上述oldest-to-newest coefficient order的bounded exact integer linear recurrence及order-r state。
- target index有限且所有中間值保持safe integer。





## 符號作用域


- A_n — 包含最近r個scalar terms的遞迴state vector
- F — shift-left並append新項的全定義單值state更新規則





## 直觀、定義與常見誤解

order決定state width與所需initial count。

coefficient array由oldest a_(n-r)到newest a_(n-1)對齊。

forward generation shift-left後append新項，unique prefix不外推analytic behavior。

倒置coefficient順序、order二只給一個初值便稱唯一，或由少數項猜closed form當證明。





## 已採用的推導導讀

[oldest-to-newest二階遞迴trace](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-recurrence-relation-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [數列](https://ocme.evemisslab.com/zh-Hant/mko/mko-sequence/) — indexed sequence。
- [方程式](https://ocme.evemisslab.com/zh-Hant/mko/mko-equation/) — update equality。
- [函數映射](https://ocme.evemisslab.com/zh-Hant/mko/mko-function-mapping/) — total single-valued rule。





## 驗證界線

只處理明示有限步exact integer models。

not_formalized

這不表示內容錯誤；只表示尚未登錄可重播的計算或形式證據。





## 下一個義務

加入Catalan numbers與generating functions。





## 同源結構化資料

本頁與互動版共用同一個物件與既有語言 edition；未新增證明或人工審定。

[原始 MKO JSON](https://ocme.evemisslab.com/data/mko/recurrence-relation.json) · [純文字 Markdown](https://ocme.evemisslab.com/zh-Hant/mko/mko-recurrence-relation/index.md)