Chapter 28: Bijective, Algebraic and Computer-Assisted Enumeration

Can a symbolic identity carry a certificate that explains its truth?

Suppose an exact computation produces the binomial row sums $1,2,4,8,16,\ldots$. The natural conjecture is $S_n=2^n$, where $S_n=\sum_{k=0}^n\binom nk$. A finite list suggests the formula. A certificate explains why it holds at every size and lets a second reader check the decisive steps without repeating the search that found it.

Define $B(n,k)=\binom nk$ for $0\leq k\leq n$, and zero for all other integer $k$, with $n\geq0$. Pascal's identity gives

$$ B(n+1,k)-2B(n,k)=B(n,k-1)-B(n,k). $$

Put $T(n,k)=-B(n,k-1)$. The right side is $T(n,k+1)-T(n,k)$, a difference that telescopes when summed. Both outer endpoints vanish, so the finite sum proves $S_{n+1}=2S_n$. Together with $S_0=1$, it proves the conjecture. The certificate consists of the local identity, the domain convention, the boundary check, and the initial value.

This chapter develops several forms of such evidence: an explicit inverse, a sign-reversing pairing, a determinant or Pfaffian with controlled signs, a telescoping identity, and a polynomial matrix identity. The foundation is the opening example and final investigation; Sections 28.1–28.10 are optional graduate extensions. The prerequisites Inclusion–exclusion and Möbius inversion, Generating functions and recurrence relations, Special counting sequences and lattice paths, and Analytic combinatorics supply the earlier counting language. Linear algebra and algorithmic thinking support the extensions; deeper results invoked without proof are labeled.

28.1 Bijective proofs and sign-reversing involutions

Optional advanced elective extension; not required to complete the chapter foundation. A bijection $\phi:A\to B$ is a map with a specified inverse. To prove a weighted counting identity, additionally require $w(\phi(a))=w(a)$. Finiteness of the relevant classes, or finite dependence at every coefficient, makes the sums well-defined.

Solved bijection. Let $U,V$ be disjoint sets with sizes $r,s$. A $k$-element subset of $U\sqcup V$ corresponds uniquely to a pair $(A,B)$ with $A\subseteq U$, $B\subseteq V$, and $|A|+|B|=k$. The forward map takes intersections; the inverse takes the union. Splitting by $i=|A|$ proves

$$ \sum_i\binom ri\binom s{k-i}=\binom{r+s}k. $$

For $r=3,s=2,k=2$, the cases contribute $1+6+3=10$. This proof explains the intermediate index and the boundary convention that out-of-range binomial coefficients vanish.

For cancellation, give each object a sign $\varepsilon(a)\in\{1,-1\}$. A sign-reversing involution pairs objects through $\iota^2=\mathrm{id}$, preserving their weight and reversing their sign on every nonfixed orbit. Each two-element orbit contributes zero. Fixed points or objects explicitly excluded from the pairing account for the surviving sum; their contribution must be described.

On subsets of $[n]$ with $n\geq1$, toggle membership of label one: $\iota(S)=S\mathbin{\triangle}\{1\}$. This has no fixed point and reverses $(-1)^{|S|}$. With every weight equal to one it proves $\sum_{k=0}^n(-1)^k\binom nk=0$. At $n=3$, the pairs are $\varnothing\leftrightarrow\{1\}$, $\{2\}\leftrightarrow\{1,2\}$, $\{3\}\leftrightarrow\{1,3\}$, and $\{2,3\}\leftrightarrow\{1,2,3\}$. For $n=0$, the empty subset contributes one instead.

Exercise. Prove $\sum_{S\subseteq[n]}(-1)^{|S|}t^{|S\cap\{2,\ldots,n\}|}=0$ for $n\geq1$. Hint: toggle the element absent from the exponent of $t$. Solution: toggling one preserves the displayed exponent while reversing the sign. The same four pairs at $n=3$ cancel coefficientwise in $t$. Weight preservation, rather than sign reversal alone, justifies this polynomial identity.

28.2 Lattice-path bijections and determinant methods

