11. Basics of recurrence relations#

In earlier units, we counted configurations directly using the sum, product, difference, and division rules, or packaged an entire sequence of counts into an ordinary generating function. For many combinatorial problems, however, an explicit formula is not immediately apparent either because a closed formula does not exist or because it is not obvious how to derive it. Expressing the counts in terms of recurrence relations, when quantities associated to larger values of depend on quantities for smaller values of , is a way to help with bookkeeping, implement efficient counting algorithms, and often derive closed formulas for counts.

Consider counting the ordered ways to write a positive integer as a sum of s and s. For , the possibilities are Because order matters, and are different outcomes. Listing every possibility by hand works for small values of , but it quickly becomes error-prone for larger values of .

Instead of constructing every list of size from scratch, we look for an inductive structure: how can an allowed object of size be decomposed into smaller objects of the same kind? This perspective leads to a recurrence relation,an equation that computes each term of a sequence from earlier terms. In this note, we examine how to formulate recurrences from combinatorial decompositions, analyze their order and algebraic classification, and connect them to ordinary generating functions.

After studying these notes, you will be able to do the following.

Derive a recurrence relation by decomposing a set of combinatorial objects into mutually exclusive cases.
Identify the order of a recurrence, specify its required initial conditions, and determine its valid index range.
Classify a recurrence as linear or nonlinear, constant-coefficient or variable-coefficient, and homogeneous or nonhomogeneous.
Convert a constant-coefficient linear recurrence into an algebraic equation for its ordinary generating function, accounting for initial conditions.
Extract the recurrence relation and initial values satisfied by the sequence of coefficients of a rational generating function.
Model combinatorial structures such as: ordered compositions, pattern-avoiding strings, and restricted walks using recurrences and auxiliary state sequences.

11.1 Decomposing ordered sums into smaller subproblems#

Let be the number of ordered lists of parts chosen from whose entries sum to . We include the empty list, written , as the unique list with sum , so .

For small values of , we can find by exhaustive listing:

To determine without listing all possibilities, let and classify each list by its final entry. Every list of positive sum has at least one entry, and because the allowed parts are only and , every list falls into exactly one of two cases:

Case 1: The list ends in . A list in this case has the form . Removing the trailing leaves , which is an ordered list of s and s with sum . Conversely, appending to any ordered list with sum produces a valid list of sum ending in . Because removing the trailing and appending are mutual inverses, lists of sum ending in are in bijection with lists of sum . There are exactly such lists.
Case 2: The list ends in . A list in this case has the form . Removing the trailing leaves , which is an ordered list of s and s with sum . Conversely, appending to any ordered list with sum produces a valid list of sum ending in . These two operations are mutual inverses, so lists of sum ending in are in bijection with lists of sum . There are exactly such lists.

Every valid list belongs to exactly one of these two cases because its final entry is either or , never both. The sum rule therefore gives

Starting from and , we can run the recurrence one term at a time: For , the recurrence organizes the eight lists into two groups. Highlighting the final part shows exactly which earlier list produced each one: Thus . The recurrence provides a bookkeeping rule: reuse the complete lists for sums and , append the appropriate final part, and obtain every list of sum exactly once.

Notice why the condition is necessary: if , the only list is , which ends in . It cannot end in because , and lists with negative sum do not exist. The recurrence requires two previous values, so the values and cannot be produced by the recurrence; they must be provided as initial conditions.

Together with and , the recurrence determines the entire sequence successively: These counts are the Fibonacci numbers shifted by one index: . The recurrence encodes the method of subdividing the problem at each step into subproblems associated to prior steps.

The same idea applies when more part sizes are allowed.

Example 1 (Ordered sums using parts of size one, two, and three)#

Let count the number of ordered lists of parts chosen from whose sum is . The initial values are because the lists for sums , , and are ; ; and , respectively.

For , every list ends in exactly one of , , or . Removing that final part leaves an ordered list with sum , , or , respectively. These three disjoint cases give For example, The four lists counted by are .

