TheoremStatement: Literature-sourcedProof: AI-generatedSession-authored (Fable 5 assisted)precheck passaudited 2026-08-27

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.

The signed first-kind and second-kind Stirling numbers are inverse transition matrices

Statement

For all $n, m \in N$ ,

$m^{\underline{n}} = \sum_{k = 0}^{n} s (n, k) m^{k} .$

Consequently, for all $n, j \in N$ ,

$\sum_{k = j}^{n} S (n, k) s (k, j) = δ_{n, j}, \sum_{k = j}^{n} s (n, k) S (k, j) = δ_{n, j},$

where $δ_{n, j}$ is the Kronecker delta. Equivalently, for sequences $(a_{k})_{k \geq 0}$ and $(b_{n})_{n \geq 0}$ in any commutative ring,

$b_{n} = \sum_{k = 0}^{n} S (n, k) a_{k} ⟺ a_{n} = \sum_{k = 0}^{n} s (n, k) b_{k} .$

Facts & Assumptions

Given: The second-kind expansion of Ordinary powers expand in the falling-factorial basis by the second-kind Stirling numbers and the first-kind expansion of The signless first-kind Stirling numbers satisfy their recurrence and expand the rising factorial.

Proof

technique · direct

1.1

Replace $x$ by $- m$ in The signless first-kind Stirling numbers satisfy their recurrence and expand the rising factorial. Since $(- m)^{\overline{n}} = (- 1)^{n} m^{\underline{n}}$ and $s (n, k) = (- 1)^{n - k} c (n, k)$ by definition, this gives $m^{\underline{n}} = \sum_{k = 0}^{n} s (n, k) m^{k}$ .

givenalgebra

1.2

A finite linear combination $\sum_{j = 0}^{n} a_{j} m^{\underline{j}}$ that vanishes for every $m \in N$ has all coefficients zero: evaluating at $m = 0$ gives $a_{0} = 0$ , and after that evaluating at $m = 1, 2, \dots, n$ strips off the remaining coefficients triangularly because $m^{\underline{j}} = 0$ for $j > m$ and $m^{\underline{m}} = m! \neq 0$ by The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $N$ .

given

2.1

Substitute the second-kind expansion of Ordinary powers expand in the falling-factorial basis by the second-kind Stirling numbers into step 1.1. This gives $m^{\underline{n}} = \sum_{k = 0}^{n} s (n, k) \sum_{j = 0}^{k} S (k, j) m^{\underline{j}} = \sum_{j = 0}^{n} (\sum_{k = j}^{n} s (n, k) S (k, j)) m^{\underline{j}}$ .

step 1.1givenalgebra

3.1

Apply step 1.2 to the identity of step 2.1. Since the left-hand side is $m^{\underline{n}}$ , the coefficient of $m^{\underline{j}}$ is $δ_{n, j}$ , so $\sum_{k = j}^{n} s (n, k) S (k, j) = δ_{n, j}$ .

step 2.1step 1.2

4.1

The matrix in step 3.1 is lower triangular with diagonal entries $1$ , so its inverse is unique. Since step 3.1 shows that $(s (n, k))_{n, k \geq 0}$ is a left inverse of $(S (n, k))_{n, k \geq 0}$ , it is also the right inverse. Hence $\sum_{k = j}^{n} S (n, k) s (k, j) = δ_{n, j}$ as well.

step 3.1algebra

5.1

Steps 3.1 and 4.1 say exactly that the two triangular Stirling matrices are inverse to one another. Therefore the two finite-sum transforms on sequences in any commutative ring are mutually inverse, which is the claimed iff.

step 3.1step 4.1∎

Depends on

Used by

The Stirling triangles invert up to size 4 Example

Dependency tree · two levels

22 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Andrew Lin, 18.212 Algebraic Combinatorics, Lecture 11, Corollary 4 (standard reference, not scraped)