Alphabeta MathLinear Recurrences and Rational Generating Functions
About this page
How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
✓ 23 results · all verified · 14 also independently AI-judged
Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 9 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.
1 · Prerequisites
Abstract Algebra
- Binary Operations, Monoids, Groups and Subgroups
- Divisibility, Euclidean Domains, Principal Ideal Domains and Unique Factorisation
- Group Actions, Orbits, Stabilisers and Cayley's Theorem
- Ideals, Quotient Rings and the Isomorphism Theorems for Rings
- Polynomial Rings, the Division Algorithm and Roots
- Rings, Subrings, Integral Domains and Fields
- Simple Field Extensions and the Construction of the Complex Numbers
- Splitting Fields
- The Field of Fractions and Localisation
Linear Algebra
- Determinants of Matrices over a Commutative Ring
- Eigenvalues, Eigenvectors and the Characteristic Polynomial
- Linear Independence, Bases and Dimension
- Linear Transformations, Rank-Nullity and Quotient Spaces
- Matrices, the Matrix of a Linear Map, and Change of Basis
- The Determinant of a Linear Operator, Cofactors and Cramer's Rule
- Vector Spaces, Linear Subspaces, Span and Direct Sums
Real Analysis
2 · Logical flowchart
3 · Items
Definition
Constant-coefficient linear recurrences, their starting index and their characteristic polynomial
Definition
Rational formal power series, proper presentations and reduced denominators
Lemma
The initial-value, recurrence-sequence, numerator and fixed-denominator rational-series spaces all have dimension d
Theorem
A coefficient sequence is eventually linearly recurrent if and only if its formal generating function is rational
Corollary
d initial values determine a sequence satisfying a fixed order-d recurrence
Corollary
The least eventual recurrence order is the degree of the reduced denominator
Proposition
Changing finitely many coefficients preserves rationality and eventual linear recurrence
Proposition
For a bi-infinite linear recurrence over K, the two half-series satisfy F_+(x)=-F_-(x⁻¹) in K(x)
Proposition
Rational formal power series are closed under sums and Cauchy products
Theorem
The Hadamard product of two rational formal power series over a field is rational
Remark
Reciprocal-root convention: χ(t)=∏ᵢ(t-λᵢ)^mᵢ corresponds to Q(x)=∏ᵢ(1-λᵢ x)^mᵢ
Lemma
A proper rational function with split denominator has a unique repeated-pole partial-fraction expansion
Lemma
Repeated poles expand formally as (1-λ x)⁻ʲ=∑_n≥0C(n+j-1, j-1)λⁿ xⁿ
Theorem
Over a named splitting field in characteristic zero, repeated characteristic roots give polynomial-times-exponential closed forms
Definition
The row-shift companion matrix of a linear recurrence
Proposition
The companion matrix advances the recurrence state vector by one step
Theorem
A recurrence companion matrix has the recurrence characteristic polynomial
Corollary
For an invertible matrix over a field, Cayley-Hamilton makes every matrix-power entry and trace sequence linearly recurrent
Definition
The Fibonacci sequence F₀=0,F₁=1 and Lucas sequence L₀=2,L₁=1
Definition
The trace of a square matrix over a commutative ring
Proposition
For matrices over a field, the commutative-ring trace agrees with the published matrix trace
Definition
Finite weighted directed multigraphs, weighted walks and their transfer matrices
Theorem
The (u,v) entry of Aⁿ is the total weight of length-n walks from u to v
Lemma
Formally, (I-xA)⁻¹=∑_n≥0Aⁿ xⁿ over every commutative coefficient ring
Theorem
Transfer-matrix theorem: weighted-walk generating functions are cofactors of I-xA divided by det(I-xA)
Lemma
d/dx det(I-xA)=-tr(adj(I-xA)A)
Corollary
Closed walks have trace and logarithmic-derivative generating functions
Corollary
Let K be a field, p≥1, and A∈ Mₚ(K). If χ_A(t)=∏_i<p(t-λᵢ) in K[t], then the transfer-matrix trace series is ∑_i<p(1-λᵢ x)⁻¹
Definition
Finite words, contiguous factors, avoidance and proper-prefix states
Definition
The longest-suffix prefix automaton for a finite set of forbidden factors
Theorem
Words over a finite alphabet avoiding finitely many nonempty factors have a rational length generating function
Corollary
Binary words avoiding any fixed nonempty factor have a rational length generating function
Sources
- R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Sections 4.1-4.2
- B. E. Sagan, Combinatorics: The Art of Counting, Section 3.7
- M. Waldschmidt, Linear Recurrence Sequences VI, slides 5-18
- R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Section 4.1
- B. E. Sagan, Combinatorics: The Art of Counting, Sections 3.6-3.7
- R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Theorem 4.1.1
- R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Theorem 4.1.1 and Proposition 4.2.2
- B. E. Sagan, Combinatorics: The Art of Counting, Theorem 3.7.1
- M. Waldschmidt, Linear Recurrence Sequences VI, slides 5-6
- R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Corollary 4.2.1
- M. Waldschmidt, Linear Recurrence Sequences VI, Order of a linear recurrence sequence
- R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Proposition 4.2.2
- M. Waldschmidt, Linear Recurrence Sequences VI, ultimately recurrent sequences
- R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Proposition 4.2.3 and Corollary 4.2.4
- R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Section 4.2
- R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Proposition 4.2.5
- M. Waldschmidt, Linear Recurrence Sequences VI, reciprocal characteristic polynomial
- M. Waldschmidt, Linear Recurrence Sequences VI, slides 19-28
- M. Waldschmidt, Linear Recurrence Sequences VI, slides 16-18
- M. Waldschmidt, Linear Recurrence Sequences VI, slide 17
- H. Pinkham, Linear Algebra, Chapter 10
- M. Waldschmidt, Linear Recurrence Sequences VI, slide 18
- R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Examples 4.1.2 and 4.7.16
- R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Section 4.7
- S. Axler, Linear Algebra Done Right, 4th ed., Definition 8.47
- R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Section 4.7.1
- R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Theorem 4.7.1
- R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Theorem 4.7.2
- J. Gallier and J. Quaintance, Linear Algebra for Computer Vision, Robotics, and Machine Learning, Section 6.4
- R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Corollary 4.7.3
- R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Corollaries 4.7.3-4.7.4
- H. Pinkham, Linear Algebra, Section 12.3
- R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Example 4.7.7 and Proposition 4.7.8
- R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Proposition 4.7.8