Example 2 (Tilings with multiple tile varieties of the same size)#

How many ways can a board be tiled using squares of length , dominoes of length , red triominoes of length , and blue triominoes of length ? Let denote the number of tilings.

The first row shows a length-one square, a length-two domino, a red length-three triomino, and a blue length-three triomino. The second row shows a length-nine board tiled, from left to right, by one square, one domino, one red triomino, and one blue triomino. — Figure 1: The four available tiles and one sample tiling. The red and blue triominoes have the same length but remain distinct choices.#

Solution: The initial values are For , classify a tiling by its rightmost tile. A tile leaves a board of length , a domino leaves one of length , and either color of triomino leaves one of length . Hence Thus the complete recurrence relation is

11.2 Recurrences, order, and initial conditions#

A recurrence relation is a propagation rule for continuing a sequence. By itself, the rule does not identify a unique sequence; starting values are an indispensable part of the definition.

Definition 3 (Recurrence relation, order, and initial conditions)#

A complete recurrence relation of order for a sequence consists of an update rule together with initial conditions: The update function must genuinely depend on ; thus is the earliest term used and the order is . The initial conditions start the computation, and the update rule then determines every term uniquely.

The order measures how far into the past the recurrence reaches. For instance, the recurrence has order , even though only two terms appear on the right-hand side. Computing requires and ; thus, three initial values () must be known before the recurrence can run.

Example 4 (The same recurrence with different initial conditions)#

Consider the order- recurrence for . Different initial conditions select entirely different sequences:

With and , we obtain the shifted Fibonacci numbers:
With and , we obtain the numbers (they have a name: “Lucas numbers”):
With and , every term is zero: .

The recurrence provides the propagation mechanism, the initial conditions anchor the sequence.

For the recurrences studied in this unit, three structural properties describe the form of the equation.

Definition 5 (Linear recurrence relation)#

An order- recurrence relation is linear if it can be written as where the coefficients and the term depend only on the index , and not on any terms of the sequence .

It has constant coefficients if each coefficient is a constant number independent of , with .
It is homogeneous if for all .
It is nonhomogeneous (or inhomogeneous) if is not identically zero. The function is called the driving term or inhomogeneous term.

Example 6 (Classifying recurrence relations)#

We classify each of the following recurrences by its order, linearity, coefficient type, and homogeneity:

: linear, order , constant coefficients (), homogeneous.
: linear, order , constant coefficients, nonhomogeneous with driving term .
: linear, order , variable coefficients (since depends on ), homogeneous.
: linear, order , constant coefficients (), homogeneous.
: nonlinear of order , because the earlier sequence terms and are multiplied together.
: nonlinear recurrence of variable order, as seen for the Catalan numbers in Unit 2.

Warning (A recurrence must specify initial conditions and an index range)#

An equation alone does not define a sequence. Consider the relation .

With initial conditions and , the sequence is constant:
With initial conditions and , the sequence grows linearly:
If only is specified, the term cannot be evaluated because is undetermined. An order- recurrence cannot begin without two initial values.

Similarly, the valid range of indices is essential. Applying at for a sequence indexed on would require , an undefined quantity. Always state the initial conditions and the range of for which the recurrence is valid.

11.3 From a recurrence to an ordinary generating function#

Let be the ordinary generating function of . Multiplying by shifts the sequence of coefficients by places: Because each term in a constant-coefficient linear recurrence corresponds to a shifted series , we can translate the recurrence into an algebraic equation for .

11.3.1 The procedure for second-order recurrences#

To understand how the algebra works, consider an order- linear homogeneous recurrence with constant coefficients: with initial conditions and . We convert this recurrence into an algebraic equation for using three steps.

