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.

Linear Recurrences and Rational Generating Functions

1 · Prerequisites

2 · Summary

Formal power series over a commutative ring, coefficient extraction with its linearity and extensionality, the unit criterion for a formal power series, and the formal derivative with its algebra are published. So are matrices over a commutative ring and their arithmetic, the determinant, Laplace cofactor expansion, minors, cofactors and the adjugate with the adjugate identity, the characteristic polynomial of a matrix and of an operator, the Cayley–Hamilton theorem, the spectral mapping theorem for polynomials, the trace as the sum of the eigenvalues, polynomial division over a field with Bézout's identity and unique factorisation, splitting fields, and the rational function field as a field of fractions.

A constant-coefficient linear recurrence and a rational generating function describe the same object: for a fixed denominator the initial-value, recurrence-sequence, numerator and rational-series spaces are linearly isomorphic, and no root is chosen. Reduced denominators give the minimal order, finite modification preserves eventual recurrence and rationality, rational series are closed under sums, products and Hadamard products, and over a splitting field partial fractions with the repeated-pole binomial series give the polynomial-times-exponential closed form. Companion matrices and Cayley–Hamilton connect the recurrence and matrix pictures. A finite weighted digraph makes walks entries of transfer-matrix powers; the formal matrix geometric series presents the walk series as a cofactor over $\det (I - x A)$ , trace and logarithmic-derivative formulas follow, and prefix automata make the generating function of words avoiding finitely many factors rational.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Constant-coefficient linear recurrences, their starting index and their characteristic polynomial

Definition

Let $K$ be a field, let $a = (a_{n})_{n \geq 0}$ be a sequence in $K$ , and let $d \geq 1$ . A constant-coefficient linear recurrence of order $d$ starting at $N$ is an identity

$a_{n + d} + c_{1} a_{n + d - 1} + \dots + c_{d} a_{n} = 0 (n \geq N),$

where $c_{1}, \dots, c_{d} \in K$ and $c_{d} \neq 0$ . Its characteristic polynomial and reciprocal denominator are

$χ (t) = t^{d} + c_{1} t^{d - 1} + \dots + c_{d}, Q (x) = 1 + c_{1} x + \dots + c_{d} x^{d} .$

The recurrence holds from the start when $N = 0$ , and it is eventual when such an $N$ exists. An order-zero recurrence starting at $N$ means $a_{n} = 0$ for every $n \geq N$ ; its characteristic polynomial and reciprocal denominator are both $1$ . This convention makes finitely supported sequences precisely the sequences of eventual order zero.

For a bi-infinite sequence $a : Z \to K$ , the same displayed identity is a recurrence of order $d$ when it holds for every $n \in Z$ . The condition $c_{d} \neq 0$ then lets the identity be solved both forward and backward.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Rational formal power series, proper presentations and reduced denominators

Definition

Let $R$ be a commutative ring. A formal power series $F \in R ⟦ x ⟧$ (Formal power series over a commutative ring and the coefficient-extraction functional $[x^{n}]$ ) is rational if there are polynomials $P, Q \in R [x]$ such that $Q (0)$ is a unit and

$Q F = P$

in $R ⟦ x ⟧$ . Equivalently, $F = P / Q$ , where $Q^{- 1}$ is the unique formal inverse supplied by A formal power series is a unit exactly when its constant coefficient is a unit.

Now let $R = K$ be a field. Multiplying numerator and denominator by $Q (0)^{- 1}$ gives a normalised presentation with $Q (0) = 1$ . Such a presentation is proper when $P = 0$ or $d e g P < \deg Q$ (Degree, leading coefficient and monic polynomial, with the zero polynomial having no degree). It is reduced when $P$ and $Q$ have no common nonunit factor. A polynomial series has the reduced presentation $P / 1$ , and the zero series has reduced presentation $0 / 1$ .

A polynomial $Q$ occurring in a normalised reduced presentation is called a reduced denominator of $F$ . The minimal-order theorem will show that all reduced denominators of one series have the same degree.

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

The initial-value, recurrence-sequence, numerator and fixed-denominator rational-series spaces all have dimension $d$

Statement

Let $K$ be a field, let $d \geq 1$ , let $c_{1}, \dots, c_{d} \in K$ with $c_{d} \neq 0$ , and put $Q (x) = 1 + c_{1} x + \dots + c_{d} x^{d}$ . The following four $K$ -vector spaces are naturally linearly isomorphic:

the initial-value space $K^{d}$ ;
the space of sequences satisfying $a_{n + d} + c_{1} a_{n + d - 1} + \dots + c_{d} a_{n} = 0$ for every $n \geq 0$ ;
the space of polynomials $P$ with $P = 0$ or $\deg P < d$ ;
the space of formal series $P / Q$ with $P = 0$ or $\deg P < d$ .

Each space has dimension $d$ .

Facts & Assumptions

Given: A field $K$ , a positive order $d$ , coefficients $c_{1}, \dots, c_{d}$ with $c_{d} \neq 0$ , and $Q (x) = 1 + c_{1} x + \dots + c_{d} x^{d}$ .

[L1]

An order- $d$ recurrence from the start is $a_{n + d} + c_{1} a_{n + d - 1} + \dots + c_{d} a_{n} = 0$ for every $n \geq 0$ (Constant-coefficient linear recurrences, their starting index and their characteristic polynomial).

[L2]

A proper fixed-denominator series has the form $P / Q$ with $Q (0) = 1$ and either $P = 0$ or $\deg P < \deg Q$ (Rational formal power series, proper presentations and reduced denominators).

[L3]

Formal series are equal exactly when all their coefficients agree, and $[x^{n}] (Q F) = \sum_{i = 0}^{n} [x^{i}] Q [x^{n - i}] F$ (Coefficient extraction is $R$ -linear, separates formal series, shifts under multiplication by $x^{k}$ , and converts products to finite convolution).

[L4]

The standard unit vectors form a basis of $K^{d}$ , so $\dim_{K} K^{d} = d$ , including the zero-dimensional boundary (The standard list $e : n \to F^{n}$ with $e_{i} (i) = 1_{F}$ and $e_{i} (j) = 0_{F}$ for $j \neq i$ is an ordered basis of $F^{n}$ ; hence $\dim_{F} F^{n} = n$ , and $F^{0}$ is the zero space with basis $\emptyset$ and dimension $0$ ).

Proof

technique · direct

1.1givenL1construct

Given $(u_{0}, \dots, u_{d - 1}) \in K^{d}$ , set $a_{i} = u_{i}$ for $i < d$ and recursively define $a_{n + d} = - (c_{1} a_{n + d - 1} + \dots + c_{d} a_{n})$ ; this produces exactly one recurrence sequence with those initial values.

1.2L1L3

For a recurrence sequence with $F = \sum_{n \geq 0} a_{n} x^{n}$ , [L3] gives $[x^{m}] (Q F) = a_{m} + c_{1} a_{m - 1} + \dots + c_{d} a_{m - d}$ for $m \geq d$ , so every such coefficient is zero by [L1] and $P : = Q F$ has degree below $d$ or is zero.

1.3L2

Because $Q (0) = 1$ , division by $Q$ is defined formally, and $P \mapsto P / Q$ is a linear bijection from the numerator space to the proper fixed-denominator series space.

2.1step 1.1algebra

Initial-value extraction is linear, and step 1.1 is its linear inverse; hence the initial-value and recurrence-sequence spaces are linearly isomorphic.

2.2step 1.2L3

Conversely, if $P = Q F$ has no nonzero coefficient in degrees $m \geq d$ , the same coefficient identity read backwards gives the recurrence for every $n = m - d \geq 0$ ; thus $F \mapsto Q F$ is a linear bijection from the recurrence-sequence space to the degree- $< d$ numerator space.

3.1step 2.1step 2.2step 1.3L4∎

Coefficient extraction identifies the numerator space with $K^{d}$ , and [L4] gives its dimension $d$ ; the linear isomorphisms in steps 2.1, 2.2 and 1.3 therefore give dimension $d$ for all four spaces.

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

A coefficient sequence is eventually linearly recurrent if and only if its formal generating function is rational

Statement

Let $K$ be a field, let $a = (a_{n})_{n \geq 0}$ be a sequence in $K$ , and let $F (x) = \sum_{n \geq 0} a_{n} x^{n}$ . Then $a$ satisfies an eventual constant-coefficient linear recurrence if and only if $F$ is a rational formal power series.

More precisely, let $Q (x) = 1 + c_{1} x + \dots + c_{d} x^{d}$ with $d \geq 1$ and $c_{d} \neq 0$ . The sequence satisfies the corresponding recurrence from index $N$ exactly when $Q F$ has no nonzero coefficient of degree at least $N + d$ . In particular, the recurrence starts at zero exactly when $Q F$ is zero or has degree below $d$ .

Facts & Assumptions

Given: A field $K$ , a sequence $a = (a_{n})_{n \geq 0}$ , and its formal generating function $F = \sum_{n \geq 0} a_{n} x^{n}$ .

[L1]

For fixed $Q (x) = 1 + c_{1} x + \dots + c_{d} x^{d}$ with $d \geq 1$ and $c_{d} \neq 0$ , multiplication by $Q$ identifies sequences recurrent from zero with numerators of degree below $d$ (The initial-value, recurrence-sequence, numerator and fixed-denominator rational-series spaces all have dimension $d$ ).

[L2]

If $0 \neq Q \in K [x]$ and $P \in K [x]$ , there are unique $D, R \in K [x]$ with $P = D Q + R$ and either $R = 0$ or $\deg R < \deg Q$ (Division algorithm for polynomials over a field).

Proof

technique · direct

1.1givenL1algebra

Suppose first that $a$ satisfies an order- $d$ recurrence from index $N$ . For $m \geq N + d$ , coefficient extraction gives $[x^{m}] (Q F) = a_{m} + c_{1} a_{m - 1} + \dots + c_{d} a_{m - d} = 0$ , so $Q F$ is a polynomial and $F = (Q F) / Q$ is rational.

1.2given

An eventual order-zero recurrence means that $a$ is eventually zero, so $F$ is a polynomial and is rational with denominator $1$ .

1.3givenL2algebra