Optional advanced elective extension; not required to complete the chapter foundation. Let $D$ be a finite directed acyclic graph with edge weights in a commutative ring. For distinct sources $A_1,\ldots,A_m$ and distinct sinks $B_1,\ldots,B_m$, let $M_{ij}$ be the sum of weights of directed paths from $A_i$ to $B_j$, where a path's weight is the product of its edge weights. Acyclicity ensures that these path sums are finite.

Expanding $\det M$ gives path families with endpoint permutation $\pi$, weighted by $\operatorname{sgn}(\pi)$. The Lindström–Gessel–Viennot cancellation leaves only families whose paths have no common vertex. Thus the determinant is their signed sum. It is an ordinary positive count when the source–sink arrangement rules out every nonidentity permutation among disjoint families. This extra condition must be checked.

Cancellation proof. Fix a topological ordering of all vertices. In an intersecting family, choose the earliest vertex used by two or more paths, then the lexicographically first pair of path indices meeting there. Swap their tails after that vertex. Both new paths are valid: every tail vertex is later in the topological order than every prefix vertex preceding the selected intersection. The total edge-weight product is unchanged, while two sinks are exchanged and the permutation sign reverses. Earlier vertices and the chosen pair at the selected vertex remain unchanged, so performing the swap again reverses it. All intersecting terms therefore cancel. This classical determinant interpretation appears in Gessel and Viennot, Binomial determinants, paths, and hook length formulae (1985).

Exercise. Why can the term $6$ not simply be described as “six forbidden identity pairs” before proving the tail-swapping correspondence? Hint: inspect which endpoints the negative determinant term uses. Solution: it enumerates crossed endpoint assignments, not identity assignments. The involution establishes their correspondence with intersecting identity pairs in this graph; equality of the two numerical counts alone would not establish the general cancellation rule.

28.3 Rook theory and generalized rook polynomials

Optional advanced elective extension; not required to complete the chapter foundation. A board $B\subseteq[n]\times[n]$ is a set of cells. A nonattacking rook placement uses at most one cell in each row and column. Let $r_k(B)$ count its size-$k$ placements and set

$$ R_B(t)=\sum_{k=0}^nr_k(B)t^k,\qquad r_0(B)=1. $$

If $B$ lists forbidden assignments for a permutation $\sigma$, inclusion–exclusion gives

$$ \#\{\sigma:(i,\sigma(i))\notin B\text{ for every }i\} =\sum_{k=0}^n(-1)^kr_k(B)(n-k)!. $$

Indeed, forcing specified forbidden cells is inconsistent if two share a row or column; otherwise a size-$k$ placement leaves $(n-k)!$ ways to complete the permutation. Rook numbers organize precisely the nonzero inclusion–exclusion terms.

Solved board. Take $B=\{(1,1),(1,2),(2,2),(3,3)\}$. Then $r_1=4$. Among its six cell pairs, $(1,1),(1,2)$ share a row and $(1,2),(2,2)$ share a column, so $r_2=4$. Its only three-rook placement is the diagonal, so

$$ R_B(t)=1+4t+4t^2+t^3,\qquad 6-4\cdot2+4\cdot1-1\cdot1=1. $$

The unique avoiding permutation is $(\sigma(1),\sigma(2),\sigma(3))=(3,1,2)$. In the diagram, shaded cells are forbidden. The left panel shows a two-rook placement on forbidden cells, one term in inclusion–exclusion. The right shows the unique full placement avoiding them. Rows and columns retain the same labels in both panels.

Two useful generalizations retain more information. A weighted rook polynomial sums $t^{|S|}\prod_{c\in S}w_c$ over nonattacking placements $S$. A factorial rook polynomial for a board with $n$ columns uses the basis of falling factorials:

$$ \Phi_B(x)=\sum_{k=0}^nr_k(B)(x)_{\underline{n-k}},\qquad (x)_{\underline j}=x(x-1)\cdots(x-j+1),\quad(x)_{\underline0}=1. $$

For a bottom-justified Ferrers board with nondecreasing column heights $b_1\leq\cdots\leq b_n$, the Goldman–Joichi–White factorization is