Multiply and sum over the valid index range. Multiply the recurrence by and sum over all indices where the recurrence holds:
Express each sum in terms of . The sum on the left-hand side is missing the first two terms of : For the first sum on the right-hand side, factor out to align the exponent of with the index of : For the second sum, factor out : Substituting these three representations back into the summed recurrence gives
Collect and solve. Move all terms containing to the left-hand side and all initial condition terms to the right-hand side: Dividing by yields the generating function:

Notice the structure of the result:

The denominator is determined entirely by the recurrence relation.
The numerator is determined by the initial conditions.

Example 7 (Generating function for ordered sums of ones and twos)#

Let count the ordered lists of s and s with sum , as in Section 11.1. We found Thus . The denominator determined by the recurrence is and the numerator determined by the initial conditions is Therefore, the ordinary generating function is In Unit 2, we obtained the same result by building an ordered list from parts with generating polynomial : The recurrence strips off the final part, while the geometric series builds the list by appending parts. These complementary decompositions produce the same generating function.

11.3.2 The general order- theorem#

The same three-step procedure applies to linear recurrences of any finite order , including nonhomogeneous equations.

Theorem 8 (Generating function of a linear recurrence with constant coefficients)#

Let satisfy the order- linear recurrence where are constants with . Define Then where is a polynomial of degree at most determined by the initial conditions: Consequently,

Proof#

Multiply the recurrence by and sum over all indices : On the left side, the first sum is For each , the shifted sum satisfies Substituting these expressions into the equation gives Moving the finite sums of degree less than to the right side defines : In the double sum, let . The exponent ranges from to , and for each fixed , the index ranges from to with . Grouping by powers of gives the coefficient of as . This establishes the formula for . Dividing by completes the proof.

Corollary 9 (Homogeneous linear recurrences have rational generating functions)#

If the recurrence in Theorem 8 is homogeneous, then for all , so . In this case, is a rational function whose denominator has degree and constant term , and whose numerator has degree at most and is determined by the initial data. More generally, whenever the driving series is a rational function, is rational.

Warning (Do not omit the numerator correction for initial conditions)#

A frequent student error when converting an order- recurrence to a generating function is to write This expression is correct only in the special circumstance that . If , expanding forces the degree- coefficient to be instead of . The term in the numerator is the exact correction required to match the independent initial condition .

Problem 10 (Applying the theorem to an order- recurrence)#

Let satisfy with , , and . Use Theorem 8 to find . First determine the denominator from the recurrence. Then write the unknown initial polynomial as and determine from the initial data.

Solution:

Find the denominator. Here , , and , so the theorem gives
Fit the initial polynomial to the initial data. Because the recurrence is homogeneous, the theorem gives Equivalently, Using only the coefficients through degree , Therefore,

11.4 From a rational generating function to a recurrence#

We can also read the connection between rational generating functions and recurrences in reverse. Multiplying a rational generating function by its denominator produces a polynomial, whose coefficients must eventually vanish.

Proposition 11 (Rational generating functions determine eventual recurrences)#

Suppose the ordinary generating function of a sequence is a rational function where is a polynomial and . Then for all with , the sequence satisfies the constant-coefficient linear recurrence

Proof#

Apply Theorem 8 in reverse. Multiplying by the denominator gives The theorem says that an identity of this form corresponds to the recurrence where . For every , we have . Hence the recurrence is homogeneous for all with .

The condition explains why the recurrence is called eventual. If , the condition holds automatically for all , so the recurrence holds from onward without exception. If , the early coefficients for receive nonzero contributions from , behaving like nonhomogeneous driving terms. Once exceeds the degree of the numerator, the homogeneous recurrence takes over permanently.

Example 12 (Reading a recurrence and initial values from a rational function)#

Consider the rational generating function Determine the recurrence relation, its valid index range, and the initial conditions satisfied by .

Solution:

Find the recurrence and its valid range. Write the denominator in the standard form Thus , , and the recurrence has order . Since the numerator has degree , Proposition 11 applies at every :
Find the initial conditions. Use the identity Equating the coefficients of and gives Therefore and .