Conversely, suppose $F = P / Q$ with $Q (0) \neq 0$ . Rescale so that $Q (0) = 1$ , and use [L2] to write $P = D Q + R$ with $R = 0$ or $\deg R < \deg Q$ ; then $F = D + R / Q$ .

2.1step 1.3L1

If $\deg Q = d \geq 1$ , [L1] says that the coefficients of $R / Q$ satisfy the order- $d$ recurrence from zero, while the polynomial $D$ changes only finitely many coefficients; hence the coefficients of $F$ satisfy that recurrence eventually. If $Q = 1$ , then $F = P$ is eventually zero and has eventual order zero.

3.1step 1.1step 2.1algebra∎

The coefficient calculation in step 1.1 is reversible: for fixed positive-degree $Q$ , the recurrence holds at $n$ exactly when $[x^{n + d}] (Q F) = 0$ . This gives the stated starting-index clause and completes both directions.

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

$d$ initial values determine a sequence satisfying a fixed order- $d$ recurrence

Statement

Fix a field $K$ , an integer $d \geq 1$ , and coefficients $c_{1}, \dots, c_{d} \in K$ with $c_{d} \neq 0$ . For every initial list $(u_{0}, \dots, u_{d - 1}) \in K^{d}$ , there is exactly one sequence $(a_{n})_{n \geq 0}$ satisfying

$a_{n + d} + c_{1} a_{n + d - 1} + \dots + c_{d} a_{n} = 0 (n \geq 0)$

and $a_{i} = u_{i}$ for $i < d$ .

Facts & Assumptions

Given: A field $K$ , a positive order $d$ , fixed recurrence coefficients with nonzero trailing coefficient, and an initial list in $K^{d}$ .

[L1]

Initial-value extraction is a linear isomorphism from the fixed-recurrence sequence space to $K^{d}$ (The initial-value, recurrence-sequence, numerator and fixed-denominator rational-series spaces all have dimension $d$ ).

Proof

technique · direct

1.1givenL1

Surjectivity in [L1] gives a recurrence sequence with the prescribed $d$ initial values.

2.1step 1.1L1∎

Injectivity in [L1] says that two recurrence sequences with the same initial list are equal, proving uniqueness. This includes $d = 1$ , where one initial value determines every later term.

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

The least eventual recurrence order is the degree of the reduced denominator

Statement

Let $F = \sum_{n \geq 0} a_{n} x^{n} \in K ⟦ x ⟧$ be rational over a field, and let $P / Q$ be a normalised reduced presentation. The least order of an eventual constant-coefficient recurrence satisfied by $(a_{n})$ is $\deg Q$ , with the convention that $\deg 1 = 0$ . Thus polynomial series have minimal eventual order zero.

Facts & Assumptions

Given: A rational series $F = P / Q$ over a field $K$ , where $Q (0) = 1$ and $P, Q$ are coprime.

[L1]

A sequence is eventually linearly recurrent exactly when its generating function is rational, and a denominator $D$ of degree $e$ supplies an eventual recurrence of order $e$ (A coefficient sequence is eventually linearly recurrent if and only if its formal generating function is rational).

[L2]

The polynomial ring over a field is a unique factorisation domain (For every field $F$ , $F [x]$ is a unique factorisation domain).

Proof

technique · direct

1.1givenL1

If $(a_{n})$ satisfies an eventual recurrence of order $e$ , [L1] gives a polynomial $A$ and a normalised denominator $D$ of degree $e$ with $F = A / D$ , so $P D = A Q$ .

2.1step 1.1L2algebra

Since $P$ and $Q$ are coprime in the UFD $K [x]$ , the identity $P D = A Q$ forces $Q ∣ D$ ; therefore $\deg Q \leq e$ .

3.1step 2.1L1∎

If $\deg Q > 0$ , the presentation $P / Q$ itself gives by [L1] an eventual recurrence of order $\deg Q$ , so step 2.1 proves minimality. If $Q = 1$ , then $F = P$ is a polynomial and its coefficients are eventually zero, giving minimal order zero.

PropositionStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Changing finitely many coefficients preserves rationality and eventual linear recurrence

Statement

Let $(a_{n})$ and $(b_{n})$ be sequences over a field which differ at only finitely many indices. Then the generating series $\sum a_{n} x^{n}$ is rational if and only if $\sum b_{n} x^{n}$ is rational. Equivalently, $(a_{n})$ is eventually linearly recurrent if and only if $(b_{n})$ is eventually linearly recurrent.

A finite modification need not preserve a recurrence with starting index zero.

Facts & Assumptions

Given: Two sequences $(a_{n})$ and $(b_{n})$ over a field which differ at only finitely many indices.

[L1]

A coefficient sequence is eventually linearly recurrent if and only if its formal generating function is rational (A coefficient sequence is eventually linearly recurrent if and only if its formal generating function is rational).

Proof

technique · direct

1.1given

The difference $H (x) = \sum_{n \geq 0} (a_{n} - b_{n}) x^{n}$ has finite support, so it is a polynomial.

2.1step 1.1algebra

If $A (x) = \sum a_{n} x^{n} = P / Q$ is rational, then $B (x) = A (x) - H (x) = (P - H Q) / Q$ is rational; the same argument with $A = B + H$ proves the converse.

3.1step 2.1L1

Applying [L1] to both series converts step 2.1 into the equivalence of eventual recurrence.

4.1step 3.1∎

For the final warning, the zero sequence satisfies $a_{n + 1} + a_{n} = 0$ from zero, while changing only $a_{0}$ to $1$ destroys that identity at $n = 0$ , even though the modified sequence is eventually zero.

PropositionStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

For a bi-infinite linear recurrence over $K$ , the two half-series satisfy $F_{+} (x) = - F_{-} (x^{- 1})$ in $K (x)$

Statement

Let $K$ be a field, let $d \geq 1$ , and let $f : Z \to K$ satisfy

$f (n + d) + c_{1} f (n + d - 1) + \dots + c_{d} f (n) = 0 (n \in Z),$

where $c_{d} \neq 0$ . Put

$F_{+} (x) = \sum_{n \geq 0} f (n) x^{n}, F_{-} (x) = \sum_{n \geq 1} f (- n) x^{n} .$

Both series are rational, and in the rational function field $K (x)$ ,

$F_{+} (x) = - F_{-} (x^{- 1}) .$

More precisely, write $F_{+} = P / Q$ with $Q = 1 + c_{1} x + \dots + c_{d} x^{d}$ , $P = \sum_{j < d} β_{j} x^{j}$ , and $P \neq 0$ . If

$r = \min {n \geq 0 : f (n) \neq 0}, s = \min {n \geq 1 : f (- n) \neq 0},$

then $r = \min {j \geq 0 : β_{j} \neq 0}$ and $f (r) = β_{r}$ , while $s = d - \deg P$ and $f (- s) = - c_{d}^{- 1} β_{d - s}$ . Finally,

$F_{+} (x) = \pm x^{r - s} F_{+} (x^{- 1})$

holds exactly when $f (n) = \mp f (- n + r - s)$ for every $n \in Z$ . If $P = 0$ , the recurrence and $c_{d} \neq 0$ force $f = 0$ , so the main identity holds and the minima are intentionally left undefined.

Facts & Assumptions

Given: A field $K$ and a bi-infinite order- $d$ recurrence with nonzero trailing coefficient.

[L1]

An eventual recurrence has a rational generating function, and a recurrence from zero with reciprocal denominator $Q$ gives a numerator of degree below $d$ (A coefficient sequence is eventually linearly recurrent if and only if its formal generating function is rational).

[L2]

The fraction field of $K [x]$ is the rational function field $K (x) = {P / Q : P, Q \in K [x], Q \neq 0}$ (For a field $F$ , $F (t) = Frac (F [t])$ is its rational function field; in particular $R (t) = Frac (R [t])$ ).

Proof

technique · direct

1.1givenL1

Applying [L1] to the positive half gives $F_{+} = P / Q$ with $\deg P < d$ , and applying it to the reversed negative half gives rationality of $F_{-}$ .

2.1givenstep 1.1algebra

In the vector space of all formal sums $\sum_{n \in Z} a_{n} x^{n}$ , multiplication by the polynomial $Q$ is coefficientwise finite. The recurrence says $Q \sum_{n \in Z} f (n) x^{n} = 0$ , so linearity gives $Q (x) \sum_{n \geq 1} f (- n) x^{- n} = - Q (x) F_{+} (x) = - P (x)$ .

2.2step 1.1algebra

The lowest nonzero coefficient of $P / Q$ equals the lowest nonzero coefficient of $P$ , because $Q (0) = 1$ ; hence the positive minimum is $r = \min {j : β_{j} \neq 0}$ and $f (r) = β_{r}$ .

3.1step 2.1L2algebra

Substitute $x^{- 1}$ for $x$ in step 2.1 and interpret both quotients in [L2]; this gives $F_{+} (x) = - F_{-} (x^{- 1})$ in $K (x)$ , not as an equality of formal power series.

4.1step 3.1algebra

Rewriting $- P (x^{- 1}) / Q (x^{- 1})$ as $- c_{d}^{- 1} x^{d} P (x^{- 1}) / (1 + c_{d}^{- 1} c_{d - 1} x + \dots + c_{d}^{- 1} x^{d})$ shows that its first nonzero term has degree $s = d - \deg P$ and coefficient $- c_{d}^{- 1} β_{d - s}$ , proving the negative-side clauses.

5.1step 3.1step 2.2step 4.1algebra

Apply the main identity to replace $F_{+} (x^{- 1})$ by $- F_{-} (x)$ ; coefficient comparison then shows that $F_{+} (x) = \pm x^{r - s} F_{+} (x^{- 1})$ is equivalent to $f (n) = \mp f (- n + r - s)$ for every integer $n$ .

6.1step 1.1given∎

If $P = 0$ , then $F_{+} = 0$ , so $f (n) = 0$ for $n \geq 0$ ; solving the recurrence backwards using $c_{d} \neq 0$ gives $f (n) = 0$ for all $n \in Z$ , and the main identity remains valid.

PropositionStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

Rational formal power series are closed under sums and Cauchy products

Statement

