Recurrence relation

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

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Sequence — Terms have an explicit index.
• Equation — The update is an equality.
• 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.