Using the recurrence with initial values and , we compute the next few terms:

As an independent check, we can expand using partial fractions (as studied in Unit 2). The denominator factors as . Setting we find and . Expanding both geometric series gives The explicit formula is . Evaluating this formula for small gives confirming the recurrence computation at every step.

11.5 Pattern-avoiding strings#

A string over an alphabet avoids a pattern if does not appear as a contiguous substring in any position. For instance, the binary string 0010 contains 00 in its first two positions and therefore does not avoid 00.

Pattern avoidance is a global condition, not merely a restriction on how a string ends. The string 0011 ends in 11, but it contains 00 at its start, so it fails to avoid 00.

11.5.1 Binary strings avoiding repeated zeroes#

Let count the number of length- binary strings over that avoid 00.

For , the empty string contains no characters and vacuously avoids 00, so .
For , both length- strings 0 and 1 avoid 00, so .

For , every valid string ends in either 1 or 0.

Case 1: The string ends in 1. A string in this case has the form . Because the added final character is 1, it cannot complete a forbidden block 00. Therefore, avoids 00 if and only if the prefix avoids 00. There are such strings.
Case 2: The string ends in 0. Because and the string avoids 00, the character immediately preceding the final 0 cannot be 0. It must be 1. Thus, every valid string ending in 0 actually ends in the two-character block 10: Because the block 10 begins with 1, appending it to any valid string of length cannot create 00. Therefore, avoids 00 if and only if the prefix avoids 00. There are such strings.

Because every valid string ends in either 1 or 0, the two cases partition the set of valid strings: With and , the sequence begins: For , among the binary strings, only 00 is forbidden, leaving 01, 10, 11, which confirms .

Using our generating function formula for order- recurrences: Compare this with the ordered-sum generating function from Example 7. The recurrence relation is identical, but the initial conditions differ ( instead of ). That difference in initial conditions produces the numerator rather than .

Example 13 (Binary strings avoiding three consecutive zeroes)#

Let count the number of length- binary strings that avoid 000. For , every valid string ends in exactly one of the blocks: Removing the trailing block leaves an arbitrary valid prefix of length , , or , respectively. Therefore, All binary strings of lengths , , and avoid 000, so The initial polynomial is Hence,

11.5.2 A nonhomogeneous recurrence: avoiding one-zero#

Let count length- binary strings that avoid 10. In any valid string, once a 1 appears, every subsequent character must also be 1; a 0 appearing anywhere after a 1 would create a 10 transition. Every valid string therefore consists of zeroes followed by ones: for some integer . Because there are choices for , there are exactly valid strings.

We can also derive this result by setting up a recurrence based on the final character: For :

If the string ends in 1, removing that 1 leaves an arbitrary valid string of length . (Appending 1 can never create 10). This yields strings.
If the string ends in 0, it cannot contain a 1 in any earlier position, because any earlier 1 followed eventually by this final 0 would require at least one 10 transition. Thus, all preceding characters must be 0. This yields exactly string: .

Because these two cases are disjoint and cover all valid strings, we obtain with . This is a nonhomogeneous linear recurrence with constant coefficient and constant driving term .

We convert it to a generating function using Theorem 8. Multiply by and sum for : Expressing each sum in terms of : Substituting and rearranging: Dividing by : Extracting the coefficient using the negative binomial expansion from Unit 2: which matches the direct count.

11.5.3 Alphabet size and subtraction techniques#

When the alphabet contains more than two symbols, the number of choices for allowed final characters scales the recurrence coefficients.

Example 14 (Ternary strings avoiding repeated zeroes)#

Let count the number of length- strings over that avoid 00. For , . For , all three characters are valid, so .

For , classify a valid string by its final symbol:

If it ends in 1 or 2: the preceding prefix can be any valid string of length . There are choices for the final symbol, contributing strings.
If it ends in 0: the preceding symbol cannot be 0, so it must be 1 or 2. The string ends in 10 or 20. The prefix of length can be any valid string. There are choices for the block, contributing strings.