$$ \Phi_B(x)=\prod_{j=1}^n(x+b_j-j+1). $$

Proof. For sufficiently large nonnegative integer $x$, adjoin $x$ full rows below the board and place one nonattacking rook in every column. Successive columns offer $x+b_j-(j-1)$ choices because nested columns contain every earlier occupied row. Alternatively, choose the $k$ rooks in the original board in $r_k(B)$ ways, then inject the other $n-k$ columns into the $x$ new rows in $(x)_{\underline{n-k}}$ ways. Equality for infinitely many $x$ proves the polynomial identity. The theorem and broader product generalizations are discussed in Miceli and Remmel, Augmented Rook Boards and General Product Formulas (2008).

For heights $(1,2,3)$, the factorization gives $(x+1)^3=(x)_{\underline3}+6(x)_{\underline2}+7x+1$, so the rook numbers are $1,6,7,1$. This Ferrers board differs from the illustrated forbidden board, whose columns are not nested.

Exercise. Recover the illustrated polynomial by deleting cell $(1,2)$. Hint: split placements according to whether they use that cell; using it removes its row and column. Solution: deletion leaves the three diagonal cells, with polynomial $(1+t)^3$. Contraction leaves only $(3,3)$, with polynomial $1+t$. Hence $R_B(t)=(1+t)^3+t(1+t)=1+4t+4t^2+t^3$.

28.4 Determinantal and Pfaffian enumeration

Optional advanced elective extension; not required to complete the chapter foundation. Determinants encode signed permutations. Pfaffians encode signed perfect matchings, where a perfect matching covers every vertex exactly once. The sign must be controlled in either method before the algebra becomes an ordinary count.

For a skew-symmetric $2m\times2m$ matrix $K$ over $\mathbb Q$ or $\mathbb R$, its Pfaffian is a sum over pairings of the ordered vertex set. Orient each pair as $i\lt j$ and multiply the entries $K_{ij}$; the pairing sign is $(-1)^c$, where $c$ counts interleaving pairs $i\lt k\lt j\lt\ell$. For four vertices this becomes

$$ \operatorname{Pf}(K)=K_{12}K_{34}-K_{13}K_{24}+K_{14}K_{23}, \qquad\det K=\operatorname{Pf}(K)^2. $$

The square identity holds generally; its full algebraic proof is omitted. It does not say that an arbitrary skew adjacency matrix counts matchings positively.

Solved four-cycle. Label a cycle $1,2,3,4,1$ and give each edge weight one. Its perfect matchings are $\{12,34\}$ and $\{14,23\}$. Choose

$$ K=\begin{pmatrix} 0&1&0&1\\-1&0&1&0\\0&-1&0&1\\-1&0&-1&0 \end{pmatrix}. $$

The Pfaffian is $1\cdot1-0+1\cdot1=2$, matching the direct count, and the determinant is four. Replacing $K_{14}$ by $-1$ and $K_{41}$ by $1$ makes the Pfaffian zero, although the underlying graph still has two matchings. The changed sign introduces cancellation rather than destroying a graph edge.

For finite planar graphs with an even number of vertices, Kasteleyn's theorem supplies an edge orientation whose associated skew matrix makes all matching monomials have one overall sign. With nonnegative edge weights, the weighted matching sum is then $|\operatorname{Pf}(K)|$. Constructing and proving the required orientation is an omitted prerequisite of this extension; arbitrary signs do not satisfy it. The planar enumeration method is explained in Kenyon, Lectures on Dimers, Section 3, including its determinant form for bipartite graphs and the Pfaffian extension.

Exercise. On the four-cycle, use weights $a,b,c,d$ for edges $12,23,34,14$ with the same skew signs. Hint: list its two matchings before calculating. Solution: the weighted sum and Pfaffian are both $ac+bd$; the determinant is $(ac+bd)^2$. The matching polynomial is linear in each edge weight because an edge appears at most once in a matching.

28.5 Holonomic sequences and creative telescoping

