Enter any one of a constant-coefficient recurrence, a rational generating function, or a closed form — the other two are derived exactly (BigInt rationals, no floating point except for displaying irreducible roots). The dark strip at the bottom recomputes the first terms independently from each representation and checks they agree; nothing is shown unverified.
Rewrites the current sequence as a(n) = Σm λ(m)·K(n,m) for six triangular kernels K — Stirling, surjection, binomial, and signed-binomial transforms. Each kernel determines λ uniquely by exact forward substitution; a result is shown only when λ itself has a recognizable closed form, which certifies the sum on every term.
A sequence satisfying a linear recurrence with constant coefficients is called
C-finite. Its three descriptions are interchangeable by elementary power-series algebra:
the recurrence a(n) = c₁a(n−1) + … + cᵣa(n−r) says exactly that the series
A(x) = Σ a(n)xⁿ becomes a polynomial after multiplication by
1 − c₁x − … − cᵣxʳ, so A(x) is rational with that denominator; conversely long
division of a rational function reads the recurrence off the denominator and the initial
values off the quotient. This equivalence is folklore of the subject — a modern
treatment is Chapter 4 of Stanley’s Enumerative Combinatorics [13] and the
“C-finite” chapter of Kauers–Paule [8]. Recovering a recurrence from raw terms by
solving a small linear system is the “guessing” tradition automated in
gfun [12] and in the OEIS Superseeker [11]; this page does the same with exact
BigInt rationals.
Writing the recurrence as p(z) = zʳ − c₁zʳ⁻¹ − … − cᵣ and factoring, each root ρ of multiplicity m contributes (polynomial of degree < m)·ρⁿ to the solution. Solving linear recurrences this way goes back to Abraham de Moivre’s Miscellanea Analytica (1730) [1], where generating functions first appear; the explicit Fibonacci form usually credited to Binet (1843) was already known to de Moivre, Daniel Bernoulli and Euler. This page factors p exactly: rational roots by the rational-root theorem; an irreducible quadratic gives an exact Binet form computed in the field ℚ(√D); factors dividing zᵐ − 1 have roots of unity, and the sequence restricted to each residue class mod m is then polynomial-with-rational-bases — the quasi-polynomial case. Quasi-polynomials are classical in lattice-point counting (Ehrhart, 1962 [3]) and are precisely the expected shape of crystal coordination sequences (Grosse-Kunstleve–Brunner–Sloane [6]). Anything irreducible of higher degree is reported honestly with numerically approximated roots (simultaneous iteration of Durand [2] and Kerner [9]) rather than a fake formula.
Sums like Σ S(n,m)λ(m) or Σ (−1)ⁿ⁻ᵐC(n,m)λ(m) use triangular kernels: K(n,m) = 0 for m > n and K(n,n) ≠ 0. For such a kernel the coefficients λ are not fitted — they are forced, term by term, by forward substitution, and this inversion is exact. The classical theory of these inverse relations (binomial, Stirling, and their signed variants) is Riordan’s Combinatorial Identities [10]; the Stirling numbers themselves date to James Stirling’s Methodus Differentialis (1730) [14], and the alternating binomial sums are inclusion–exclusion, whose closed principle is usually credited to da Silva (1854) and Sylvester (1883), with the derangement computation already in de Montmort (1708–13). The lens then asks whether the forced λ is itself simple: finitely supported, polynomial, exponential-polynomial, or a hypergeometric term (λ(m+1)/λ(m) a rational function of m, so λ is a product of factorials, Pochhammer symbols and a geometric part). Because inversion is exact, a recognized λ that matches every inverted value certifies the sum identity on every published term with no further proof obligation. Applying transforms and then trying to recognize the result is the strategy of Sloane’s Superseeker [11]; the lens differs in doing the inverse direction exactly and in accepting only certified matches.
Kaneko [7] defined the poly-Bernoulli numbers Bn(k) through the polylogarithm generating function Lik(1−e⁻ᵗ)/(1−e⁻ᵗ); for negative upper index they are positive integers with the striking symmetry Bn(−k) = Bk(−n). Brewbaker [4] proved they count lonesum matrices — 0–1 matrices reconstructible from their row and column sums, a class characterized by Ryser’s forbidden-pattern theorem (1957) [5] — and derived both the alternating surjection sum Σᵤ (−1)ⁿ⁺ᵤ j! S(n,j) (j+1)ᵗ and the positive product form Σm (m!)² S(n+1,m+1) S(k+1,m+1). The generator above uses the first (via the duality) to produce each row’s exponential-polynomial closed form; the lens, run while a row is active, re-derives the second mechanically: inverting the full array under the S(·+1,m+1) kernel in both variables produces a diagonal coefficient matrix whose diagonal is recognized as (m!)².
Recurrences with polynomial coefficients (P-recursive sequences), definite hypergeometric summation, and proofs of sum identities belong to the Gosper [5a]–Zeilberger [15]–Petkovšek [16] algorithmic world described in A = B [17]; that machinery certifies recurrences for sums and decides when hypergeometric closed forms exist. This page stops at the C-finite boundary on purpose, and says so when a characteristic polynomial has no rational, quadratic-surd, or root-of-unity structure.