Combining the cases: With and , we compute . (Among all strings of length , only 00 is forbidden). The generating function is

The difference rule from Unit 1 is particularly effective when an allowed ending is described by subtracting an exception from all valid prefixes.

Example 15 (Ternary strings avoiding one-zero via subtraction)#

Let count length- strings over that avoid 10. For , . For , .

For , consider the final symbol:

If the final symbol is 1 or 2: appending 1 or 2 to any valid length- string can never create 10. This produces valid strings.
If the final symbol is 0: we may append 0 to any valid length- prefix except those that end in 1. How many valid length- strings end in 1? A valid string of length ending in 1 is formed uniquely by appending 1 to an arbitrary valid string of length . (Appending 1 never introduces 10). Thus, exactly of the valid prefixes end in 1. By the difference rule, the number of valid prefixes that do not end in 1 is .

Summing the allowed endings: With and : For , among the strings, only 10 is forbidden, leaving . For , among the strings, exactly contain 10 (100, 101, 102, 010, 110, 210), leaving .

The generating function has denominator and numerator Therefore, Subtraction avoids the need to divide the prefixes into separate positive cases based on their endings.

11.6 Walks with forbidden reversals: a lucky simplification#

Suppose a robot moves on the integer lattice . At each second it takes one of three steps: To prevent the robot from wasting a move, it may not reverse horizontal direction immediately: the consecutive blocks LR and RL are forbidden. Let be the number of valid step sequences of length . The empty walk gives , and the three one-step walks give .

To extend a valid walk of length , the number of choices depends on its final step:

If it ends in U, all three next steps are allowed.
If it ends in L or R, exactly two next steps are allowed.

Let be the number of valid length- walks ending in U. The remaining walks end horizontally. Counting all valid one-step extensions gives We can evaluate the exceptional count without creating a system of recurrences. Appending U to any valid walk of length produces a unique valid walk of length ending in U, and removing the final U reverses this operation. Therefore, Substitution gives the scalar recurrence

The sequence begins For , among the two-step walks, only LR and RL are forbidden, confirming .

The generating function has denominator and numerator Therefore, Here we were lucky: the walks receiving three extensions—those ending in U—are in immediate bijection with all valid walks one step shorter. For more complicated local restrictions, each ending type may have its own continuation rules, and no exceptional count collapses so neatly to an earlier total. We will need a reliable method, based on state variables and matrix recurrence relations, to model that more difficult logic.

11.7 Boundary choices: decomposing from the start versus the end#

In the examples developed so far, we decomposed objects by examining their final element—the last part of a sum, the trailing symbol of a string, or the final step of a walk. Decomposing by the first element is equally valid and can sometimes simplify the argument.

11.7.1 Initial character decomposition in pattern avoidance#

Consider again the sequence of length- binary strings that avoid 10 from Section 11.5.2. When we decomposed by the final character, strings ending in 0 required an argument showing that all previous symbols had to be 0.

Let us instead classify a valid string of length by its first character:

Case 1: The string begins with 0. Prepending 0 to any valid string of length cannot create 10, because the newly added character is 0. Therefore, any valid string of length can serve as the suffix. This yields strings.
Case 2: The string begins with 1. If the string begins with 1, it can never contain a 0 in any subsequent position, because a 0 anywhere after this leading 1 would create a 10 transition. Thus, all remaining characters must be 1. This yields exactly string: .

Because every valid string begins with either 0 or 1, the sum rule immediately reproduces Looking at the start of the string makes the uniqueness of the second case immediate.

11.7.2 A geometric model: tiling a grid with dominoes#

Decomposing from a boundary is also the fundamental tool for counting tilings of two-dimensional regions.

Example 16 (Tiling a board with dominoes)#

How many ways are there to tile a board using dominoes? Dominoes may be placed horizontally () or vertically ().