Optional advanced elective extension; not required to complete the chapter foundation. A sequence $(a_n)$ over characteristic zero is P-recursive, or holonomic, if it satisfies a nontrivial polynomial-coefficient recurrence

$$ \sum_{j=0}^dp_j(n)a_{n+j}=0 $$

for all sufficiently large $n$. An ordinary generating function $A(z)$ is D-finite if a nontrivial linear combination of its derivatives with polynomial coefficients vanishes. These are formal definitions; positive analytic radius is not assumed.

The coefficient and generating-function descriptions are equivalent. Differentiation multiplies coefficients by falling factorials and shifts indices; the operator $z\,d/dz$ multiplies the coefficient at $z^n$ by $n$. These operations translate between recurrences and differential equations, with finite initial terms producing a polynomial forcing term that can be annihilated by further differentiation. This is a standard formal equivalence; the complete general operator conversion is omitted. The approach is developed in Zeilberger, A holonomic systems approach to special functions identities (1990).

Solved conversion. For $b_n=\binom{2n}n$, the factorial ratio gives

$$ (n+1)b_{n+1}=(4n+2)b_n,\qquad b_0=1. $$

Multiplying by $z^n$ and summing over $n\geq0$ yields $B'=4zB'+2B$, hence $(1-4z)B'=2B$. The solution with constant term one is $B(z)=(1-4z)^{-1/2}$. Coefficient comparison in the differential equation reproduces the recurrence, giving a reversible proof certificate.

Creative telescoping seeks polynomials $p_j(n)$ and a term $G(n,k)$ such that

$$ \sum_{j=0}^dp_j(n)F(n+j,k)=G(n,k+1)-G(n,k). $$

For finite supports, summing over a common range gives a recurrence for $\sum_kF(n,k)$ when both outer boundary values of $G$ vanish. Nonzero boundary values produce an inhomogeneous recurrence. Changing supports must be handled before summation; infinite sums additionally need convergence and interchange hypotheses. The certificate can be easy to verify even when its discovery requires substantial symbolic computation.

The opening identity is a first-order certificate with $F=B$, $p_0=-2$, $p_1=1$, and $G=T$. It proves the recurrence for the sum directly rather than fitting that recurrence to initial values.

Exercise. Is $a_n=n!$ holonomic even though its OGF has radius zero? Hint: compare successive terms. Solution: $a_{n+1}-(n+1)a_n=0$, so it is P-recursive. Stirling gives $(n!)^{1/n}\sim n/e$, implying radius zero for the OGF. Formal holonomic manipulation remains valid; analytic contour methods require additional convergence.

28.6 Wilf–Zeilberger (WZ) method

Optional advanced elective extension; not required to complete the chapter foundation. A WZ pair satisfies

$$ F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k). $$

If each row has finite support and the outer $G$ values vanish, $\sum_kF(n,k)$ is independent of $n$. Normalizing an expected closed form into $F$ converts a summation identity into this constant-sum statement. The original certificate framework is Wilf and Zeilberger, Rational Functions Certify Combinatorial Identities (1990).

For hypergeometric terms, the quotients under unit shifts in $n$ and $k$ are rational functions wherever defined. A search can seek $G=RF$ with rational $R$, reducing verification to an algebraic identity after clearing denominators. This is a method for an appropriate class of terms, not a guarantee that every guessed enumerative identity has a first-order WZ certificate.

Solved certificate with complete boundaries. Normalize the binomial sum by the conjectured $2^n$ and define, for all integer $k$ and $n\geq0$,

$$ F(n,k)=2^{-n}B(n,k),\qquad G(n,k)=-2^{-n-1}B(n,k-1). $$

Pascal's identity gives $F(n+1,k)=\tfrac12F(n,k)+\tfrac12F(n,k-1)$, including the zero-extended endpoints. Consequently

$$ F(n+1,k)-F(n,k)=\frac12F(n,k-1)-\frac12F(n,k) =G(n,k+1)-G(n,k). $$

Sum over $k=0,\ldots,n+1$. The outer values are $G(n,0)=0$ and $G(n,n+2)=0$, so the normalized sums agree. At $n=0$ the sum is one. Induction proves $\sum_kB(n,k)=2^n$ for every $n\geq0$.

