# Recurrence relation

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

An order-r recurrence uses explicit initial values and a total single-valued state update to determine successive sequence terms.

mko-recurrence-relation · definition · v0.10.0



## Mathematical statement

The order-r state A_n=(a_(n−r+1),...,a_n) contains the latest r scalar terms. initial_values[j]=a_j, and coefficients[j] multiplies a_(n−r+j). The new term is constant+sum over j=0..r−1 of coefficients[j]*a_(n−r+j); the update F shifts the state left and then appends the new scalar term. Declare r, the scope n≥r and all r initial values. A missing initial value, multivalued rule or undefined denominator does not supply uniqueness. Finite generation checks only a prefix, not a closed form, convergence or asymptotics.





## Representative formula (exact TeX)

A_n=F(A_{n-1})





## Assumptions


- Positive families use the stated oldest-to-newest coefficient order and a bounded exact integer linear recurrence with an order-r state.
- The target index is finite and every intermediate value remains a safe integer.





## Symbol scope


- A_n — recurrence state vector containing the latest r scalar terms
- F — total single-valued state rule that shifts left and appends the new term





## Intuition, definition, and misconceptions

Order fixes the state width and required initial-value count.

Coefficients align from oldest a_(n−r) to newest a_(n−1).

Forward generation shifts left and appends the new term; unique prefixes do not establish analytic behavior.

Do not reverse coefficients, give one initial value for an order-two rule and claim uniqueness, or treat a guessed closed form as a proof.





## Adopted derivation guide

[An oldest-to-newest order-two recurrence trace](https://ocme.evemisslab.com/en/derivations/derivation-mko-recurrence-relation-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Sequence](https://ocme.evemisslab.com/en/mko/mko-sequence/) — Terms have an explicit index.
- [Equation](https://ocme.evemisslab.com/en/mko/mko-equation/) — The update is an equality.
- [Function mapping](https://ocme.evemisslab.com/en/mko/mko-function-mapping/) — The rule is total and single-valued.





## Verification boundary

Only explicitly specified finite-step exact integer models are handled.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.





## Next obligation

Add Catalan numbers and generating functions.





## Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/recurrence-relation.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-recurrence-relation/index.md)