CorollaryStatement: Literature-sourcedProof: AI-generatedSession-authored (Fable 5 assisted)precheck passjudge pass (z-ai/glm-5.2)verified 2026-07-29 (claude-fable-5)

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.

$\iota(D_n) = \iota(n)\,\iota(D_{n-1}) + (-1)^{n}$ for $n \ge 1$ , and $D_n = (n-1)(D_{n-1} + D_{n-2})$ for $n \ge 2$

Statement

Let $D_n$ be the derangement numbers (The derangement number $D_n$ : the number of bijections of an $n$ -element set with no fixed point) and $\iota$ the canonical natural (The canonical natural $\iota(n) = n \cdot 1_F$ of a field). Then:

For every $n \ge 1$ , in $\mathbb{R}$ , $\iota(D_n) \;=\; \iota(n)\,\iota(D_{n-1}) + (-1)^{n} .$
For every $n \ge 2$ , in $\mathbb{N}$ , $D_n \;=\; (n-1)\,\big(D_{n-1} + D_{n-2}\big).$

All differences are the truncated ones (Finite sums and finite products of natural numbers, $\sum_{k<n} a_k$ and $\prod_{k<n} a_k$ in $\mathbb{N}$ ), which in the stated ranges are the ordinary ones.

Both hypotheses are exactly what the proofs need, and nothing is asserted outside them. Clause 1 is proved from the identity $n = (n-1)+1$ and its consequence $n! = (n-1)!\cdot n$ , both of which fail at $n = 0$ under the truncated difference, where $n-1$ is $0$ ; so $n = 1$ is its first legal index, and there it reads $\iota(D_1) = \iota(1)\,\iota(D_0) - 1 = 0$ . Clause 2 is derived by applying clause 1 twice, at $n$ and at $n-1$ , so it needs $n - 1 \ge 1$ ; its first legal index is $n = 2$ , where it reads $D_2 = 1\cdot(D_1 + D_0) = 1$ . Under the truncated difference the two displayed formulas happen also to be true at $n = 0$ and at $n = 1$ respectively, both sides being $1$ in the first case and $0$ in the second, but neither of those readings is proved here and neither is claimed.

Facts & Assumptions

Given: A natural number $n$ with $n \ge 1$ in clause 1 and $n \ge 2$ in clause 2; the abbreviation $p := n-1$ , so that $p + 1 = n$ (Order on the natural numbers, Finite sums and finite products of natural numbers, $\sum_{k<n} a_k$ and $\prod_{k<n} a_k$ in $\mathbb{N}$ , Every nonzero natural number is a successor).

[L1]

The derangement formula: $\iota(D_m) = \iota(m!)\sum_{i<m+1}(-1)^{i}/\iota(i!)$ for every $m \in \mathbb{N}$ ( $\iota(D_n) = \iota(n!)\sum_{i<n+1}(-1)^{i}/\iota(i!)$ , with the term at $i = 0$ equal to $1$ and $D_0 = 1$ ).

[L2]

Recursion clause of the real finite sum: $\sum_{i<q+1}u_i = \sum_{i<q}u_i + u_q$ (Finite sums and finite products, by recursion, Laws of finite sums and finite products).

[L3]

Factorials: $\sigma(m)! = m!\cdot\sigma(m)$ , so $n! = p!\cdot n$ when $p+1 = n$ ; and $m! \ne 0$ for every $m$ (The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $\mathbb{N}$ ).

[L4]

$\iota$ is additive and multiplicative with $\iota(1) = 1$ , and it is injective (Laws of finite sums and products in $\mathbb{N}$ , and $\iota\big(\sum_{k<n} a_k\big) = \sum_{k<n} \iota(a_k)$ , clauses 0 and 7, The canonical natural $\iota(n) = n \cdot 1_F$ of a field). In particular $\iota(n) - 1 = \iota(p)$ when $p+1 = n$ , and $\iota(m!) \ne 0$ .

[L5]

Powers of $-1$ : $(-1)^{0} = 1$ and $(-1)^{q+1} = -(-1)^{q}$ (Integer powers $a^m$ ).

[L6]

$\mathbb{R}$ is an ordered field, so subtraction and division by a nonzero element are available (Ordered field, Field).

Proof

technique · direct

1.1

