Recurrence relations and counting

Let a strip of integer length n be tiled with unit squares and length-two dominoes, all tiles having one color. Every nonempty tiling ends either with a square or with a domino. Removing that last tile leaves a tiling of length n minus one or n minus two, respectively. These cases are disjoint because their final tiles differ, and exhaustive because no other tile lengths are allowed. Reattaching the removed tile provides the inverse map in each case.

The empty strip has one tiling, and the length-one strip has one tiling. With these initial values, the recurrence determines each later value by induction. Defining the count at negative lengths to be zero can simplify formulas, but that is an explicit convention rather than another physical strip. A different tile palette changes the recurrence: two square colors contribute twice the shorter-strip count. The coefficients record the number of reversible extension choices, not an adjustment guessed after comparing a few terms.

Consider binary words with no adjacent ones. To append a zero, every valid shorter word is eligible; to append a one, only words ending in zero are eligible. A total count alone does not describe those eligibility classes, so temporarily keep separate counts for final zero and final one. The empty word needs its own initial interpretation, or the length-one cases can be supplied directly. This state-based view is the counting analogue of tracking sufficient boundary data in an algorithm.

State transitions count extensions, whereas a stochastic transition matrix distributes probability. These should not be confused: both may use matrix multiplication, but their entries have different meanings and their row sums obey different rules. Finite-state recurrences are particularly effective for restrictions on a bounded window of recent symbols. If eligibility depends on an unbounded statistic, the state may need to grow with size. Claiming that a finite state captures the rule requires proving that two histories in that state have identical future possibilities.

A proposed recurrence should be checked at its first valid index and against small direct enumerations. This catches missing empty objects, overlapping cases, and off-by-one choices of size. To establish uniqueness, assume all previous values have been determined and use the recurrence to determine the next. A closed form then needs to satisfy both the recurrence and every required initial value. Matching only the recurrence leaves an entire family of possible sequences.

Recurrences can be computationally useful even without a closed form. Tabulating each value once avoids the duplicated work of a naive recursive program. Integer arithmetic keeps counts exact; machine integers may overflow long before the underlying structural argument fails. A recurrence that subtracts large counts can also be less numerically stable in floating-point arithmetic than one with positive terms. The proof, the algorithm, and the chosen numeric representation are separate parts of a trustworthy counting calculation.