Solve recurrences as formal power series

Try

A tiling of a board of length n by squares of length one and dominoes of length two has a simple last-piece decomposition. Let a_n count tilings, with a_0=1 for the empty board and a_1=1. The last piece is a square or domino, so a_n=a_(n−1)+a_(n−2). The recurrence is combinatorial; a generating function packages all of its values into one algebraic equation.

Predict

Predict which initial terms must be removed when shifting a sum. If A(z)=Σ from n≥0 of a_n z^n, then summing the recurrence from n=2 gives A−1−z on the left, z(A−1)+z²A on the right. Forgetting the subtraction inside z(A−1) produces a different numerator and therefore a different sequence. Initial conditions are part of the equation, not optional annotations.

Experiment

Build the first coefficients before doing algebra.

Board length	0	1	2	3	4	5
Tiling count	1	1	2	3	5	8

Now solve A(1−z−z²)=1. Multiply the proposed series by the denominator and check that every coefficient after the constant vanishes. This is an independent check of both the recurrence and the boundary terms.

Understand

An ordinary generating function is a formal series A(z)=Σa_n z^n. Equality means coefficientwise equality. Products use finite convolution: the coefficient at n is Σ from k=0 to n of a_k b_(n−k). Thus the algebra is meaningful without assigning a numerical value to z. A series with nonzero constant coefficient has a unique formal inverse, found recursively, so denominators such as 1−z−z² are legitimate. More generally a constant-coefficient linear recurrence yields a rational generating function whose denominator records the recurrence and whose numerator records the initial conditions and any finite forcing terms.

Apply

When the denominator factors, partial fractions recover explicit coefficients. Since 1/(1−λz)=Σλ^n z^n, simple factors yield exponential terms. Repeated factors yield polynomial multipliers: 1/(1−z)² has coefficient n+1 by convolution, and more generally (1−z)^(−k) has coefficient C(n+k−1, k−1). This explains the repeated-root terms in recurrence solutions rather than treating them as a memorized exception. For the tiling example, factoring over the reals produces the two Fibonacci characteristic roots; the irrational terms combine to give integer coefficients because they represent the same uniquely determined formal series.

For a concrete repeated-root check, let b_n=n+1. Its second difference is zero, so b_n=2b_(n−1)−b_(n−2), with b_0=1, b_1=2. Summing gives B(z)=1/(1−z)². The recurrence, the convolution count and the coefficient formula all agree. This three-way agreement is stronger evidence than checking only the first two values of a guessed closed form.

Continue

Use coefficient extraction for weighted choices as well. The coefficient of z^n in 1/((1−z)(1−z²)) counts solutions x+2y=n, since the factors choose the multiplicities of parts one and two. The introductory generating-function lesson supplies the basic notation; here the emphasis is exact recurrence translation and repeated factors. Analytic questions such as convergence radius and asymptotic estimates require additional justification after the formal identity has been established.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with count labeled products with exponential series.