TheoremStatement: Literature-sourcedProof: Literature-sourcedjudge pass (gpt-5.6-terra)audited 2026-08-28

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.

Exact-k partition recurrence

Statement

For every integer $n$ and every integer $k \geq 1$ ,

$p_{k} (n) = p_{k - 1} (n - 1) + p_{k} (n - k) .$

Facts & Assumptions

Given: an integer $n$ and an integer $k \geq 1$ .

[F1]

The quantity $p_{k} (n)$ counts partitions of $n$ into exactly $k$ positive parts, and it is defined to be $0$ when $n < 0$ or $k < 0$ (The functions p(n), p_k(n), and the standard restricted partition families).

Proof

technique · decomposition

1.1F1

A partition of $n$ into exactly $k$ positive parts either contains a part equal to $1$ or has every part at least $2$ . These two cases are disjoint and exhaustive.

2.1step 1.1F1construct

In the first case, delete one part equal to $1$ . The remaining parts still form a partition, now of $n - 1$ , and they are exactly $k - 1$ positive parts. Conversely, adjoining one part equal to $1$ to any partition of $n - 1$ into $k - 1$ positive parts gives a partition of $n$ into $k$ positive parts containing a $1$ . So the first case contributes $p_{k - 1} (n - 1)$ .

2.2step 1.1F1construct

In the second case, subtract $1$ from each of the $k$ parts. Because each part was at least $2$ , the result is a partition of $n - k$ into exactly $k$ positive parts. Conversely, adding $1$ to each part of any partition of $n - k$ into $k$ positive parts recovers a partition of $n$ into $k$ parts all at least $2$ . So the second case contributes $p_{k} (n - k)$ . If $n - k < 0$ , then [F1] makes this contribution $0$ , exactly as it should.

3.1step 2.1step 2.2∎

The two disjoint cases of steps 2.1 and 2.2 cover every partition counted by $p_{k} (n)$ , so their cardinalities add to $p_{k} (n)$ . This is the stated recurrence.

Depends on

The functions p(n), p_k(n), and the standard restricted partition families

Used by

The recurrence gives p₃(5)=2 Example
FALSE: pₖ(n) is counted by C(n-1, k-1) False statement

Dependency tree · two levels

3 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

Darij Grinberg, Enumerative Combinatorics: class notes (standard reference, not scraped)