PropositionStatement: Literature-sourcedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passaudited 2026-08-16

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.

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.1

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_{-}$ .

givenL1

2.1

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)$ .

givenstep 1.1algebra

2.2

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}$ .

step 1.1algebra

3.1

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.

step 2.1L2algebra

4.1

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.

step 3.1algebra

5.1

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$ .

step 3.1step 2.2step 4.1algebra

6.1

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.

step 1.1given∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 29 results over 10 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd ed., Proposition 4.2.3 and Corollary 4.2.4 (standard reference, not scraped)

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)