ExampleConstruction: AI-generatedVerification: AI-generatedprecheck 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.

Binary words avoiding $101$ have generating function $(1 + x^{2}) / (1 - 2 x + x^{2} - x^{3})$

Example

Let $a_{n}$ be the number of binary words of length $n$ that avoid $101$ . Then

$\sum_{n \geq 0} a_{n} x^{n} = \frac{1 + x^{2}}{1 - 2 x + x^{2} - x^{3}} .$

The first values are

$a_{0}, a_{1}, \dots, a_{6} = 1, 2, 4, 7, 12, 21, 37.$

Facts & Assumptions

Given: The singleton forbidden set $B = {101}$ over ${0, 1}$ .

[L1]

The prefix automaton uses the allowed proper-prefix states and the longest suffix transition (The longest-suffix prefix automaton for a finite set of forbidden factors).

[L2]

Its fixed-entry walk series are cofactors of $I - x A$ divided by $\det (I - x A)$ (Transfer-matrix theorem: weighted-walk generating functions are cofactors of $I - x A$ divided by $\det (I - x A)$ ).

Verification

technique · transfer matrix with finite enumeration check

1.1givenL1

By [L1], the states are $ε, 1, 10$ and, in that order, their transfer matrix is $A = (\begin{matrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \end{matrix})$ . The missing transition from $10$ on $1$ is precisely the rejected factor $101$ .

2.1step 1.1L2algebra

Avoiding words are walks from $ε$ to any state. Summing the three corresponding entries supplied by [L2], or solving $(I - x A) y = 1$ , gives $(1 + x^{2}) / (1 - 2 x + x^{2} - x^{3})$ .

3.1step 2.1algebra∎

Direct enumeration by length gives $1, 2, 4, 7, 12, 21, 37$ through length six. These values also satisfy $a_{n} = 2 a_{n - 1} - a_{n - 2} + a_{n - 3}$ for $3 \leq n \leq 6$ , as the denominator in step 2.1 requires.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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

Binary words avoiding 101101 have generating function (1+x2)/(1−2x+x2−x3)(1+x2)/(1−2x+x2−x3)