Two schematic two-row boards. In the first, one vertical domino fills the first column and leaves a two-by-(n minus 1) rectangle. In the second, two horizontal dominoes fill the first two columns and leave a two-by-(n minus 2) rectangle. — Figure 2: The top-left square is covered either by one vertical domino or by a horizontal domino that forces a second horizontal domino below it. The two cases leave smaller complete rectangles.#

Solution: Let be the number of valid tilings of a board. For , the board is empty and has tiling, so . For , the board can only be covered by a single vertical domino, so .

For , focus on the top-left square of the board (column , row ). In any valid tiling, this square must be covered by either a vertical domino or a horizontal domino:

Case 1: The top-left square is covered by a vertical domino. A vertical domino occupies both squares of column (row and row ). Removing this domino leaves an uncovered board. Conversely, placing a vertical domino in column next to any valid tiling of a board produces a valid tiling of the board. Thus, there are tilings in this case.
Case 2: The top-left square is covered by a horizontal domino. A horizontal domino occupies the top squares of columns and . Now consider the bottom square of column (row , column ). It cannot be covered by a vertical domino, because the square above it is already occupied. It cannot be left empty. Therefore, it must be covered by another horizontal domino, which occupies the bottom squares of columns and . Together, these two horizontal dominoes completely fill columns and , forming a block. Removing both horizontal dominoes leaves an uncovered board. Conversely, placing two horizontal dominoes in the first two columns next to any valid tiling of a board produces a valid tiling of the board. Thus, there are tilings in this case.

Every valid tiling covers the top-left square in exactly one of these two ways, and the two cases leave independent sub-boards. The sum rule therefore gives With and , this is again the Fibonacci recurrence: The generating function is

The domino tiling problem demonstrates that whether objects are represented as algebraic lists, character strings, or geometric tiles, the underlying combinatorial technique is identical:

Isolate an indispensable boundary element (such as the final part, first symbol, or a fixed corner square).
Classify the mutually exclusive ways to cover or choose that boundary element.
Establish bijections between each case and smaller instances of the original problem to determine the recurrence relation and initial conditions.

11.8 Two next questions#

Now that we covered the basics of recurrence relations, we still need to understand two questions.

How do we solve the recurrence?
How do we model more complex recurrence problems?

Problem 17 (A recurrence that is difficult to guess)#

Let be the number of tilings of a board by dominoes. Try to find a recurrence relation for by examining the tiles that meet the left boundary.

Three schematic three-row boards. The first has a straight cut after two completely tiled columns and leaves a smaller rectangle. The second has a horizontal domino crossing the cut in the top row, so the top square beyond the cut is occupied. The third is the reflected case with the bottom square beyond the cut occupied. — Figure 3: A cut through a tiling need not leave a smaller rectangle. A horizontal domino crossing the cut can leave the top or bottom square of the next column already occupied.#

The pictures show the obstacle. After removing tiles near the left boundary, the remaining region may be a smaller complete rectangle, but it may instead have a top or bottom boundary square already occupied by a horizontal domino. The number counts only complete rectangles, so it does not distinguish these partial boundary shapes.

Consequently, a recurrence involving only the totals is difficult to derive directly or guess reliably. A systematic solution must record which boundary squares are already occupied, assign a count to each possible boundary state, and track how those states change when a column is added. Matrix recurrence relations will organize those simultaneous transitions.

Problem 18 (Overlapping forbidden substrings)#

Let be the number of length- strings over the alphabet that avoid all three substrings Find a recurrence relation and initial conditions for .

This recurrence is difficult to guess from the totals alone. Whether a new letter is legal depends on the current suffix: for example, suffixes abc, bca, and cab forbid different next letters. These suffixes also overlap—the ending of one nearly forbidden pattern can be the beginning of another. A reliable model therefore needs states recording the longest relevant suffix of the current string, rather than only the total number of valid strings.