Section 2.3

Recursions

Counts that satisfy a recurrence: staircase (Fibonacci) problems, binary strings with forbidden patterns, tilings, regions cut by lines, sorting passes.

Toolkit

Many counting problems decompose by conditioning on the last (or first) element, cell, or move, yielding a linear recurrence $a_n$ satisfies in terms of $a_{n-1}, a_{n-2},\dots$ ; solve via telescoping, characteristic roots, or direct bijection to tilings/strings.

Key facts:

Fibonacci recursion $F_n=F_{n-1}+F_{n-2}$ counts: tilings of a $1\times n$ strip by squares/dominoes, binary strings of length $n$ avoiding a fixed consecutive pattern (e.g. no HH), subsets of $\{1,\dots,n\}$ with no two consecutive elements.
Closed form $F_n=\frac{\varphi^n-\psi^n}{\sqrt5}$ , $\varphi=\frac{1+\sqrt5}{2}$ ; ratios $F_{n-1}/F_n\to 1/\varphi$ govern limiting densities.
Lines/planes cutting regions: $k$ -th new line adds at most $k-1$ intersection points, hence at most $k$ new regions; $R_n = R_{n-1}+n = 1+\binom{n+1}{2}$ for the plane.
For boards/strips of fixed small width (e.g. $3\times n$ ), set up coupled recursions for the full count and for “defect” shapes (missing a corner/cell), solving the linear system simultaneously.
Each independent local binary choice (fire/not-fire a swap, choose/not-choose a tile) that corresponds bijectively to outcomes gives counts $2^{m}$ .

Problems