On $0\leq k\leq n$, the rational certificate is

$$ R(n,k)=-\frac{k}{2(n-k+1)},\qquad G(n,k)=R(n,k)F(n,k). $$

The needed shift ratio is $F(n+1,k)/F(n,k)=(n+1)/(2(n+1-k))$. Interior verification reduces to

$$ \frac{n+1}{2(n+1-k)}-1 =-\frac12+\frac{k}{2(n-k+1)}. $$

After multiplication by the common denominator, both sides have numerator $2k-n-1$. This supplies a small rational-function check. At $k=n+1$, however, the displayed $R$ is undefined and $F(n,k)=0$, while the globally defined shifted-binomial expression gives $G(n,n+1)=-2^{-n-1}\neq0$. Substituting “zero times infinity equals zero” would destroy the proof. The shifted definition, rather than the rational quotient alone, supplies the endpoint value.

Exercise. Check the WZ identity at $k=n+1$. Hint: evaluate both sides before taking quotients. Solution: the left side is $F(n+1,n+1)-F(n,n+1)=2^{-n-1}$. The right side is $G(n,n+2)-G(n,n+1)=0-(-2^{-n-1})$. They agree, including at $n=0$. The full certificate therefore consists of algebra, domain, endpoints, and initial data.

28.7 Constant-term identities

Optional advanced elective extension; not required to complete the chapter foundation. For a finite Laurent polynomial, $\operatorname{CT}_x$ selects the coefficient of $x^0$. All exponent matching is finite, so no contour or convergence assumption is needed. In several variables, the constant term means exponent zero in every variable.

Solved Vandermonde example. For nonnegative integers $r,s$,

$$ \operatorname{CT}_x(1+x)^r(1+x^{-1})^s =\sum_k\binom rk\binom sk =\binom{r+s}s. $$

Expansion proves the first equality by matching exponents. For the second, rewrite the product as $x^{-s}(1+x)^{r+s}$ and select its constant term. At $r=3,s=2$, the sum is $1+6+3=10$. With $r=s=n$, it gives the central binomial coefficient, linking constant terms to the holonomic example.

A deeper finite identity is Dyson's constant-term theorem. For nonnegative integers $a_1,\ldots,a_m$, define

$$ D_{\boldsymbol a}(\boldsymbol x)=\prod_{i\neq j}(1-x_i/x_j)^{a_i}. $$

Then

$$ \operatorname{CT}_{\boldsymbol x}D_{\boldsymbol a} =\frac{(a_1+\cdots+a_m)!}{a_1!\cdots a_m!}. $$

This is an established theorem, despite its historical name as a conjecture. Good's 1970 proof provides a recurrence certificate. Lagrange interpolation of the constant polynomial one, evaluated at zero, gives the rational identity

$$ \sum_i\prod_{j\neq i}(1-x_i/x_j)^{-1}=1. $$

When every $a_i\gt0$, multiplication by $D_{\boldsymbol a}$ yields $D_{\boldsymbol a}=\sum_iD_{\boldsymbol a-\boldsymbol e_i}$. Constant terms satisfy the same recurrence. If $a_i=0$, only nonpositive powers of $x_i$ remain, so taking its constant term deletes that variable and its exponent. The all-zero value is one. These rules determine the result by induction on dimension and total exponent. The multinomial expression has the same boundary values and recurrence, since its predecessor terms sum with ratios $a_i/(\sum_j a_j)$. This proves the theorem.

Exercise. Evaluate the constant term for $m=3$ and all $a_i=1$, and explain the role of the boundary rule. Hint: each predecessor has a zero exponent. Solution: every predecessor reduces to the two-variable case with exponents $(1,1)$, whose constant term is two. There are three predecessors, giving six, equal to $3!$. The boundary rule makes the recurrence an independently usable certificate rather than an equation lacking initial conditions.

28.8 Transfer matrices and automata-based enumeration