Let $n \ge 1$ and put $p := n-1$ , so $p+1 = n$ . Then $n! = p!\cdot n$ by [L3], hence $\iota(n!) = \iota(p!)\,\iota(n)$ by [L4], and both $\iota(n!)$ and $\iota(p!)$ are nonzero.

givenL3L4

1.2

The formula at $p$ . By [L1] and $p+1 = n$ , $\iota(D_p) = \iota(p!)\sum_{i<n}(-1)^{i}/\iota(i!)$ .

1.3

Splitting the sum at its last index. By [L2], $\sum_{i<n+1}(-1)^{i}/\iota(i!) = \sum_{i<n}(-1)^{i}/\iota(i!) + (-1)^{n}/\iota(n!)$ .

2.1

Clause 1. Multiplying step 1.3 by $\iota(n!)$ and using [L1] at $m = n$ , step 1.1 and step 1.2, $\iota(D_n) = \iota(n!)\sum_{i<n}(-1)^{i}/\iota(i!) + (-1)^{n} = \iota(n)\,\iota(p!)\sum_{i<n}(-1)^{i}/\iota(i!) + (-1)^{n} = \iota(n)\,\iota(D_p) + (-1)^{n}$ .

step 1.1step 1.2step 1.3L1L6

3.1

Now let $n \ge 2$ , so that $p = n-1 \ge 1$ and $p - 1 = n-2$ . Applying step 2.1 at $p$ in place of $n$ gives $\iota(D_p) = \iota(p)\,\iota(D_{n-2}) + (-1)^{p}$ , hence $(-1)^{p} = \iota(D_p) - \iota(p)\,\iota(D_{n-2})$ ; and $(-1)^{n} = (-1)^{p+1} = -(-1)^{p}$ by [L5], so $(-1)^{n} = \iota(p)\,\iota(D_{n-2}) - \iota(D_p)$ .

step 2.1L5L6

4.1

Clause 2. Substituting step 3.1 into step 2.1, $\iota(D_n) = \iota(n)\,\iota(D_p) - \iota(D_p) + \iota(p)\,\iota(D_{n-2}) = \big(\iota(n)-1\big)\iota(D_p) + \iota(p)\,\iota(D_{n-2}) = \iota(p)\big(\iota(D_p) + \iota(D_{n-2})\big)$ , using $\iota(n)-1 = \iota(p)$ from [L4]; the right-hand side is $\iota\big(p\,(D_{n-1} + D_{n-2})\big)$ by the additivity and multiplicativity of $\iota$ , so $D_n = (n-1)(D_{n-1} + D_{n-2})$ by injectivity.

step 2.1step 3.1L4L6algebra∎

Remarks

Clause 2 is derived from clause 1 and not from the formula. Two instances of clause 1, at $n$ and at $n-1$ , are enough, and that is why clause 2 begins one index later: the second instance needs $n-1 \ge 1$ .
Why clause 1 is stated in $\mathbb{R}$ and clause 2 in $\mathbb{N}$ . Clause 1 carries the term $(-1)^{n}$ , which is not a natural number when $n$ is odd. Clause 2 has no signs left in it, both sides are counts, and injectivity of $\iota$ carries the identity back into $\mathbb{N}$ where it belongs.
The truncated difference is why the hypotheses have to be written out. Under it the symbols $D_{n-1}$ and $D_{n-2}$ never become ill formed: at $n = 0$ the first reads $D_0$ and at $n = 1$ the second reads $D_0$ as well. So a reader cannot tell from the shape of the formula where it stops being proved, and the ranges $n \ge 1$ and $n \ge 2$ have to be stated rather than inferred.

Depends on

Used by

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 89 results over 28 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

Derangement (Wikipedia) (standard reference, not scraped)
Rencontres numbers (Wikipedia) (standard reference, not scraped)
Principle of Inclusion and Exclusion (Open Math Books) (standard reference, not scraped)

ι(Dn)=ι(n) ι(Dn−1)+(−1)n\iota(D_n) = \iota(n)\,\iota(D_{n-1}) + (-1)^{n}ι(Dn​)=ι(n)ι(Dn−1​)+(−1)n for n≥1n \ge 1n≥1, and Dn=(n−1)(Dn−1+Dn−2)D_n = (n-1)(D_{n-1} + D_{n-2})Dn​=(n−1)(Dn−1​+Dn−2​) for n≥2n \ge 2n≥2