Let $R$ be a commutative ring. If $F, G \in R ⟦ x ⟧$ are rational, then both $F + G$ and the Cauchy product $F G$ are rational. This includes zero series and polynomial presentations.

Facts & Assumptions

Given: Rational presentations $F = P_{1} / Q_{1}$ and $G = P_{2} / Q_{2}$ over a commutative ring $R$ .

[L1]

A rational formal series has a presentation $P / Q$ whose denominator has unit constant coefficient (Rational formal power series, proper presentations and reduced denominators).

[L2]

A formal series is a unit exactly when its constant coefficient is a unit (A formal power series is a unit exactly when its constant coefficient is a unit).

Proof

technique · direct

1.1givenL1L2

The product $Q_{1} Q_{2}$ has unit constant coefficient $Q_{1} (0) Q_{2} (0)$ , so it is a unit of $R ⟦ x ⟧$ by [L2].

2.1step 1.1L1algebra∎

The identities $F + G = (P_{1} Q_{2} + P_{2} Q_{1}) / (Q_{1} Q_{2})$ and $F G = P_{1} P_{2} / (Q_{1} Q_{2})$ have polynomial numerators and the denominator from step 1.1, so [L1] makes both series rational. The formulas remain valid when a numerator is zero or a denominator is $1$ .

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

The Hadamard product of two rational formal power series over a field is rational

Statement

Let $K$ be a field. If $F = \sum_{n \geq 0} a_{n} x^{n}$ and $G = \sum_{n \geq 0} b_{n} x^{n}$ are rational formal power series over $K$ , then their Hadamard product

$F * G : = \sum_{n \geq 0} a_{n} b_{n} x^{n}$

is rational.

Facts & Assumptions

Given: Rational series $F = \sum a_{n} x^{n}$ and $G = \sum b_{n} x^{n}$ over a field $K$ .

[L1]

A coefficient sequence has a rational generating function exactly when it is eventually linearly recurrent (A coefficient sequence is eventually linearly recurrent if and only if its formal generating function is rational).

[L2]

A linearly independent subset of a vector space spanned by $m$ vectors has at most $m$ elements (If $V$ has a spanning set with $n$ elements, then every linearly independent subset of $V$ is finite with at most $n$ elements; in particular $V$ has no linearly independent subset equinumerous with $N$ ).

Proof

technique · direct

1.1givenL1

By [L1], after deleting finite prefixes the sequences $a$ and $b$ satisfy recurrences of orders $d$ and $e$ . Hence all shifts of the first tail lie in the span of its first $d$ shifts, and all shifts of the second tail lie in the span of its first $e$ shifts.

2.1step 1.1L1

If $d = 0$ or $e = 0$ , one tail and hence the product tail is zero, so [L1] already proves rationality. It remains to take $d, e \geq 1$ .

3.1step 1.1step 2.1algebra

Let $W$ be the span, inside the vector space of $K$ -valued sequences, of the $d e$ coefficientwise products $(S^{i} a) (S^{j} b)$ with $0 \leq i < d$ and $0 \leq j < e$ . Every simultaneous shift $S^{k} (a_{n} b_{n}) = (S^{k} a) (S^{k} b)$ belongs to $W$ by bilinear expansion.

4.1step 3.1L2algebra

By [L2], among any $d e + 1$ simultaneous shifts of the product tail there is a nontrivial linear dependence. Remove initial and terminal zero coefficients from such a relation and normalise its last coefficient to $1$ ; the remaining first coefficient is nonzero and the relation is an eventual constant-coefficient recurrence for $(a_{n} b_{n})$ .

5.1step 1.1step 2.1step 4.1L1∎

Applying [L1] to the product sequence in step 4.1 proves that $F * G$ is rational in the positive-order case. Together with step 2.1, this covers all rational inputs, and finite prefixes discarded in step 1.1 do not affect eventual recurrence.

RemarkRemark: AI-adaptedProof: Not applicablejudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Reciprocal-root convention: $χ (t) = \prod_{i} (t - λ_{i})^{m_{i}}$ corresponds to $Q (x) = \prod_{i} (1 - λ_{i} x)^{m_{i}}$

Statement

The recurrence convention of Constant-coefficient linear recurrences, their starting index and their characteristic polynomial pairs

$χ (t) = t^{d} + c_{1} t^{d - 1} + \dots + c_{d}$

with $Q (x) = 1 + c_{1} x + \dots + c_{d} x^{d}$ . Therefore, in any field over which $χ$ splits,

$χ (t) = \prod_{i} (t - λ_{i})^{m_{i}} ⟺ Q (x) = \prod_{i} (1 - λ_{i} x)^{m_{i}} .$

The roots of $Q$ are the reciprocals $λ_{i}^{- 1}$ , while the numbers appearing in recurrence closed forms are the characteristic roots $λ_{i}$ . The nonzero trailing coefficient in the recurrence makes every $λ_{i}$ nonzero. This convention is algebraic and does not assert convergence of $P / Q$ at any value of $x$ (Rational formal power series, proper presentations and reduced denominators).

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

A proper rational function with split denominator has a unique repeated-pole partial-fraction expansion

Statement

Let $E$ be a field, let $λ_{1}, \dots, λ_{s} \in E$ be pairwise distinct and nonzero, let $m_{i} \geq 1$ , and put

$Q (x) = \prod_{i = 1}^{s} (1 - λ_{i} x)^{m_{i}} .$

For every $P \in E [x]$ with $P = 0$ or $\deg P < \deg Q$ , there are unique scalars $b_{i j} \in E$ such that

$\frac{P (x)}{Q (x)} = \sum_{i = 1}^{s} \sum_{j = 1}^{m_{i}} \frac{b_{i j}}{(1 - λ_{i} x)^{j}} .$

For $P = 0$ , every $b_{i j}$ is zero.

Facts & Assumptions

Given: A field $E$ , distinct nonzero $λ_{i}$ , positive multiplicities $m_{i}$ , and a proper numerator $P$ for $Q = \prod_{i} (1 - λ_{i} x)^{m_{i}}$ .

[L1]

A split recurrence denominator has factors $(1 - λ_{i} x)^{m_{i}}$ corresponding to the characteristic factors $(t - λ_{i})^{m_{i}}$ (Reciprocal-root convention: $χ (t) = \prod_{i} (t - λ_{i})^{m_{i}}$ corresponds to $Q (x) = \prod_{i} (1 - λ_{i} x)^{m_{i}}$ ).

[L2]

Coprime polynomials $f, g$ over a field admit $A, B$ with $A f + B g = 1$ (Bézout identity and the Euclidean algorithm for polynomials over a field).

[L3]

Splitting permits a factorisation into linear factors with repetitions recording multiplicity (Polynomials that split and splitting fields of a polynomial or a family of polynomials).

Proof

technique · direct

1.1givenL2L3

The powers $q_{i} = (1 - λ_{i} x)^{m_{i}}$ are pairwise coprime: distinct linear factors have no common root, and [L2] then gives a Bezout identity for every pair.

2.1step 1.1L2algebra

Iterating the two-factor Bezout decomposition gives polynomials $U_{i}$ with $\deg U_{i} < m_{i}$ such that $P / Q = \sum_{i} U_{i} / q_{i}$ ; at each stage the remainder modulo $q_{i}$ supplies $U_{i}$ .

3.1step 2.1algebra

Each $U_{i} / q_{i}$ has a unique expansion $\sum_{j = 1}^{m_{i}} b_{i j} (1 - λ_{i} x)^{- j}$ , because the polynomials $1, (1 - λ_{i} x), \dots, (1 - λ_{i} x)^{m_{i} - 1}$ form a basis of the polynomials of degree below $m_{i}$ .

4.1step 1.1step 3.1L2

If the displayed partial-fraction sum is zero, clear denominators and reduce modulo $q_{i}$ ; all terms except the $i$ th vanish, so $U_{i} \prod_{k \neq i} q_{k} \equiv 0 (m o d q_{i})$ . The second factor is invertible modulo $q_{i}$ by [L2], hence $U_{i} = 0$ for every $i$ , and step 3.1 gives every $b_{i j} = 0$ .

5.1step 2.1step 3.1step 4.1L1∎

Steps 2.1 and 3.1 give existence, while step 4.1 gives uniqueness. The zero numerator yields the all-zero coefficients.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Repeated poles expand formally as $(1 - λ x)^{- j} = \sum_{n \geq 0} (\binom{n + j - 1}{j - 1}) λ^{n} x^{n}$

Statement

Let $R$ be a commutative ring, let $λ \in R$ , and let $j \geq 1$ . In $R ⟦ x ⟧$ ,

$\frac{1}{(1 - λ x)^{j}} = \sum_{n \geq 0} (\binom{n + j - 1}{j - 1}) λ^{n} x^{n} .$

The binomial coefficient acts by repeated addition in $R$ . The formula includes $n = 0$ , $j = 1$ , and $λ = 0$ and is purely formal.

Facts & Assumptions

Given: A commutative ring $R$ , an element $λ \in R$ , and an integer $j \geq 1$ .

[L1]

A formal series is invertible exactly when its constant coefficient is a unit, and its inverse is unique (A formal power series is a unit exactly when its constant coefficient is a unit).

[L2]

The coefficient of a Cauchy product is $[x^{n}] (f g) = \sum_{i = 0}^{n} [x^{i}] f [x^{n - i}] g$ (Coefficient extraction is $R$ -linear, separates formal series, shifts under multiplication by $x^{k}$ , and converts products to finite convolution).

[L3]

Binomial coefficients count finite subsets and satisfy $(\binom{n}{0}) = 1$ , $(\binom{n}{n}) = 1$ , and $(\binom{n}{k}) = 0$ for $k > n$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ).

[L4]