Optional advanced elective extension; not required to complete the chapter foundation. A finite-state model remembers only the information needed to decide the next legal step. In a deterministic labeled automaton, every word has at most one path from its specified start. Counting paths then counts accepted words. A nondeterministic model may count several paths for the same word, so this correspondence must be justified.

Consider binary words avoiding the adjacent pattern $11$, including the empty word. State $A$ means the prefix is empty or ends in zero; state $B$ means it ends in one. The transitions are:

Both states accept, and the start is $A$. With rows indicating the current state and columns the next state, the transition-count matrix is

$$ M=\begin{pmatrix}1&1\\1&0\end{pmatrix},\qquad s=\begin{pmatrix}1&0\end{pmatrix},\qquad t=\begin{pmatrix}1\\1\end{pmatrix}. $$

The number of length-$n$ accepted words is $a_n=sM^nt$. Induction on the word length proves this: each entry in a matrix product sums over one intermediate state and one legal next symbol. The local state description also proves that acceptance is equivalent to avoiding $11$, including words ending in one.

Solved enumeration. The counts through length six are $1,2,3,5,8,13,21$. Cayley–Hamilton gives $M^2=M+I$, so $a_{n+2}=a_{n+1}+a_n$. Alternatively, a legal word of length $n\geq2$ starts with $0$ followed by any legal word of length $n-1$, or with $10$ followed by any legal word of length $n-2$. The two prefix classes are disjoint and their removal maps have inverses, giving the same recurrence with $a_0=1,a_1=2$.

