Recurrence Relation Ontology

FLOW ALGEBRA
TITLE: Recurrence Relation Ontology
DOMAIN: Discrete Mathematics / Combinatorics
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/combinatorics/recurrence-relation-ontology.html
VERSION: 1.0
DATE: 2026-10-11
AUTHORS: Mark Higgins — Sky (Recursive AI)
PROJECT: Kireth Semantic Library | https://kirethresearch.org
SOURCE_STATUS: Mathematical synthesis; live webpage content not independently verified.

1. ONTOLOGY
ontology RecurrenceRelationOntology extends CombinatoricsOntology
  purpose: represent recursively defined sequences, initial conditions, solution methods and validation.

2. TYPED ENTITIES
entity Sequence { index_set: subset(Integer); codomain: Set; term: index -> codomain }
entity RecurrenceRelation { order: PositiveInteger; expression: Equation; domain: IndexSet }
entity InitialCondition { index: Integer; value: Scalar }
entity LinearRecurrence { coefficients: Sequence(Scalar); forcing_term: Sequence(Scalar) }
entity HomogeneousRecurrence extends LinearRecurrence { forcing_term: ZeroSequence }
entity NonHomogeneousRecurrence extends LinearRecurrence
entity CharacteristicPolynomial { coefficients: Sequence(Scalar); roots: Multiset(Complex) }
entity ClosedForm { expression: Function; domain: IndexSet }
entity GeneratingFunction { formal_series: FormalPowerSeries }
entity SolutionCertificate { recurrence_check: Boolean; initial_check: Boolean; assumptions: Set }

3. CORE RELATIONSHIPS
RecurrenceRelation --defines_terms_of--> Sequence
RecurrenceRelation --requires--> InitialCondition
LinearRecurrence --has_coefficients--> Scalar
HomogeneousRecurrence --specialises--> LinearRecurrence
CharacteristicPolynomial --derived_from--> ConstantCoefficientHomogeneousRecurrence
GeneratingFunction --encodes--> Sequence
ClosedForm --solves--> RecurrenceRelation
SolutionCertificate --validates--> ClosedForm

4. FORMAL SEMANTICS
flow RecurrenceDefinition:
  input: sequence a, integer k >= 1, index n >= n0 + k
  rule: a[n] = F(n, a[n-1], ..., a[n-k])
  require: all referenced terms are defined and F maps inputs to the sequence codomain
  output: recursively determined term a[n]

flow InitialValueProblem:
  input: recurrence of order k, values a[n0] ... a[n0+k-1]
  require: F is single-valued and defined for all subsequent steps
  output: unique forward sequence on the valid index domain

flow LinearRecurrence:
  input: coefficients c[1] ... c[k], forcing term g[n]
  rule: a[n] = SUM(i=1..k, c[i]*a[n-i]) + g[n]
  note: coefficients may depend on n in general; constant-coefficient methods require constants

5. ALGEBRAIC OPERATIONS
operation FORWARD_EVALUATE(recurrence, initial_values, target_index)
  require: sufficient initial conditions and a well-defined recurrence
  output: computed sequence term

operation CHARACTERISTIC_SOLVE(recurrence)
  require: homogeneous linear recurrence with constant coefficients
  construct: p(r) = r^k - c[1]*r^(k-1) - ... - c[k]
  rule: root r of multiplicity m contributes (b[0] + ... + b[m-1]*n^(m-1))*r^n
  output: general solution; constants fixed by initial conditions

operation GENERATING_FUNCTION_SOLVE(recurrence, initial_values)
  input: A(x) = SUM(n>=0, a[n]*x^n)
  method: translate recurrence into formal power series identity
  output: generating function and coefficients where derivable

operation VERIFY_SOLUTION(candidate, recurrence, initial_values)
  check: candidate satisfies recurrence at every required index
  check: candidate matches all initial conditions
  output: SolutionCertificate

6. MATHEMATICAL LAWS AND EXAMPLES
law Fibonacci: F[0]=0; F[1]=1; F[n]=F[n-1]+F[n-2] for n>=2
law Geometric: a[n]=r*a[n-1], a[0]=a0 => a[n]=a0*r^n for n>=0
law Arithmetic: a[n]=a[n-1]+d, a[0]=a0 => a[n]=a0+n*d
law CharacteristicRoots: a[n]=p*a[n-1]+q*a[n-2] => r^2-p*r-q=0
law Superposition: solutions of a homogeneous linear recurrence form a vector space over the coefficient field
law ParticularPlusHomogeneous: general nonhomogeneous solution = one particular solution + general homogeneous solution
law FormalSeriesFibonacci: A(x)=x/(1-x-x^2) for Fibonacci sequence with F[0]=0, F[1]=1

7. INFERENCE RULES
rule UNIQUE_FORWARD:
  if recurrence is deterministic, total on subsequent inputs, and k consecutive starting values exist
  then one unique forward sequence exists

rule CONSTANT_COEFFICIENT:
  if recurrence is homogeneous linear with constant coefficients
  then characteristic polynomial solution methods apply

rule VERIFY_INDUCTION:
  if candidate matches base values and recurrence preserves candidate formula
  then candidate formula holds at all subsequent valid indices

rule GROWTH_CAUTION:
  if characteristic roots are complex or repeated
  then account for modulus, oscillation and polynomial multiplicity factors

8. VALIDATION
constraint ORDER_POSITIVE: recurrence.order >= 1
constraint INITIAL_SUFFICIENCY: supply k consecutive initial values for order-k forward recurrence
constraint INDEX_VALIDITY: no reference to undefined sequence indices
constraint TYPE_COMPATIBILITY: operations preserve declared codomain
constraint SOLUTION_CORRECTNESS: validate both recurrence equation and initial conditions
constraint NONLINEAR_CAUTION: do not apply linear characteristic polynomial methods to nonlinear recurrences
constraint ASYMPTOTIC_CAUTION: growth statements require root and cancellation assumptions

9. SEMANTIC_EQUIVALENCE
semantic_equivalence "recurrence relation" <-> "recursive sequence equation" [context: sequence mathematics]
semantic_equivalence "linear recurrence sequence" <-> "linearly recurrent sequence" [context: linear recurrence]
semantic_difference "recurrence relation" != "closed-form expression"
semantic_difference "homogeneous recurrence" != "nonhomogeneous recurrence"
semantic_difference "recurrence relation" != "recursive algorithm" [related but not identical]

10. CONFIDENCE
confidence mathematical_definitions: 1.00
confidence standard_identities: 1.00
confidence source_page_alignment: unverified
confidence application_specific_inferences: require validation

11. FLOW_HASH
flow_hash:
  algorithm: SHA-256
  canonicalisation: UTF-8; LF line endings; exclude FLOW_HASH value from digest
  value: COMPUTE_ON_PUBLICATION
  purpose: integrity and change detection; not a claim of precomputed verification

12. UPDATE_MODEL
update_model:
  trigger: new recurrence class, revised definition, corrected identity, or source-page revision
  actions: revalidate formulas; revise dependencies; increment version; recompute FLOW_HASH
  preserve: source URL, provenance, revision history

13. AI_CONSUMPTION
ai_consumption:
  parse: typed entities, relationships, preconditions and mathematical laws
  reasoning: select methods only when preconditions hold
  execution: evaluate terms; derive candidates; verify against initial conditions
  retrieval: connect to combinatorics, generating functions, sequences, induction and algorithms
  safety: distinguish formal identities from heuristic or numerical approximations
  provenance: cite source URL and mark webpage alignment unverified

END FLOW ALGEBRA