The hockey-stick identity is $\sum_{i < n + 1} (\binom{i}{k}) = (\binom{n + 1}{k + 1})$ (Pascal's rule $(\binom{n + 1}{k + 1}) = (\binom{n}{k}) + (\binom{n}{k + 1})$ , and the hockey-stick identity $\sum_{i \leq n} (\binom{i}{k}) = (\binom{n + 1}{k + 1})$ ).

Proof

technique · induction

1.1baseL1L2L3

For $j = 1$ , put $G = \sum_{n \geq 0} λ^{n} x^{n}$ . By [L2], the constant coefficient of $(1 - λ x) G$ is $1$ and every positive coefficient is $λ^{n} - λ λ^{n - 1} = 0$ , so $G = (1 - λ x)^{- 1}$ by [L1]; this is the formula because $(\binom{n}{0}) = 1$ .

2.1ihstep 1.1L2

Assume the formula holds for one $j \geq 1$ . Multiplying its right-hand side by the $j = 1$ series from step 1.1, [L2] makes the coefficient of $x^{n}$ equal to $λ^{n} \sum_{k = 0}^{n} (\binom{k + j - 1}{j - 1})$ .

3.1step 2.1L3L4

Terms below $j - 1$ vanish by [L3], so [L4] changes the sum in step 2.1 to $(\binom{n + j}{j})$ ; therefore the product is the claimed series for exponent $j + 1$ .

4.1step 1.1step 3.1discharge-induction∎

The base case and induction step prove the formula for every $j \geq 1$ . At $n = 0$ the coefficient is $1$ , and at $λ = 0$ all positive coefficients vanish, so the stated boundaries are included.

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Over a named splitting field in characteristic zero, repeated characteristic roots give polynomial-times-exponential closed forms

Statement

Let $K$ be a field of characteristic zero, let $(a_{n})_{n \geq 0}$ satisfy an order- $d$ recurrence from zero, and let $E / K$ be a splitting field of its characteristic polynomial. If

$χ (t) = \prod_{i = 1}^{s} (t - λ_{i})^{m_{i}}$

in $E [t]$ , with distinct roots $λ_{i}$ , then there are unique polynomials $p_{i} \in E [z]$ with $\deg p_{i} < m_{i}$ such that

$a_{n} = \sum_{i = 1}^{s} p_{i} (n) λ_{i}^{n} (n \geq 0) .$

Conversely, every sequence of this form satisfies the recurrence whose characteristic polynomial is the displayed product. Equality is in $E$ , and no identification with $R$ or $C$ is assumed.

Facts & Assumptions

Given: A characteristic-zero field $K$ , a sequence satisfying a recurrence from zero, a named splitting field $E / K$ , and the displayed factorisation of its characteristic polynomial.

[L1]

A recurrence from zero has a proper rational generating function with its reciprocal denominator (A coefficient sequence is eventually linearly recurrent if and only if its formal generating function is rational).

[L2]

The factorisation $χ (t) = \prod_{i} (t - λ_{i})^{m_{i}}$ corresponds to $Q (x) = \prod_{i} (1 - λ_{i} x)^{m_{i}}$ (Reciprocal-root convention: $χ (t) = \prod_{i} (t - λ_{i})^{m_{i}}$ corresponds to $Q (x) = \prod_{i} (1 - λ_{i} x)^{m_{i}}$ ).

[L3]

A proper fraction with that split denominator has a unique expansion $\sum_{i, j} b_{i j} (1 - λ_{i} x)^{- j}$ (A proper rational function with split denominator has a unique repeated-pole partial-fraction expansion).

[L4]

Formally, $[x^{n}] (1 - λ x)^{- j} = (\binom{n + j - 1}{j - 1}) λ^{n}$ (Repeated poles expand formally as $(1 - λ x)^{- j} = \sum_{n \geq 0} (\binom{n + j - 1}{j - 1}) λ^{n} x^{n}$ ).

[L5]

A splitting field is generated by the roots over the base field, and repeated factors record their multiplicities (Polynomials that split and splitting fields of a polynomial or a family of polynomials).

[L6]

Characteristic zero means that no positive natural multiple of the field identity is zero (The characteristic of a ring: the least $n \geq 1$ with $n \cdot 1_{R} = 0$ when one exists, and $0$ otherwise).

[L7]

The binomial coefficient satisfies $(\binom{n}{k}) k! = n^{\underline{k}}$ when $k \leq n$ ( $(\binom{n}{k}) k! (n - k)! = n!$ for $k \leq n$ ; hence $(\binom{n}{k}) k! = n^{\underline{k}}$ , the quotient $n! / (k! (n - k)!)$ is a natural number, and $(\binom{n}{k}) = (\binom{n}{n - k})$ ).

Proof

technique · direct

1.1givenL1L2L5

By [L1] the generating function is $P / Q$ with $P = 0$ or $\deg P < d$ , and [L2] identifies $Q$ with the split product $\prod_{i} (1 - λ_{i} x)^{m_{i}}$ in $E [x]$ .

1.2L6L7algebra

By [L6], every positive factorial is nonzero and hence invertible in $E$ . For $1 \leq j \leq m$ put $q_{j} (z) = ((j - 1)!)^{- 1} (z + 1) (z + 2) \dots (z + j - 1) \in E [z]$ , the product being empty for $j = 1$ , so $q_{1} = 1$ . Each $q_{j}$ has degree $j - 1$ and leading coefficient $((j - 1)!)^{- 1} \neq 0$ , and for every natural $n$ the identity $(\binom{n + j - 1}{j - 1}) (j - 1)! = (n + j - 1)^{\underline{j - 1}} = (n + 1) \dots (n + j - 1)$ from [L7] gives $q_{j} (n) = (\binom{n + j - 1}{j - 1})$ . The degrees $0, \dots, m - 1$ are distinct, so triangular elimination makes $q_{1}, \dots, q_{m}$ a basis of the polynomials in $E [z]$ of degree below $m$ .

2.1step 1.2L1L2L4algebra

Conversely, expand each $p_{i}$ in the binomial-polynomial basis from step 1.2. Then [L4] shows that the generating function of $p_{i} (n) λ_{i}^{n}$ has denominator dividing $(1 - λ_{i} x)^{m_{i}}$ ; summing gives a rational function with denominator dividing $Q$ , so [L1] gives the recurrence with characteristic polynomial dividing the displayed product. Multiplying by any missing factors gives the displayed order- $d$ recurrence itself.

2.2step 1.1L3L4

Apply [L3] and then [L4] to obtain $a_{n} = \sum_{i = 1}^{s} \sum_{j = 1}^{m_{i}} b_{i j} (\binom{n + j - 1}{j - 1}) λ_{i}^{n}$ .

3.1step 2.2step 1.2L3

Step 1.2 rewrites each coefficient $(\binom{n + j - 1}{j - 1})$ as $q_{j} (n)$ , so grouping the terms of step 2.2 with the same $i$ gives $a_{n} = \sum_{i} p_{i} (n) λ_{i}^{n}$ with $p_{i} = \sum_{j = 1}^{m_{i}} b_{i j} q_{j}$ , a polynomial in $E [z]$ of degree below $m_{i}$ . Uniqueness follows from the uniqueness in [L3], the basis property in step 1.2, and coefficient extensionality.

4.1step 3.1step 2.1L2∎

Steps 3.1 and 2.1 prove both directions, including repeated roots and the case of one root. The condition $c_{d} \neq 0$ in the recurrence excludes zero among the $λ_{i}$ .

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

The row-shift companion matrix of a linear recurrence

Definition

Let $R$ be a commutative ring, let $d \geq 1$ , and let

$χ (t) = t^{d} + c_{1} t^{d - 1} + \dots + c_{d} .$

The row-shift companion matrix of this recurrence polynomial is the matrix $C \in M_{d} (R)$ (Finite rectangular matrices over a commutative ring, their entries, rows and columns) whose entries are

$C_{i, i + 1} = 1 (0 \leq i < d - 1), C_{d - 1, j} = - c_{d - j} (0 \leq j < d),$

with all other entries zero. Thus

$C = (\begin{array}{ccccc} 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & \dots & 1 \\ - c_{d} & - c_{d - 1} & - c_{d - 2} & \dots & - c_{1} \end{array}) .$

For a recurrence sequence $a$ , its state at time $n$ is the column vector $v_{n} = (a_{n}, a_{n + 1}, \dots, a_{n + d - 1})^{T}$ . This convention matches the signs and order in Constant-coefficient linear recurrences, their starting index and their characteristic polynomial.

PropositionStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

The companion matrix advances the recurrence state vector by one step

Statement

Let $a$ satisfy an order- $d$ recurrence from zero over a field, let $C$ be its row-shift companion matrix, and put $v_{n} = (a_{n}, \dots, a_{n + d - 1})^{T}$ . Then

$v_{n + 1} = C v_{n} and v_{n} = C^{n} v_{0}$

for every $n \geq 0$ .

Facts & Assumptions

Given: An order- $d$ recurrence sequence $a$ , its state vectors $v_{n}$ , and its companion matrix $C$ .

[L1]

The companion matrix has shift rows and final row $(- c_{d}, - c_{d - 1}, \dots, - c_{1})$ (The row-shift companion matrix of a linear recurrence).

[L2]

Matrix multiplication is $(A B)_{i k} = \sum_{j} a_{i j} b_{j k}$ , and $I_{d}$ is the identity matrix (Entrywise ring-matrix operations, rectangular matrix products, identity matrices and transpose).

[L3]

Matrix multiplication is associative and satisfies $I_{d} A = A = A I_{d}$ (Matrix arithmetic over a commutative ring is associative, unital and distributive, and transpose reverses products).

Proof

technique · induction

1.1givenL1L2

Multiplying $C$ by $v_{n}$ , the first $d - 1$ rows return $a_{n + 1}, \dots, a_{n + d - 1}$ and the final row returns $- c_{d} a_{n} - \dots - c_{1} a_{n + d - 1} = a_{n + d}$ , so $C v_{n} = v_{n + 1}$ .

1.2baseL2L3

At $n = 0$ , one has $C^{0} v_{0} = I_{d} v_{0} = v_{0}$ .

2.1ihstep 1.1L3

If $v_{n} = C^{n} v_{0}$ , then step 1.1 and associativity give $v_{n + 1} = C v_{n} = C^{n + 1} v_{0}$ .

3.1step 1.2step 2.1discharge-induction∎

Induction proves $v_{n} = C^{n} v_{0}$ for every $n \geq 0$ , together with the one-step identity from step 1.1.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

A recurrence companion matrix has the recurrence characteristic polynomial

Statement

Let $K$ be a field, let $d \geq 1$ , and let $C$ be the row-shift companion matrix associated with

$χ (t) = t^{d} + c_{1} t^{d - 1} + \dots + c_{d} .$

Then the matrix characteristic polynomial is exactly

$χ_{C} (t) = \det (t I_{d} - C) = t^{d} + c_{1} t^{d - 1} + \dots + c_{d} .$

Facts & Assumptions

Given: A positive integer $d$ , coefficients $c_{1}, \dots, c_{d}$ , and their row-shift companion matrix $C$ .

[L1]

The row-shift companion matrix has superdiagonal entries $1$ and final row $(- c_{d}, \dots, - c_{1})$ (The row-shift companion matrix of a linear recurrence).

[L2]

For a field matrix $A$ , its characteristic polynomial is $χ_{A} (t) = \det (t I - A)$ (For $A \in M_{n} (F)$ , the characteristic polynomial is $χ_{A} (x) = \det (x I_{n} - A)$ when $n \geq 1$ , with $χ_{A} (x) = 1$ for the unique $0 \times 0$ matrix).

[L3]

A determinant may be expanded along any row or column as the sum of entries times their cofactors (Laplace expansion computes the determinant along every row and every column over a commutative ring).

Proof

technique · induction

1.1baseL1L2

For $d = 1$ , one has $C = (- c_{1})$ and $\det (t I - C) = t + c_{1}$ .

1.2ihL1L2

Assume the formula for size $d - 1$ . In $t I_{d} - C$ , the first column has only two nonzero entries: $t$ in row $0$ and $c_{d}$ in row $d - 1$ .

2.1step 1.2L3

Expanding that column by [L3], the cofactor of $t$ is the size- $(d - 1)$ companion determinant $t^{d - 1} + c_{1} t^{d - 2} + \dots + c_{d - 1}$ by the induction hypothesis.

2.2step 1.2L3algebra

The minor of the entry $c_{d}$ is triangular with diagonal entries $- 1$ ; its determinant is $(- 1)^{d - 1}$ , and the cofactor sign is also $(- 1)^{d - 1}$ , so this contribution is $c_{d}$ .

3.1step 2.1step 2.2algebra

Therefore $\det (t I_{d} - C) = t (t^{d - 1} + c_{1} t^{d - 2} + \dots + c_{d - 1}) + c_{d}$ , which is the claimed polynomial.

4.1step 1.1step 3.1discharge-induction∎

The base case and induction step prove the formula for every $d \geq 1$ .

CorollaryStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

For an invertible matrix over a field, Cayley-Hamilton makes every matrix-power entry and trace sequence linearly recurrent

Statement

Let $K$ be a field, let $n \geq 1$ , and let $A \in M_{n} (K)$ be invertible. Write

$χ_{A} (t) = t^{n} + b_{1} t^{n - 1} + \dots + b_{n} .$

Then $b_{n} \neq 0$ , and for every pair $u, v < n$ the sequence $m \mapsto (A^{m})_{u v}$ , as well as the sequence $m \mapsto tr (A^{m})$ , satisfies from $m = 0$ the order- $n$ recurrence

$s_{m + n} + b_{1} s_{m + n - 1} + \dots + b_{n} s_{m} = 0.$

Facts & Assumptions

Given: A field $K$ , a positive size $n$ , and an invertible matrix $A \in M_{n} (K)$ with the displayed characteristic polynomial.

[L1]

Every finite-dimensional endomorphism satisfies its characteristic polynomial: $χ_{T} (T) = 0$ (Cayley-Hamilton: every finite-dimensional endomorphism satisfies its characteristic polynomial, $χ_{T} (T) = 0$ ).

[L2]

A matrix $A$ defines the coordinate endomorphism $T_{A} (x) = A x$ (For $A \in M_{n} (R)$ , the coordinate endomorphism $T_{A} : R^{n} \to R^{n}$ , with $\det (T_{A}) : = \det (A)$ and $adj (T_{A}) : = T_{adj (A)}$ ).

[L3]

The operator characteristic polynomial is the characteristic polynomial of any representing matrix (The basis-independent characteristic polynomial $χ_{T}$ of an endomorphism of a finite-dimensional space, including $χ_{T} = 1$ in dimension zero).

[L4]

The matrix characteristic polynomial is $χ_{A} (t) = \det (t I - A)$ (For $A \in M_{n} (F)$ , the characteristic polynomial is $χ_{A} (x) = \det (x I_{n} - A)$ when $n \geq 1$ , with $χ_{A} (x) = 1$ for the unique $0 \times 0$ matrix).

[L5]

The trace of a field matrix is the finite sum of its diagonal entries (The trace $tr (A)$ as the sum of the diagonal entries).

[L6]

An invertible positive-sized matrix over a commutative ring has unit determinant (An invertible square matrix over a commutative ring has unit determinant).

Proof

technique · direct

1.1givenL1L2L3

Apply [L1] to the coordinate endomorphism [L2]. By [L3], its characteristic polynomial is $χ_{A}$ , so the representing matrices satisfy $A^{n} + b_{1} A^{n - 1} + \dots + b_{n} I = 0$ .

1.2L4L6algebra

By [L4], the constant coefficient is $b_{n} = \det (- A) = (- 1)^{n} \det (A)$ . The determinant is a unit by [L6], so $b_{n} \neq 0$ in the field $K$ and the relation has order $n$ under the page's recurrence convention.

2.1step 1.1algebra

Multiplying the identity in step 1.1 by $A^{m}$ gives $A^{m + n} + b_{1} A^{m + n - 1} + \dots + b_{n} A^{m} = 0$ for every $m \geq 0$ .

3.1step 2.1L5algebra

Extracting the $(u, v)$ entry from step 2.1 proves the displayed recurrence for every matrix-power entry; summing its diagonal entries and using [L5] proves the same recurrence for the trace sequence.

4.1step 3.1step 1.2∎

Steps 3.1 and 1.2 establish both families of order- $n$ recurrences from $m = 0$ .

DefinitionDefinition: Literature-sourcedProof: Not applicableaudited 2026-08-16Open item page →

The Fibonacci sequence $F_{0} = 0, F_{1} = 1$ and Lucas sequence $L_{0} = 2, L_{1} = 1$

Definition

The Fibonacci sequence $(F_{n})_{n \geq 0}$ and Lucas sequence $(L_{n})_{n \geq 0}$ are defined by

$F_{0} = 0, F_{1} = 1, L_{0} = 2, L_{1} = 1,$

and, for every $n \geq 0$ ,

$F_{n + 2} = F_{n + 1} + F_{n}, L_{n + 2} = L_{n + 1} + L_{n} .$

Both are order- $2$ recurrences in the convention of Constant-coefficient linear recurrences, their starting index and their characteristic polynomial, with characteristic polynomial $t^{2} - t - 1$ and reciprocal denominator $1 - x - x^{2}$ . The distinct initial pairs distinguish the two sequences.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

The trace of a square matrix over a commutative ring

Definition

Let $R$ be a commutative ring, let $p \in N$ , and let $A = (a_{i j}) \in M_{p} (R)$ (Finite rectangular matrices over a commutative ring, their entries, rows and columns). The trace of $A$ over $R$ is

${tr}_{R} (A) : = \sum_{i < p} a_{i i} .$

For $p = 0$ , this is the empty sum and equals $0_{R}$ . The subscript may be omitted when the coefficient ring is clear.

PropositionStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

For matrices over a field, the commutative-ring trace agrees with the published matrix trace

Statement

Let $K$ be a field, let $p \in N$ , and let $A \in M_{p} (K)$ . Then the commutative-ring trace ${tr}_{K} (A)$ equals the published field-matrix trace $tr (A)$ . This includes $p = 0$ .

Facts & Assumptions

Given: A field $K$ , a size $p \in N$ , and a matrix $A = (a_{i j}) \in M_{p} (K)$ .

[L1]

The commutative-ring trace is ${tr}_{K} (A) = \sum_{i < p} a_{i i}$ , with empty sum zero when $p = 0$ (The trace of a square matrix over a commutative ring).

[L2]

The published field trace is $tr (A) = \sum_{i < p} a_{i i}$ , with empty sum zero when $p = 0$ (The trace $tr (A)$ as the sum of the diagonal entries).

Proof

technique · direct

1.1givenL1

By [L1], the commutative-ring trace of $A$ is the finite diagonal sum $\sum_{i < p} A_{i i}$ .

1.2givenL2

By [L2], the published field trace of $A$ is the same finite diagonal sum.

2.1step 1.1step 1.2∎

Comparing steps 1.1 and 1.2 proves equality; for $p = 0$ both are the same empty sum $0_{K}$ .

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Finite weighted directed multigraphs, weighted walks and their transfer matrices

Definition

Let $R$ be a commutative ring (Commutative ring). A finite weighted directed multigraph over $R$ consists of a finite vertex set $p = {0, \dots, p - 1}$ , a finite edge set $E$ , source and target maps $s, t : E \to p$ , and a weight map $w : E \to R$ . Parallel edges and loops are allowed.

A walk of length $n$ from $u$ to $v$ is a sequence $(e_{0}, \dots, e_{n - 1})$ of edges with $s (e_{0}) = u$ , $t (e_{n - 1}) = v$ , and $t (e_{i}) = s (e_{i + 1})$ whenever $i + 1 < n$ . Its weight is $\prod_{i < n} w (e_{i})$ . At length zero there is one empty walk from $u$ to $u$ , of weight $1_{R}$ , and no empty walk between distinct vertices.

The transfer matrix or weighted adjacency matrix is $A \in M_{p} (R)$ (Finite rectangular matrices over a commutative ring, their entries, rows and columns) defined by

$A_{u v} : = \sum_{\begin{array}{c} e \in E \\ s (e) = u, t (e) = v \end{array}} w (e) .$

An empty edge sum is $0_{R}$ . Rows record sources and columns record targets.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

The $(u, v)$ entry of $A^{n}$ is the total weight of length- $n$ walks from $u$ to $v$

Statement

Let $A$ be the transfer matrix of a finite weighted directed multigraph over a commutative ring $R$ . For every $n \in N$ and vertices $u, v$ ,

$(A^{n})_{u v} = \sum_{W : u ⇝ v, ∣ W ∣ = n} w (W) .$

The sum is over all length- $n$ walks from $u$ to $v$ . Powers of a square matrix are the ones given by the recursion $A^{0} : = I_{p}$ and $A^{n + 1} : = A^{n} A$ , where $p$ is the number of vertices; the cited matrix laws supply the product and the identity but no power notation, so the recursion is fixed here. At $n = 0$ , both sides are $1_{R}$ when $u = v$ and $0_{R}$ otherwise.

Facts & Assumptions

Given: A finite weighted directed multigraph over $R$ , its transfer matrix $A$ , vertices $u, v$ , and a length $n \in N$ .

[L1]

The transfer entry $A_{u v}$ is the sum of the weights of all edges from $u$ to $v$ , and the unique empty walk at a vertex has weight $1_{R}$ (Finite weighted directed multigraphs, weighted walks and their transfer matrices).

[L2]

Matrix multiplication is $(A B)_{u v} = \sum_{z} A_{u z} B_{z v}$ and the identity matrix has diagonal entries $1$ and off-diagonal entries $0$ (Entrywise ring-matrix operations, rectangular matrix products, identity matrices and transpose).

[L3]

For matrices over a commutative ring of compatible shapes, $A (B C) = (A B) C$ and $I_{m} A = A = A I_{n}$ , and the entrywise additive and distributive laws hold, including all zero-sized shapes (Matrix arithmetic over a commutative ring is associative, unital and distributive, and transpose reverses products).

Proof

technique · induction

1.1baseL1L2

For $n = 0$ , the recursion in the Statement gives $A^{0} = I_{p}$ , so $(A^{0})_{u v} = (I_{p})_{u v}$ , which is $1_{R}$ when $u = v$ and $0_{R}$ otherwise by [L2]; this agrees with the empty-walk convention in [L1], the empty walk being the unique walk of length $0$ from $u$ to $v$ and existing only when $u = v$ .

1.2ihL2

Assume the formula at length $n$ . The recursion gives $A^{n + 1} = A^{n} A$ , so $(A^{n + 1})_{u v} = \sum_{z < p} (A^{n})_{u z} A_{z v}$ by the product formula of [L2].

2.1step 1.2L1L3algebra

Substitute the induction formula and the edge-sum definition [L1] into step 1.2. The distributive laws of [L3] expand the result into one product for each length- $n$ walk from $u$ to $z$ followed by one edge from $z$ to $v$ .

3.1step 2.1L1

Every length- $(n + 1)$ walk has a unique penultimate vertex and last edge, so the expansion in step 2.1 is exactly the total weight of all length- $(n + 1)$ walks from $u$ to $v$ .

4.1step 1.1step 3.1discharge-induction∎

The base case and induction step prove the formula for all $n \in N$ .

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Formally, $(I - x A)^{- 1} = \sum_{n \geq 0} A^{n} x^{n}$ over every commutative coefficient ring

Statement

Let $R$ be a commutative ring, let $p \in N$ , and let $A \in M_{p} (R)$ . In the matrix ring $M_{p} (R ⟦ x ⟧)$ ,

$(I_{p} - x A)^{- 1} = \sum_{n \geq 0} A^{n} x^{n} .$

The matrix series is defined entrywise. The identity is formal, including $p = 0$ , and uses no norm, convergence, or spectral-radius hypothesis.

Facts & Assumptions

Given: A commutative ring $R$ , a size $p \in N$ , and a matrix $A \in M_{p} (R)$ .

[L1]

Formal series are coefficient functions with Cauchy product $[x^{n}] (f g) = \sum_{i = 0}^{n} [x^{i}] f [x^{n - i}] g$ (Formal power series over a commutative ring and the coefficient-extraction functional $[x^{n}]$ ).

[L2]

Cauchy multiplication makes $R ⟦ x ⟧$ a commutative ring containing $R [x]$ (Cauchy multiplication makes $R ⟦ x ⟧$ a commutative ring containing $R [x]$ as the finitely supported subring).

[L3]

Matrix products use finite row-column sums and $I_{p}$ is the identity matrix (Entrywise ring-matrix operations, rectangular matrix products, identity matrices and transpose).

[L4]

Matrix multiplication is associative and distributive, including zero-sized shapes (Matrix arithmetic over a commutative ring is associative, unital and distributive, and transpose reverses products).

Proof

technique · direct

1.1givenL1L2L3L4

Define $S = \sum_{n \geq 0} A^{n} x^{n}$ entrywise. The constant coefficient of $(I_{p} - x A) S$ is $I_{p}$ , and for every $n \geq 1$ its coefficient is $A^{n} - A A^{n - 1} = 0$ .

1.2givenL1L2L3L4

The same coefficient calculation on the other side gives the constant coefficient $I_{p}$ and positive coefficient $A^{n} - A^{n - 1} A = 0$ for $S (I_{p} - x A)$ .

2.1step 1.1step 1.2L1∎

Coefficient extensionality makes both products equal to $I_{p}$ , so $S$ is the two-sided inverse of $I_{p} - x A$ . For $p = 0$ all matrices are the unique empty matrix and the same identity holds.

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Transfer-matrix theorem: weighted-walk generating functions are cofactors of $I - x A$ divided by $\det (I - x A)$

Statement

Let $R$ be a commutative ring, let a finite weighted directed multigraph have $p \geq 1$ vertices and transfer matrix $A$ , and put $M (x) = I_{p} - x A$ . For vertices $u, v$ ,

$\sum_{n \geq 0} (\sum_{W : u ⇝ v, ∣ W ∣ = n} w (W)) x^{n} = (M^{- 1})_{u v} = \frac{(- 1)^{u + v} \det M^{(v, u)}}{\det M} .$

The quotient is a rational formal power series over $R$ because $\det M$ has constant coefficient $1_{R}$ .

Facts & Assumptions

Given: A nonempty finite weighted directed multigraph over $R$ , its $p \times p$ transfer matrix $A$ , vertices $u, v$ , and $M = I_{p} - x A$ .

[L1]

The $(u, v)$ entry of $A^{n}$ is the total weight of length- $n$ walks from $u$ to $v$ (The $(u, v)$ entry of $A^{n}$ is the total weight of length- $n$ walks from $u$ to $v$ ).

[L2]

Formally, $M^{- 1} = \sum_{n \geq 0} A^{n} x^{n}$ over every commutative coefficient ring (Formally, $(I - x A)^{- 1} = \sum_{n \geq 0} A^{n} x^{n}$ over every commutative coefficient ring).

[L3]

The adjugate satisfies $adj (M)_{u v} = (- 1)^{u + v} \det M^{(v, u)}$ (Deleted-row-and-column minors, cofactors, the cofactor matrix and the adjugate over a commutative ring).

[L4]

For a positive-sized square matrix, $M adj (M) = adj (M) M = \det (M) I$ (For every positive-sized square matrix over a commutative ring, $A adj (A) = adj (A) A = \det (A) I$ ).

[L5]

If $\det (M)$ is a unit, then $M^{- 1} = \det (M)^{- 1} adj (M)$ (If $\det (A)$ is a unit, then $A^{- 1} = \det (A)^{- 1} adj (A)$ ).

[L6]

The determinant is the finite Leibniz sum over permutations (For $n \geq 1$ , the determinant over a commutative ring by the Leibniz formula, and $∣ \det A ∣$ for a real matrix).

[L7]

A formal series is a unit exactly when its constant coefficient is a unit (A formal power series is a unit exactly when its constant coefficient is a unit).

[L8]

Cauchy multiplication makes $R ⟦ x ⟧$ a commutative ring (Cauchy multiplication makes $R ⟦ x ⟧$ a commutative ring containing $R [x]$ as the finitely supported subring).

Proof

technique · direct

1.1givenL1L2

By [L2], the $(u, v)$ entry of $M^{- 1}$ is $\sum_{n \geq 0} (A^{n})_{u v} x^{n}$ , and [L1] identifies each coefficient with the total weight of the corresponding walks.

1.2givenL6L7

Setting $x = 0$ gives $M (0) = I_{p}$ . In the Leibniz sum [L6], only the identity permutation contributes to $\det (I_{p})$ , so $\det M$ has constant coefficient $1_{R}$ and is a unit by [L7].

2.1step 1.2L4L5L8

Apply [L4] and [L5] over the commutative ring $R ⟦ x ⟧$ from [L8] to obtain $M^{- 1} = \det (M)^{- 1} adj (M)$ .

3.1step 2.1L3

Taking the $(u, v)$ entry in step 2.1 and using [L3] gives $(M^{- 1})_{u v} = (- 1)^{u + v} \det M^{(v, u)} / \det M$ .

4.1step 1.1step 3.1L3L6∎

Combining steps 1.1 and 3.1 proves the formula, with no analytic hypothesis. The assumption $p \geq 1$ is exactly the positive-size domain of [L3] through [L6].

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

$\frac{d}{d x} \det (I - x A) = - tr (adj (I - x A) A)$

Statement

Let $R$ be a commutative ring, let $p \geq 1$ , let $A \in M_{p} (R)$ , and put $M (x) = I_{p} - x A$ . Then, with the formal derivative,

$\frac{d}{d x} \det M (x) = - {tr}_{R [x]} (adj (M (x)) A) .$

The subscript names the coefficient ring the trace is taken over. Since $adj (M (x)) A$ has entries in $R [x]$ , not in $R$ , the trace here is the one belonging to the commutative ring $R [x]$ ; the defining formula $\sum_{i < p} a_{i i}$ is the same.

Facts & Assumptions

Given: A commutative ring $R$ , a positive size $p$ , a matrix $A \in M_{p} (R)$ , and $M = I_{p} - x A$ .

[L1]

The ring trace is the finite sum of the diagonal entries (The trace of a square matrix over a commutative ring).

[L2]

The adjugate is the transpose of the cofactor matrix, so $adj (M)_{i j} = C_{j i} (M)$ (Deleted-row-and-column minors, cofactors, the cofactor matrix and the adjugate over a commutative ring).

[L3]

The determinant is the Leibniz sum $\det (M) = \sum_{σ} sgn (σ) \prod_{i} M_{σ (i), i}$ (For $n \geq 1$ , the determinant over a commutative ring by the Leibniz formula, and $∣ \det A ∣$ for a real matrix).

[L4]

The formal derivative is coefficientwise and sends $x$ to $1$ and constants to $0$ (The formal derivative $D (\sum a_{n} x^{n}) = \sum_{n \geq 1} n a_{n} x^{n - 1}$ ).

[L5]

Formal differentiation is linear and satisfies the product rule (Formal differentiation is linear and satisfies product, power, quotient, chain, and coefficient-recovery laws).

Proof

technique · direct

1.1givenL3L5

Differentiate the finite Leibniz sum [L3]. By [L5], each product contributes one term for each selected matrix entry, and grouping all terms that differentiate $M_{i j}$ leaves its cofactor $C_{i j} (M)$ .

1.2L1L2algebra

By [L1] and matrix multiplication, ${tr}_{R} (adj (M) A) = \sum_{i} \sum_{j} adj (M)_{i j} A_{j i}$ . Using [L2] and renaming the finite indices gives $\sum_{i, j} C_{i j} (M) A_{i j}$ .

2.1step 1.1L4algebra

Thus $(\det M)^{'} = \sum_{i, j} C_{i j} (M) M_{i j}^{'}$ . Since $M^{'} = - A$ by [L4], this is $- \sum_{i, j} C_{i j} (M) A_{i j}$ .

3.1step 2.1step 1.2L2∎

Comparing steps 2.1 and 1.2 gives the displayed derivative identity. Positive size supplies every cofactor used in [L2].

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

Closed walks have trace and logarithmic-derivative generating functions

Statement

Let $R$ be a commutative ring, let $p \geq 1$ , let $A \in M_{p} (R)$ be a transfer matrix, and put $Q (x) = \det (I_{p} - x A)$ . Then

$\sum_{n \geq 0} {tr}_{R} (A^{n}) x^{n} = \frac{{tr}_{R [x]} (adj (I_{p} - x A))}{Q (x)},$

and

$\sum_{n \geq 1} {tr}_{R} (A^{n}) x^{n} = - \frac{x Q^{'} (x)}{Q (x)} .$

The coefficient ${tr}_{R} (A^{n})$ is the total weight of all closed walks of length $n$ . Each trace subscript names the commutative ring its argument's entries lie in: $A^{n} \in M_{p} (R)$ , while $adj (I_{p} - x A)$ has entries in $R [x]$ , so that numerator is ${tr}_{R [x]}$ . The defining formula $\sum_{i < p} a_{i i}$ is the same in each case. The second expression is a formal logarithmic derivative; no logarithm or convergence is required.

Facts & Assumptions

Given: A positive-sized transfer matrix $A$ over a commutative ring $R$ , $M = I_{p} - x A$ , and $Q = \det M$ .

[L1]

The transfer-matrix formula identifies each entry of $M^{- 1}$ with the corresponding weighted-walk series and with an adjugate entry divided by $Q$ (Transfer-matrix theorem: weighted-walk generating functions are cofactors of $I - x A$ divided by $\det (I - x A)$ ).

[L2]

The determinant derivative satisfies $Q^{'} = - {tr}_{R [x]} (adj (M) A)$ , the trace being over $R [x]$ where those entries lie ( $\frac{d}{d x} \det (I - x A) = - tr (adj (I - x A) A)$ ).

[L3]

The ring trace is the finite sum of diagonal entries, including the empty-sum convention (The trace of a square matrix over a commutative ring).

Proof

technique · direct

1.1givenL1L3

Sum the diagonal instances of [L1]. By [L3], the left side is $\sum_{n \geq 0} {tr}_{R} (A^{n}) x^{n}$ and the numerator on the right is ${tr}_{R [x]} (adj (M))$ , proving the first identity and the closed-walk interpretation.

1.2L1L3algebra

From [L1], $M^{- 1} = \sum_{n \geq 0} A^{n} x^{n} = adj (M) / Q$ . Multiplying by $A$ , taking the trace over $R ⟦ x ⟧$ where $M^{- 1} A$ has its entries, and then multiplying by $x$ gives $x {tr}_{R ⟦ x ⟧} (M^{- 1} A) = \sum_{n \geq 1} {tr}_{R} (A^{n}) x^{n}$ , the right-hand coefficients being the traces over $R$ of the matrices $A^{n}$ .

2.1step 1.2L2algebra

Dividing [L2] by the unit $Q$ gives $- x Q^{'} / Q = x {tr}_{R ⟦ x ⟧} (M^{- 1} A)$ . Combine this with step 1.2 to obtain the second identity.

3.1step 1.1step 2.1∎

Both calculations take place in $R ⟦ x ⟧$ , so they require no topology or spectral-radius assumption.

CorollaryStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Let $K$ be a field, $p \geq 1$ , and $A \in M_{p} (K)$ . If $χ_{A} (t) = \prod_{i < p} (t - λ_{i})$ in $K [t]$ , then the transfer-matrix trace series is $\sum_{i < p} (1 - λ_{i} x)^{- 1}$

Statement

Let $K$ be a field, let $p \geq 1$ , and let $A \in M_{p} (K)$ . Suppose that its characteristic polynomial is displayed as a product of linear factors in the base field,

$χ_{A} (t) = \prod_{i < p} (t - λ_{i}) in K [t],$

where roots are repeated according to algebraic multiplicity. Then

$tr (A^{n}) = \sum_{i < p} λ_{i}^{n} (n \geq 0),$

and, formally,

$\sum_{n \geq 0} tr (A^{n}) x^{n} = \sum_{i < p} \frac{1}{1 - λ_{i} x} .$

When $A$ is a transfer matrix, this is the eigenvalue form of its closed-walk trace series.

Facts & Assumptions

Given: A field $K$ , a positive size $p$ , a matrix $A \in M_{p} (K)$ , and the displayed split factorisation of $χ_{A}$ in $K [t]$ .

[L1]

For a transfer matrix, the closed-walk series is $\sum_{n \geq 0} {tr}_{K} (A^{n}) x^{n}$ (Closed walks have trace and logarithmic-derivative generating functions).

[L2]

The matrix $A$ defines the coordinate endomorphism $T_{A} (x) = A x$ (For $A \in M_{n} (R)$ , the coordinate endomorphism $T_{A} : R^{n} \to R^{n}$ , with $\det (T_{A}) : = \det (A)$ and $adj (T_{A}) : = T_{adj (A)}$ ).

[L3]

The characteristic polynomial of an endomorphism equals that of any representing matrix (The basis-independent characteristic polynomial $χ_{T}$ of an endomorphism of a finite-dimensional space, including $χ_{T} = 1$ in dimension zero).

[L4]

The trace of an endomorphism equals the trace of any representing matrix (The basis-independent trace of an endomorphism of a finite-dimensional vector space).

[L5]

If $χ_{T} (t) = \prod_{i < p} (t - λ_{i})$ , then $χ_{q (T)} (y) = \prod_{i < p} (y - q (λ_{i}))$ for every polynomial $q$ (If $χ_{T} (x) = \prod_{i < n} (x - λ_{i})$ in $F [x]$ , then $χ_{p (T)} (y) = \prod_{i < n} (y - p (λ_{i}))$ for every $p \in F [x]$ : the eigenvalues of $p (T)$ are $p (λ_{i})$ , counted with algebraic multiplicity).

[L6]

When the characteristic polynomial splits, the trace is the sum of its roots with algebraic multiplicity (If $χ_{T} (x) = \prod_{i < n} (x - λ_{i})$ in $F [x]$ , then $tr (T) = \sum_{i < n} λ_{i}$ : trace is the sum of the eigenvalues counted with algebraic multiplicity).

[L7]

The case $j = 1$ of the repeated-pole formula is $(1 - λ x)^{- 1} = \sum_{n \geq 0} λ^{n} x^{n}$ (Repeated poles expand formally as $(1 - λ x)^{- j} = \sum_{n \geq 0} (\binom{n + j - 1}{j - 1}) λ^{n} x^{n}$ ).

[L8]

Over a field, the commutative-ring matrix trace equals the published matrix trace (For matrices over a field, the commutative-ring trace agrees with the published matrix trace).

Proof

technique · direct

1.1givenL2L3

Let $T_{A}$ be the coordinate endomorphism from [L2]. By [L3], the given factorisation is also $χ_{T_{A}} (t) = \prod_{i < p} (t - λ_{i})$ .

2.1step 1.1L5L6

Apply [L5] to $q (t) = t^{n}$ . The roots of $χ_{T_{A}^{n}}$ are $λ_{i}^{n}$ with the displayed multiplicities, so [L6] gives $tr (T_{A}^{n}) = \sum_{i < p} λ_{i}^{n}$ .

3.1step 2.1L4L8

By [L4] and [L8], the left side in step 2.1 is $tr (A^{n})$ in either trace convention. This proves the coefficient formula, including $n = 0$ .

4.1step 3.1L7algebra

Multiply the coefficient formula by $x^{n}$ , sum formally over $n \geq 0$ , and apply [L7] to each of the finitely many roots; this yields the displayed rational-series identity.

5.1step 4.1L1∎

If $A$ is a transfer matrix, [L1] identifies the left side of step 4.1 with its closed-walk trace series. The split factorisation was assumed at the outset and is not inferred from algebraic closure or diagonalisation.

DefinitionDefinition: AI-adaptedProof: Not applicableaudited 2026-08-16Open item page →

Finite words, contiguous factors, avoidance and proper-prefix states

Definition

Let $Σ$ be a finite set, called an alphabet. A word of length $n$ over $Σ$ is a function from the natural number $n = {0, \dots, n - 1}$ (The natural numbers $N$ (von Neumann)) to $Σ$ , written $a_{0} a_{1} \dots a_{n - 1}$ . The unique word of length zero is the empty word $ε$ . Concatenation of words $u$ and $v$ is denoted by $u v$ .

A word $u$ is a contiguous factor of $w = a_{0} \dots a_{n - 1}$ if $u = a_{i} \dots a_{i + r - 1}$ for some $0 \leq i \leq i + r \leq n$ . It is a prefix if $i = 0$ , a suffix if $i + r = n$ , and a proper prefix if it is a prefix other than the whole word.

For a set $B$ of words, a word avoids $B$ if none of its contiguous factors belongs to $B$ . Its set of proper-prefix states is

$S_{B} : = {u : u avoids B and u is a proper prefix of some b \in B} .$

If $B$ is nonempty and every word in $B$ is nonempty, then $ε \in S_{B}$ . If $B$ is finite, then $S_{B}$ is finite.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

The longest-suffix prefix automaton for a finite set of forbidden factors

Definition

Let $Σ$ be a finite alphabet and let $B$ be a finite nonempty set of nonempty words over $Σ$ . With $S_{B}$ as in Finite words, contiguous factors, avoidance and proper-prefix states, the prefix automaton for $B$ has state set $S_{B}$ , initial state $ε$ , and the following transitions.

For $s \in S_{B}$ and $a \in Σ$ , reject the letter $a$ if the concatenation $s a$ contains a factor in $B$ . Otherwise define $δ (s, a)$ to be the longest suffix of $s a$ that belongs to $S_{B}$ , and put an edge labelled $a$ from $s$ to $δ (s, a)$ . This state exists because $ε \in S_{B}$ , and it is unique because suffixes of distinct lengths are distinct.

For enumeration, give every edge weight $1$ over $Z$ . Different letters that induce the same transition remain parallel edges, so the associated transfer-matrix entry is the number of such letters.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16Open item page →

Words over a finite alphabet avoiding finitely many nonempty factors have a rational length generating function

Statement

Let $Σ$ be a finite alphabet and let $B$ be a finite set of nonempty words over $Σ$ . If $a_{n}$ is the number of length- $n$ words over $Σ$ that avoid every factor in $B$ , then

$A (x) : = \sum_{n \geq 0} a_{n} x^{n}$

is a rational formal power series over $Z$ .

Facts & Assumptions

Given: A finite alphabet $Σ$ and a finite set $B$ of nonempty words.

[L1]

A rational formal series has a polynomial numerator and a polynomial denominator with unit constant coefficient (Rational formal power series, proper presentations and reduced denominators).

[L2]

For nonempty $B$ , the prefix automaton retains the longest suffix that is a proper prefix of a forbidden word and rejects a transition that creates a forbidden factor (The longest-suffix prefix automaton for a finite set of forbidden factors).

[L3]

For a finite weighted digraph with transfer matrix $M$ , the total weight of length- $n$ walks from $u$ to $v$ is $(M^{n})_{u v}$ (The $(u, v)$ entry of $A^{n}$ is the total weight of length- $n$ walks from $u$ to $v$ ).

[L4]

Every fixed-entry walk generating series of a nonempty finite weighted digraph is a cofactor of $I - x M$ divided by $\det (I - x M)$ , hence rational (Transfer-matrix theorem: weighted-walk generating functions are cofactors of $I - x A$ divided by $\det (I - x A)$ ).

[L5]

Finite sums of rational formal power series are rational (Rational formal power series are closed under sums and Cauchy products).

Proof

technique · automaton invariant and transfer matrix

1.1givenL1algebra

If $B = \emptyset$ and $q = ∣ Σ ∣$ , then $a_{n} = q^{n}$ and $(1 - q x) \sum_{n \geq 0} q^{n} x^{n} = 1$ coefficientwise, so [L1] makes $A (x) = 1 / (1 - q x)$ rational.

1.2givenL2

Suppose now that $B$ is nonempty. After a word $w$ avoiding $B$ has been read, the automaton state is the longest suffix of $w$ belonging to $S_{B}$ : this holds initially at $ε$ , and repeated application of [L2] preserves it as each accepted letter is appended.

2.1step 1.2L2

Let $w$ avoid $B$ , let $s$ be its state from step 1.2, and let $a \in Σ$ . If $w a$ contains a forbidden factor $b$ , that factor ends at the appended letter, so $b = b^{'} a$ with $b^{'}$ a suffix of $w$ ; and $b^{'}$ avoids $B$ and is a proper prefix of $b \in B$ , so $b^{'} \in S_{B}$ . Since $s$ is the longest suffix of $w$ in $S_{B}$ , the word $b^{'}$ is a suffix of $s$ , so $b$ is a factor of $s a$ and [L2] rejects $a$ . Conversely, $s$ is a suffix of $w$ , so any factor of $s a$ in $B$ is a factor of $w a$ . Thus [L2] rejects exactly the extensions that cease to avoid $B$ .

3.1step 1.2step 2.1

Steps 1.2 and 2.1 give a weight-preserving bijection between length- $n$ words avoiding $B$ and length- $n$ walks in the prefix automaton from $ε$ to any state in $S_{B}$ .

4.1step 1.1step 3.1L3L4L5∎

By [L3], $a_{n} = \sum_{v \in S_{B}} (M^{n})_{ε v}$ . Each series $\sum_{n \geq 0} (M^{n})_{ε v} x^{n}$ is rational by [L4], and their finite sum is rational by [L5]. Together with the empty- $B$ case in step 1.1, this proves the result.

CorollaryStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-16Open item page →

Binary words avoiding any fixed nonempty factor have a rational length generating function

Statement

Fix a nonempty binary word $w$ . If $a_{n}$ is the number of words in ${0, 1}^{n}$ that do not contain $w$ as a contiguous factor, then $\sum_{n \geq 0} a_{n} x^{n}$ is a rational formal power series over $Z$ .

Facts & Assumptions

Given: A nonempty word $w$ over the finite alphabet ${0, 1}$ .

[L1]

Words over a finite alphabet that avoid a finite set of nonempty factors have a rational length generating function (Words over a finite alphabet avoiding finitely many nonempty factors have a rational length generating function).

Proof

technique · specialization

1.1given

The alphabet ${0, 1}$ is finite, and $B = {w}$ is a finite set of nonempty words.

2.1step 1.1L1∎

Apply [L1] using step 1.1. Its conclusion is the asserted rationality.

5 · Examples, counterexamples and false statements

None yet.

Linear Recurrences and Rational Generating Functions

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Constant-coefficient linear recurrences, their starting index and their characteristic polynomial

Definition

Rational formal power series, proper presentations and reduced denominators

Definition

The initial-value, recurrence-sequence, numerator and fixed-denominator rational-series spaces all have dimension dd

Statement

Facts & Assumptions

Proof

A coefficient sequence is eventually linearly recurrent if and only if its formal generating function is rational

Statement

Facts & Assumptions

Proof

dd initial values determine a sequence satisfying a fixed order-dd recurrence

Statement

Facts & Assumptions

Proof

The least eventual recurrence order is the degree of the reduced denominator

Statement

Facts & Assumptions

Proof

Changing finitely many coefficients preserves rationality and eventual linear recurrence

Statement

Facts & Assumptions

Proof

For a bi-infinite linear recurrence over KK, the two half-series satisfy F+(x)=−F−(x−1)F+​(x)=−F−​(x−1) in K(x)K(x)

Statement

Facts & Assumptions

Proof

Rational formal power series are closed under sums and Cauchy products

Statement

Facts & Assumptions

Proof

The Hadamard product of two rational formal power series over a field is rational

Statement

Facts & Assumptions

Proof

Reciprocal-root convention: χ(t)=∏i(t−λi)miχ(t)=∏i​(t−λi​)mi​ corresponds to Q(x)=∏i(1−λix)miQ(x)=∏i​(1−λi​x)mi​

Statement

A proper rational function with split denominator has a unique repeated-pole partial-fraction expansion

Statement

Facts & Assumptions

Proof

Repeated poles expand formally as (1−λx)−j=∑n≥0(n+j−1j−1)λnxn(1−λx)−j=∑n≥0​(j−1n+j−1​)λnxn

Statement

Facts & Assumptions

Proof

Over a named splitting field in characteristic zero, repeated characteristic roots give polynomial-times-exponential closed forms

Statement

Facts & Assumptions

Proof

The row-shift companion matrix of a linear recurrence

Definition

The companion matrix advances the recurrence state vector by one step

Statement

Facts & Assumptions

Proof

A recurrence companion matrix has the recurrence characteristic polynomial

Statement

Facts & Assumptions

Proof

For an invertible matrix over a field, Cayley-Hamilton makes every matrix-power entry and trace sequence linearly recurrent

Statement

Facts & Assumptions

Proof

The Fibonacci sequence F0=0,F1=1F0​=0,F1​=1 and Lucas sequence L0=2,L1=1L0​=2,L1​=1

Definition

The trace of a square matrix over a commutative ring

Definition

For matrices over a field, the commutative-ring trace agrees with the published matrix trace

Statement

Facts & Assumptions

Proof

Finite weighted directed multigraphs, weighted walks and their transfer matrices

Definition

The (u,v)(u,v) entry of AnAn is the total weight of length-nn walks from uu to vv

The initial-value, recurrence-sequence, numerator and fixed-denominator rational-series spaces all have dimension $d$

$d$ initial values determine a sequence satisfying a fixed order- $d$ recurrence

For a bi-infinite linear recurrence over $K$ , the two half-series satisfy $F_{+} (x) = - F_{-} (x^{- 1})$ in $K (x)$

Reciprocal-root convention: $χ (t) = \prod_{i} (t - λ_{i})^{m_{i}}$ corresponds to $Q (x) = \prod_{i} (1 - λ_{i} x)^{m_{i}}$

Repeated poles expand formally as $(1 - λ x)^{- j} = \sum_{n \geq 0} (\binom{n + j - 1}{j - 1}) λ^{n} x^{n}$

The Fibonacci sequence $F_{0} = 0, F_{1} = 1$ and Lucas sequence $L_{0} = 2, L_{1} = 1$

The $(u, v)$ entry of $A^{n}$ is the total weight of length- $n$ walks from $u$ to $v$

Formally, $(I - x A)^{- 1} = \sum_{n \geq 0} A^{n} x^{n}$ over every commutative coefficient ring

Transfer-matrix theorem: weighted-walk generating functions are cofactors of $I - x A$ divided by $\det (I - x A)$

$\frac{d}{d x} \det (I - x A) = - tr (adj (I - x A) A)$

Let $K$ be a field, $p \geq 1$ , and $A \in M_{p} (K)$ . If $χ_{A} (t) = \prod_{i < p} (t - λ_{i})$ in $K [t]$ , then the transfer-matrix trace series is $\sum_{i < p} (1 - λ_{i} x)^{- 1}$