Mark each one by $u$. The matrix becomes $M(u)=\begin{pmatrix}1&u\\1&0\end{pmatrix}$. Multiplication now weights a path by $u^{\#1}$ and retains the same unique-path interpretation. Transfer matrices can contain cycles because they enumerate a fixed length at each coefficient, unlike the unrestricted finite-path sums used in the acyclic determinant setting.

Exercise. Find the length-four polynomial in $u$. Hint: choose one positions with no adjacency. Solution: there is one all-zero word, four placements of one one, and three placements of two ones: $0101,1001,1010$. Thus the polynomial is $1+4u+3u^2$, whose value at $u=1$ is eight.

28.9 Symbolic computation of generating functions

Optional advanced elective extension; not required to complete the chapter foundation. Solving a formal linear system can produce a generating function together with an exact certificate. For a finite-state transition matrix $M$, start row $s$, and accepting column $t$, the formal geometric series gives

$$ A(z)=\sum_{n\geq0}sM^nt\,z^n=s(I-zM)^{-1}t. $$

The inverse exists as a formal power series because $I-zM$ has constant term $I$. This argument establishes rationality without assuming analytic convergence or numerically inverting a matrix at selected points.

Solved symbolic system. Let $h_A,h_B$ count allowed suffixes starting in the two states of Section 28.8. Since either state permits an empty suffix,

$$ h_A=1+z(h_A+h_B),\qquad h_B=1+zh_A. $$

Elimination gives

$$ h_A=\frac{1+z}{1-z-z^2},\qquad h_B=\frac1{1-z-z^2}. $$

The start state is $A$, so $A(z)=h_A$. Multiplying by the denominator yields $a_0=1$, $a_1-a_0=1$, and $a_n-a_{n-1}-a_{n-2}=0$ for $n\geq2$. The numerator carries initial-condition information; the denominator alone does not determine the count.

An exact certificate avoids trusting the elimination step. Set $D(z)=1-z-z^2$ and $v(z)=(1+z,1)^{\mathsf T}$. Direct multiplication verifies

$$ (I-zM)v(z)=D(z)t. $$

Its first coordinate is $(1-z)(1+z)-z=D(z)$, and its second is $-z(1+z)+1=D(z)$. Since $D(0)=1$, division is valid formally, and uniqueness of the linear system proves the rational function.

For a model with $d$ states, dense exact elimination uses $O(d^3)$ field operations in a conventional implementation. Rational-function degrees and integer coefficient sizes may grow, so this is not a bit-complexity guarantee. Once a candidate numerator vector and denominator are supplied, an independent checker only needs polynomial matrix multiplication, the unit constant term, and the state-model justification.

Exercise. Retain the one-marking variable and find a symbolic certificate. Hint: use $M(u)$, $D(z,u)=1-z-uz^2$, and $v(z,u)=(1+uz,1)^{\mathsf T}$. Solution: $(I-zM(u))v=D(z,u)t$, so the generating function is $(1+uz)/(1-z-uz^2)$. Its $z^4$ coefficient is $1+4u+3u^2$, checking the weighted enumeration independently.

28.10 Automated conjecture discovery and proof certificates

Optional advanced elective extension; not required to complete the chapter foundation. Discovery and verification solve different problems. A discovery program may enumerate small objects, fit recurrences, search for rational functions, or seek a telescoping multiplier. A verifier checks the resulting finite evidence against a stated theorem and its hypotheses. The output should identify the exact combinatorial model and all domain and boundary conventions.

Solved discovery trace. From $a_0,\ldots,a_5=1,2,3,5,8,13$, seek an order-two constant-coefficient recurrence $a_n=ca_{n-1}+da_{n-2}$. The first two equations are $3=2c+d$ and $5=3c+2d$, whose unique rational solution is $c=d=1$. It correctly predicts the next displayed terms. This is a plausible conjecture, not an infinite proof. For any finite cutoff $N$, the sequence $b_n=a_n+\binom n{N+1}$ agrees through $N$ and differs at $N+1$.

Attach the two-state automaton and polynomial identity from Section 28.9. The verifier checks four labeled transition cases, the start and accepting states, and the two polynomial coordinates of $(I-zM)v=Dt$. The finite state invariant proves that every allowed word has exactly one accepted path. The polynomial identity and $D(0)=1$ prove the generating function at every degree. The recurrence now follows as a theorem, and its constant leading coefficient makes its two initial values sufficient.

A useful certificate contract has these fields:

For WZ, propagation is telescoping plus induction. For a generating-function system, it is uniqueness of the formal solution. For a sign-reversing involution, it is cancellation of all two-element orbits with an explicit description of survivors. Finite exact checks support these proofs by detecting implementation mistakes; floating-point residuals and long fitted prefixes are evidence of a different kind.

Exercise. Does $(n-2)(b_{n+1}-b_n)=0$ for all $n\geq0$, together with $b_0=0$, uniquely determine the sequence? Hint: inspect the step $n=2$. Solution: it forces $b_1=b_2=0$, but leaves $b_3$ arbitrary, after which every later value equals $b_3$. Both the zero sequence and $0,0,0,1,1,1,\ldots$ satisfy the stated data. A polynomial-coefficient recurrence certificate must account for exceptional indices where its leading coefficient vanishes.

Produce an enumerative conjecture and an independently checkable certificate

The investigation counts binary words of length $n$ avoiding $11$. It connects a prefix-removal bijection with an exact matrix certificate, using the same model for discovery, proof, and checking. The two-state witness below contains everything required for the foundation investigation; the optional WZ and constant-term extensions supply other certificate types.

Part A: warm-up and discovery, 35 points. Enumerate valid words through length twelve. Use the first terms to solve for coefficients in $a_n=ca_{n-1}+da_{n-2}$, then test predictions on additional lengths. Hint: enumeration can generate all bit words and reject those containing $11$, or extend only legal prefixes while retaining the two states.

Verified counts. For $n=0,\ldots,12$, the values are

$$ 1,2,3,5,8,13,21,34,55,89,144,233,377. $$

At length four the eight words are $0000,0001,0010,0100,0101,1000,1001,1010$. The equations $3=2c+d$, $5=3c+2d$ give $c=d=1$. A candidate OGF is $(1+z)/(1-z-z^2)$. The finite checks support these conjectures; the following parts certify them.

Part B: bijective proof, 25 points. For $n\geq2$, split a valid word by its initial symbols and give explicit deletion and reconstruction maps. Include the cases $n=0,1$. Hint: the initial alternatives are $0$ and $10$.

Worked solution. A word beginning with zero is uniquely $0v$, with $v$ any valid length-$(n-1)$ word. A word beginning with one must next have zero, and is uniquely $10v$, with $v$ any valid length-$(n-2)$ word. Removing or adding the prefix gives inverse maps, and the added prefixes cannot create $11$ at the join because their last symbol is zero. These two classes are disjoint and exhaustive. Hence $a_n=a_{n-1}+a_{n-2}$, with one empty word and two length-one words. Induction establishes the recurrence for every length. This is a direct bijection certificate, rather than a fit to the observed numbers.

Part C: polynomial certificate, 25 points. Use

$$ M=\begin{pmatrix}1&1\\1&0\end{pmatrix},\quad s=\begin{pmatrix}1&0\end{pmatrix},\quad t=\begin{pmatrix}1\\1\end{pmatrix},\quad v=\begin{pmatrix}1+z\\1\end{pmatrix},\quad D=1-z-z^2. $$

Verify $(I-zM)v=Dt$ and prove why it determines the counting function. Hint: compare the constant terms before solving the formal linear system.

Worked solution. The first coordinate is $(1-z)(1+z)-z=1-z-z^2$ and the second is $-z(1+z)+1=1-z-z^2$. Thus the identity is exact. The system $h=t+zMh$ has unique formal coefficients: $h_0=t$ and $h_n=Mh_{n-1}$ for $n\geq1$. Since $D(0)=1$, the candidate $h=v/D$ satisfies it and is that unique solution. Taking the start coordinate gives $A(z)=sh=(1+z)/D$. The accepting column includes both states, so a final one is allowed; replacing it by $(1,0)^{\mathsf T}$ would count a different family.

Independent checker outline. First inspect the three legal transitions and the rejected fourth case to verify the state invariant by induction. Next represent $D$ and both coordinates of $v$ as exact integer coefficient arrays. Multiply by $I-zM$, subtract $Dt$, and check every residual coefficient. Finally check the constant term of $D$ and select the start coordinate. This verification uses neither the recurrence-fitting procedure nor numerical inversion, and its short residual identities justify all sizes through formal uniqueness.

Part D: verification and application, 15 points. Compare direct enumeration, the bijective recurrence, matrix powers, and coefficient extraction through the cutoff. Explain how an encoder that excludes adjacent ones can use the count. Hint: every accepted word is a possible codeword; a fixed-length injective encoding needs enough distinct outputs.

Solution outline. All four methods give the displayed counts. Direct enumeration of all words through a cutoff $N$ costs exponential work, while the two-term recurrence uses $O(N)$ integer additions and the state system uses constant many updates per length; these are arithmetic operation counts. At length four, eight permissible words encode three message bits injectively into four channel symbols by assigning the eight messages to the eight words. In general at most $\lfloor\log_2a_n\rfloor$ binary message bits can be assigned this way. This describes a spacing constraint and codebook capacity, rather than an error-correction guarantee. The proved state model and certificate make the count reusable without rerunning exhaustive enumeration.

Optional marked extension, ungraded. Let $a_{n,k}$ count valid words with exactly $k$ ones. Prove

$$ a_{n,k}=\binom{n-k+1}k,\qquad \sum_{n,k\geq0}a_{n,k}z^nu^k=\frac{1+uz}{1-z-uz^2}, $$

for $n\geq0$ and $0\leq k\leq\lfloor(n+1)/2\rfloor$, with $a_{n,k}=0$ outside that range. Solution route: if one positions are $i_1\lt\cdots\lt i_k$ with differences at least two, map them to $j_r=i_r-(r-1)$. These are $k$ distinct positions in $[n-k+1]$, and adding the staircase recovers the original positions. Independently verify $(I-zM(u))(1+uz,1)^{\mathsf T}=(1-z-uz^2)t$. This gives both a size-and-statistic bijection and an algebraic certificate.

Optional telescoping extension, ungraded. Reproduce the opening binomial sum proof as the WZ pair $F(n,k)=2^{-n}B(n,k)$ and $G(n,k)=-2^{-n-1}B(n,k-1)$. Check the interior rational identity, the endpoint $k=n+1$, the outer zero values, and the initial row separately. This is an exercise in verifying an established identity, not a claim of a newly discovered research result.