MGU Mathematics Series — Combinatorics
Part IV: Recurrence, Generating Functions, and Algebraic Methods
Sequences · Recurrences · Characteristic Equations · Fibonacci · Applications
Chapter 10 of 14
MGU Mathematics Series  ·  Combinatorics  ·  Library Textbook Edition

Chapter 10:
Recurrence
Relations

Recursive definitions, arithmetic and geometric sequences, first- and second-order linear recurrences, characteristic equations, the Fibonacci sequence, and applications to counting and algorithms

■ Part IV: Recurrence, Generating Functions & Algebraic Methods ■

■ 14 Sections  •  Chapter 10 of 14 ■

Follows Chapter 9: Combinatorial Identities and Proof  ·  Prepares students for Chapter 11: Generating Functions

Chapter 10 — Front Matter

Purpose and Overview

This chapter introduces recurrence relations — equations that describe how each term in a sequence depends on one or more earlier terms. Recurrences appear naturally in combinatorics whenever the solution to a counting problem of size n can be built from solutions to smaller versions of the same problem. Rather than jumping to a formula immediately, you will first learn to describe the structure of a sequence recursively, then develop methods for finding closed-form expressions from that recursive description.

This chapter is algebra-based. It uses equations, exponents, polynomials, and factoring — tools you already know from Algebra II. It does not require limits, derivatives, integrals, or convergence tests. A recurrence relation is an algebraic equation, and solving one is an algebraic process.

Opening Question

A staircase has n steps. You can climb one step at a time or two steps at a time. In how many ways can you reach the top? If the staircase has 1 step, there is exactly 1 way. If it has 2 steps, there are 2 ways. If it has 3 steps, there are 3 ways. If it has 4 steps, there are 5 ways. If it has 5 steps, there are 8 ways. You may recognize these numbers: 1, 2, 3, 5, 8, 13, 21, ... They are the Fibonacci numbers. By the end of this chapter, you will understand exactly why — and be able to write, interpret, and solve recurrences like the one that generates this sequence.

14Sections
12Objectives
15Key Terms
10+Worked Examples

Why This Chapter Matters

Many counting problems have a recursive structure. The number of subsets of a set of size n, the number of binary strings with certain properties, the number of ways to tile a rectangle, the number of paths through a grid — all of these can be described using recurrences. Algorithms in computer science are analyzed using recurrences. The Fibonacci sequence, which appears throughout combinatorics, number theory, and computer science, is defined by one. Understanding recurrences means understanding how structure repeats and builds.

Recurrence relations also prepare you for generating functions, the topic of Chapter 11. A generating function often turns a recurrence into an algebraic equation that can be solved for a closed-form formula. Chapter 10 builds the foundation for that technique.

Learning Objectives

  1. 1Explain what a recurrence relation is and how it differs from a closed-form formula.
  2. 2Write a recurrence relation from a description or counting context.
  3. 3Use initial conditions to compute the first several terms of a sequence.
  4. 4Recognize and solve arithmetic and geometric recurrences.
  5. 5Solve first-order linear recurrences using algebraic substitution or the fixed-point method.
  6. 6Identify second-order linear homogeneous recurrences and apply the characteristic equation method.
  7. 7Handle the repeated-root case in the characteristic equation method.
  8. 8Work with Fibonacci-type recurrences and interpret their combinatorial structure.
  9. 9Recognize nonhomogeneous recurrences and apply basic solution strategies.
  10. 10Apply recurrences to combinatorial counting problems.
  11. 11Identify where recurrences appear in algorithms and computer science.
  12. 12Avoid and explain common recurrence mistakes.
Chapter 10 — Contents

Sections at a Glance

Sections 10.1 – 10.6
Foundations: Sequences, Recursive Definitions, and First-Order Recurrences
What Recurrences Are · Recursive Definitions · Initial Conditions · Arithmetic · Geometric · First-Order Linear
Section 10.1

What a Recurrence Relation Is

A sequence is an ordered list of values. You have worked with sequences before: the list 1, 4, 9, 16, 25, … is the sequence of perfect squares. The list 2, 4, 8, 16, 32, … is the sequence of powers of 2. When you write a_n for the n-th term, you can describe it in two fundamentally different ways.

The first way is a closed-form formula: an explicit expression that gives a_n directly in terms of n. For example, a_n = n² gives perfect squares directly — plug in n and out comes the term.

The second way is a recurrence relation: an equation that defines a_n in terms of one or more earlier terms a_{n-1}, a_{n-2}, …. For example, the equation

a_n = a_{n-1} + 2

says that each term is 2 more than the previous term. If you know that a_1 = 3, then a_2 = 5, a_3 = 7, a_4 = 9, and so on. The recurrence generates the sequence one step at a time. A closed-form formula lets you jump directly to any term.

Neither form is universally better. Recurrences are often easier to write — because they describe how a situation grows from smaller cases — while closed-form formulas are easier to evaluate directly. Much of this chapter is about moving between the two: writing a recurrence from a problem, and then solving it to find the closed form.

Why Recurrences Appear in Combinatorics

Many counting problems have a self-similar structure: to count configurations of size n, you reduce to counting configurations of size n-1 (or n-2). The number of subsets of an n-element set, the number of arrangements with restrictions, the number of tiling patterns, and the number of paths through a grid all satisfy recurrences. In every case, the recurrence captures the structure exactly.

Section 10.2

Recursive Definitions

A recursive definition of a sequence has two parts: a recurrence relation that defines how each new term is built from earlier terms, and one or more initial conditions that give the starting values. Together, these two parts determine the sequence completely. Without initial conditions, the recurrence alone does not pin down a unique sequence.

You have seen recursive definitions before, even if not by that name. The factorial is defined recursively:

0! = 1    and    n! = n · (n−1)!   for n ≥ 1

The binomial coefficient satisfies Pascal's Identity:

C(n,k) = C(n−1, k−1) + C(n−1, k)

with base cases C(n,0) = 1 and C(n,n) = 1. Pascal's Triangle is built by applying this recurrence.

Recursive definitions are not circular. They always build larger terms from strictly smaller ones, so the process terminates at the base case. You are not defining a term using itself; you are defining it using previously defined terms.

Key Distinction

A recurrence says: "To find term n, look at earlier terms." A closed form says: "Here is an explicit formula for term n." For any given sequence, both descriptions refer to the same values — they are just different ways of presenting the same mathematical object.

Section 10.3

Initial Conditions

Initial conditions are not optional. A recurrence relation alone describes a family of sequences. The initial conditions select one specific sequence from that family.

The number of initial conditions required depends on the order of the recurrence. A first-order recurrence (involving only a_{n-1}) requires one initial condition. A second-order recurrence (involving a_{n-1} and a_{n-2}) requires two initial conditions.

RecurrenceOrderInitial Conditions NeededExample
a_n = 2a_{n-1}FirstOne (e.g., a₁)Doubling sequences
a_n = a_{n-1} + dFirstOne (e.g., a₁)Arithmetic sequences
a_n = a_{n-1} + a_{n-2}SecondTwo (e.g., a₁ and a₂)Fibonacci-type sequences
a_n = 5a_{n-1} − 6a_{n-2}SecondTwo (e.g., a₀ and a₁)Exponential combinations
Initial Conditions Have Combinatorial Meaning

In counting problems, never guess initial conditions. Compute them directly from the problem. For example, the number of ways to tile a 1×1 board is 1 (one square tile), and the number of ways to tile a 1×2 board is 2 (two squares or one domino). These are the correct base cases — and they reflect the actual structure of the problem, not an arbitrary choice.

Section 10.4

Arithmetic Recurrences

An arithmetic recurrence has the form a_n = a_{n-1} + d where d is a constant. Each term is obtained by adding the same value to the previous term. Unrolling this recurrence gives the closed-form formula for arithmetic sequences:

a_n = a_1 + (n − 1)d
Example 10.4.1
Stacking Library Fines
  • ProblemA library charges a base fee of $3 for the first day a book is overdue, and an additional $2 for each day after that. Let a_n be the total fine after n days overdue. Write a recurrence and find the closed form.
  • ThinkEach day, $2 is added to the previous total. This is an arithmetic recurrence with d = 2.
  • RepresentLet a_n = total fine after n days. Recurrence: a_n = a_{n-1} + 2 with initial condition a_1 = 3.
  • Count a_n = a_1 + (n − 1)(2) = 3 + 2(n − 1) = 2n + 1
  • Checka_1 = 2(1) + 1 = 3. a_2 = 2(2) + 1 = 5. Also a_2 = a_1 + 2 = 5. Consistent.
  • InterpretAfter n days overdue, the total fine is 2n + 1 dollars.
Answer: a_n = 2n + 1
Practice 10.4Arithmetic Recurrences
  1. Sequence: 5, 9, 13, 17, … Write the recurrence and closed form.
  2. a_n = a_{n-1} + 7, a_1 = 2. Find a₆.
  3. A tank gains 15 gallons per hour. It starts with 40 gallons. Write and solve the recurrence for the amount after n hours.
  4. Explain why a_n = a_{n-1} − 4 with a_1 = 100 is still an arithmetic recurrence.
Section 10.5

Geometric Recurrences

A geometric recurrence has the form a_n = r · a_{n-1} where r ≠ 0 is the common ratio. Unrolling gives the closed form for geometric sequences:

a_n = a_1 · r^(n−1)
Example 10.5.1
Doubling Bacteria
  • ProblemA colony of bacteria starts with 50 cells and doubles every hour. Let a_n be the number of cells after n hours.
  • RepresentRecurrence: a_n = 2 · a_{n-1} with a_0 = 50.
  • Counta_n = 50 · 2^n
  • Checka_0 = 50. a_1 = 100. Also a_1 = 2 · 50 = 100. Consistent.
  • InterpretAfter n hours, there are 50 · 2^n bacteria.
Answer: a_n = 50 · 2^n
Geometric Recurrences in Counting

Geometric recurrences arise in combinatorics whenever each new element multiplies the number of options by a fixed factor. The total number of binary strings of length n satisfies a_n = 2 · a_{n-1} because each new character is chosen independently from 2 options. The closed form is a_n = 2^n.

Section 10.6

First-Order Linear Recurrences

The general first-order linear recurrence combines both multiplication and addition:

a_n = p · a_{n-1} + q

When q = 0 this is geometric; when p = 1 this is arithmetic. The general case requires a technique to solve. Two approaches are available.

Method 1: Unrolling. Repeatedly substitute the recurrence into itself to find a pattern, then sum the resulting geometric series.

Method 2: Fixed-point method. Find the value L such that if a_{n-1} = L then a_n = L. This satisfies L = pL + q, giving L = q/(1−p) when p ≠ 1. Then b_n = a_n − L satisfies a pure geometric recurrence.

Example 10.6.1
Savings Account with Monthly Deposits
  • ProblemA savings account starts with $100. Each month, the account earns 10% interest and you deposit an additional $20. Let a_n be the balance after n months. Write and solve the recurrence.
  • RepresentEach month: multiply by 1.1, then add 20. Recurrence: a_n = 1.1 · a_{n-1} + 20 with a_0 = 100.
  • ThinkUse the fixed-point method. Find L where L = 1.1L + 20.
  • Count L = 1.1L + 20 → −0.1L = 20 → L = −200 Let b_n = a_n − (−200) = a_n + 200 b_n = 1.1 · b_{n-1}, so b_n = b_0 · (1.1)^n = 300 · (1.1)^n Therefore: a_n = 300(1.1)^n − 200
  • Checka_0 = 300(1) − 200 = 100. a_1 = 300(1.1) − 200 = 130. Direct: 1.1(100) + 20 = 130. Consistent.
  • InterpretAfter n months, the balance is 300(1.1)^n − 200 dollars.
Answer: a_n = 300(1.1)^n − 200
Practice 10.6First-Order Linear Recurrences
  1. a_n = 3a_{n-1} + 5, a_0 = 2. Find the fixed point and closed form.
  2. a_n = 2a_{n-1} + 1, a_0 = 0. Solve by unrolling.
  3. A city population grows by 5% per year and gains 1,000 new residents annually. Start: 20,000. Write and solve.
  4. Why does the fixed-point method fail when p = 1? What method would you use instead?
Sections 10.7 – 10.8
Second-Order Recurrences and Characteristic Equations
Two-Term Recurrences · Characteristic Roots · Distinct Roots · Repeated Root Case
Section 10.7

Second-Order Linear Recurrences

A second-order linear recurrence defines each term from the two preceding terms:

a_n = p · a_{n-1} + q · a_{n-2}

where p and q are constants and q ≠ 0. This is a linear homogeneous recurrence with constant coefficients. Two initial conditions are required.

Second-order recurrences arise naturally in many counting problems. The staircase problem from the opening, the tiling problem, and the Fibonacci sequence all satisfy second-order recurrences. The key idea is that the general solution is a linear combination of two simpler solutions — and finding those simpler solutions is the job of the characteristic equation.

Counting SituationRecurrenceInitial Conditions
Staircase (1 or 2 steps)s_n = s_{n-1} + s_{n-2}s₁ = 1, s₂ = 2
Tiling 1×n board (squares + dominoes)T_n = T_{n-1} + T_{n-2}T₁ = 1, T₂ = 2
Binary strings, no two consecutive 0sb_n = b_{n-1} + b_{n-2}b₁ = 2, b₂ = 3
Section 10.8

Characteristic Equations

Where the characteristic equation comes from. Consider the recurrence a_n = p · a_{n-1} + q · a_{n-2}. Suppose we guess that the solution has the form a_n = r^n for some constant r. Substituting:

r^n = p · r^(n-1) + q · r^(n-2)

Divide both sides by r^(n-2) (assuming r ≠ 0):

r² = p · r + q   →   r² − pr − q = 0

This is the characteristic equation. Its solutions are the characteristic roots.

Three Cases for the Characteristic Equation

Case 1 — Two distinct real roots r₁ ≠ r₂:

General solution:   a_n = A · r₁ⁿ + B · r₂ⁿ

Case 2 — One repeated real root r₁ = r₂ = r:

General solution:   a_n = (A + Bn) · rⁿ

Case 3 — Complex roots (preview only at this level):

Produces oscillating sequences. Explored in advanced coursework.

In Cases 1 and 2, the constants A and B are determined by the two initial conditions.

Example 10.8.1
Solving a Second-Order Recurrence — Distinct Roots
  • ProblemSolve a_n = 5a_{n-1} − 6a_{n-2} with a_0 = 1 and a_1 = 0.
  • ThinkThis is a linear homogeneous second-order recurrence. Write the characteristic equation and factor it.
  • RepresentCharacteristic equation: r² − 5r + 6 = 0.
  • Count Factor: (r − 2)(r − 3) = 0 → r₁ = 2, r₂ = 3 General solution: a_n = A · 2ⁿ + B · 3ⁿ Initial conditions: a_0 = A + B = 1 a_1 = 2A + 3B = 0 → A = 1 − B → 2(1−B) + 3B = 0 → B = −2 → A = 3 Closed form: a_n = 3 · 2ⁿ − 2 · 3ⁿ
  • Checka_0 = 3 − 2 = 1 ✓. a_1 = 6 − 6 = 0 ✓. a_2 = 5(0) − 6(1) = −6. Formula: 3(4) − 2(9) = 12 − 18 = −6 ✓.
Answer: a_n = 3 · 2ⁿ − 2 · 3ⁿ
Example 10.8.2
Solving a Second-Order Recurrence — Repeated Root
  • ProblemSolve a_n = 4a_{n-1} − 4a_{n-2} with a_0 = 1 and a_1 = 4.
  • RepresentCharacteristic equation: r² − 4r + 4 = 0 → (r−2)² = 0 → repeated root r = 2.
  • Count General solution (repeated root): a_n = (A + Bn) · 2ⁿ a_0 = (A + 0) · 1 = A = 1 → A = 1 a_1 = (1 + B) · 2 = 4 → 1 + B = 2 → B = 1 Closed form: a_n = (1 + n) · 2ⁿ
  • Checka_0 = 1 · 1 = 1 ✓. a_1 = 2 · 2 = 4 ✓. a_2 = 4(4) − 4(1) = 12. Formula: (1+2) · 4 = 12 ✓.
Answer: a_n = (1 + n) · 2ⁿ
Student Warning — The Repeated Root Case

When the characteristic equation has a repeated root r, the two linearly independent solutions are rⁿ and n · rⁿ. The general solution is (A + Bn) · rⁿ, not (A + B) · rⁿ. If you write the latter, you have only one free constant — which is not enough to satisfy two initial conditions in general.

Practice 10.8Characteristic Equations
  1. Write the characteristic equation for each recurrence and identify the roots.
    a.  a_n = 6a_{n-1} − 8a_{n-2}   b.  a_n = 4a_{n-1} − 4a_{n-2}   c.  a_n = a_{n-1} + 6a_{n-2}
  2. Solve a_n = 3a_{n-1} − 2a_{n-2}, a_0 = 1, a_1 = 2.
  3. Solve a_n = 6a_{n-1} − 9a_{n-2}, a_0 = 2, a_1 = 6. (Repeated root.)
  4. A student finds that a recurrence has characteristic roots r₁ = 4 and r₂ = 4. They write general solution a_n = A · 4ⁿ. Explain the error and correct it.
Sections 10.9 – 10.10
Fibonacci-Type Recurrences and Nonhomogeneous Recurrences
Fibonacci · Golden Ratio · Binet's Formula · Nonhomogeneous · Particular Solutions
Section 10.9

Fibonacci-Type Recurrences

The Fibonacci sequence is one of the most studied sequences in mathematics. It is defined by:

F_n = F_{n-1} + F_{n-2}   for n ≥ 3,   with F₁ = 1, F₂ = 1

The sequence begins: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Applying the characteristic equation to the Fibonacci recurrence gives:

r² − r − 1 = 0   →   r = (1 ± √5) / 2

The two roots are the golden ratio φ = (1 + √5)/2 ≈ 1.618 and its conjugate φ̂ = (1 − √5)/2 ≈ −0.618. The general solution leads to Binet's formula:

F_n = (φⁿ − φ̂ⁿ) / √5

This remarkable fact states that the n-th Fibonacci number — always a positive integer — can be computed using irrational numbers. The irrational parts cancel perfectly in every case.

Why Fibonacci Appears in Counting

Any counting problem with the following structure produces a Fibonacci-type sequence: at each step, you can make either a "size-1 move" (going from n-1) or a "size-2 move" (going from n-2), and these cases are disjoint and exhaustive. Staircase climbing, tiling with squares and dominoes, and binary strings with no two consecutive 0s all have this structure — hence all satisfy the same recurrence.

Example 10.9.1
Staircase Counting — Using the Fibonacci Recurrence
  • ProblemLet s_n denote the number of ways to climb a staircase of n steps, taking 1 or 2 steps at a time. Write the recurrence and find s_6.
  • ThinkTo reach step n, the climber came from step n-1 (one step back) or step n-2 (two steps back). So the number of ways to reach step n is the sum of the ways to reach each of those two prior steps.
  • RepresentRecurrence: s_n = s_{n-1} + s_{n-2}. Initial conditions: s_1 = 1 (one way: take 1 step), s_2 = 2 (two ways: 1+1 or 2).
  • Count s_3 = 2 + 1 = 3 s_4 = 3 + 2 = 5 s_5 = 5 + 3 = 8 s_6 = 8 + 5 = 13
  • CheckList arrangements for n = 3: (1,1,1), (1,2), (2,1). Three ways. Consistent with s_3 = 3.
  • InterpretThere are 13 ways to climb a 6-step staircase taking 1 or 2 steps at a time.
Answer: s_6 = 13
Section 10.10

Nonhomogeneous Recurrences

A nonhomogeneous linear recurrence includes an additional term that is a function of n alone:

a_n = p · a_{n-1} + q · a_{n-2} + f(n)

The general solution is the sum of two parts: the general solution to the associated homogeneous recurrence (setting f(n) = 0), and any particular solution to the full nonhomogeneous recurrence.

a_n = a_n^(h) + a_n^(p)

Finding the particular solution involves guessing a form based on f(n), then substituting to determine the coefficients.

Form of f(n)Guess for particular solution
Constant cConstant C
Linear bn + cLinear Bn + C
c · rⁿ where r is not a characteristic rootC · rⁿ
c · rⁿ where r is a characteristic rootC · n · rⁿ
Example 10.10.1
A Recurrence with a Constant Nonhomogeneous Term
  • ProblemSolve a_n = 3a_{n-1} + 4 with a_0 = 1.
  • ThinkFirst-order and nonhomogeneous. Find the homogeneous solution, then a particular solution by guessing a constant.
  • Count Homogeneous solution: a_n^(h) = A · 3ⁿ Particular solution: guess a_n^(p) = C Substitute: C = 3C + 4 → −2C = 4 → C = −2 General solution: a_n = A · 3ⁿ − 2 Initial condition: a_0 = A − 2 = 1 → A = 3 Closed form: a_n = 3 · 3ⁿ − 2 = 3^(n+1) − 2
  • Checka_0 = 3 − 2 = 1 ✓. a_1 = 9 − 2 = 7. Direct: 3(1) + 4 = 7 ✓.
Answer: a_n = 3^(n+1) − 2
Do Not Apply the Characteristic Equation to the Nonhomogeneous Part

The characteristic equation applies only to the homogeneous recurrence. For nonhomogeneous recurrences, you must find a particular solution separately and add it to the homogeneous general solution. Skipping the particular solution gives an incomplete answer that cannot satisfy the initial conditions in general.

Practice 10.9–10.10Fibonacci and Nonhomogeneous
  1. Write the first 10 terms of the Fibonacci sequence using F₁ = 1, F₂ = 1.
  2. Write the first 10 terms of the Lucas sequence: L₁ = 1, L₂ = 3, L_n = L_{n-1} + L_{n-2}. How do they relate to Fibonacci terms?
  3. How many ways are there to climb a staircase of 10 steps taking 1 or 2 steps at a time?
  4. Verify that F_n² − F_{n-1} · F_{n+1} = (−1)^(n-1) for n = 2, 3, 4 (Cassini's identity).
  5. Solve a_n = 2a_{n-1} + 3, a_0 = 1. Guess a constant particular solution.
  6. Solve a_n = 3a_{n-1} + 2^n, a_0 = 1. (r = 2 is not the characteristic root.)
Sections 10.11 – 10.12
Recurrences in Counting Problems and Computer Science
Tiling · Binary Strings · Subsets · Tower of Hanoi · Algorithm Analysis
Section 10.11

Recurrences in Counting Problems

Framework for Recursive Counting

When a counting problem has a recursive structure, use this approach:

1. Define a_n clearly — what exactly is being counted for a given n.

2. Identify how a configuration of size n can be built from configurations of smaller size.

3. Write the recurrence relating a_n to earlier terms.

4. Determine initial conditions from the base cases by direct count.

5. Compute terms using the recurrence, or solve for a closed form.

Example 10.11.1
Tiling a Board with Squares and Dominoes
  • ProblemA 1×n board is tiled using 1×1 squares and 1×2 dominoes. Let T_n be the number of ways. Find a recurrence and compute T_5.
  • ThinkConsider the leftmost cell. Either it is covered by a 1×1 square (leaving a 1×(n−1) board) or it starts a 1×2 domino covering the first two cells (leaving a 1×(n−2) board). These cases are disjoint and exhaustive.
  • RepresentRecurrence: T_n = T_{n-1} + T_{n-2}. Initial conditions: T_1 = 1 (one square tile), T_2 = 2 (two squares or one domino).
  • Count T_3 = 2 + 1 = 3 T_4 = 3 + 2 = 5 T_5 = 5 + 3 = 8
  • CheckList tilings for n = 3 (S = square, D = domino): (S,S,S), (S,D), (D,S). Three tilings. Consistent.
  • InterpretThere are 8 ways to tile a 1×5 board using squares and dominoes. The sequence is Fibonacci-type.
Answer: T_5 = 8
Example 10.11.2
Binary Strings with No Two Consecutive Zeros
  • ProblemLet b_n be the number of binary strings of length n with no two consecutive 0s. Find a recurrence and compute b_5.
  • ThinkConsider the last character. If the string ends in 1, the first n-1 digits can be any valid string: b_{n-1} options. If it ends in 0, the second-to-last digit must be 1 (to avoid two consecutive 0s), and the first n-2 digits can be any valid string: b_{n-2} options.
  • RepresentRecurrence: b_n = b_{n-1} + b_{n-2}. Initial conditions: b_1 = 2 (strings: 0 and 1), b_2 = 3 (strings: 01, 10, 11 — not 00).
  • Count b_3 = 3 + 2 = 5 b_4 = 5 + 3 = 8 b_5 = 8 + 5 = 13
  • CheckFor n = 3: list 010, 011, 101, 110, 111. Five valid strings. Consistent with b_3 = 5.
  • InterpretThere are 13 valid binary strings of length 5. The same Fibonacci recurrence applies, but with different initial conditions — so this is a Fibonacci-type sequence.
Answer: b_5 = 13
Example 10.11.3
Counting Subsets Recursively
  • ProblemLet S_n be the number of subsets of an n-element set. Write and solve a recurrence.
  • ThinkSingle out one element e from the set. Every subset either contains e or does not. Subsets containing e correspond to subsets of the remaining n-1 elements with e added. Subsets not containing e are exactly the subsets of the remaining n-1 elements.
  • RepresentRecurrence: S_n = 2 · S_{n-1} with S_0 = 1 (the empty set has one subset: itself).
  • CountS_n = 2^n
  • CheckFor n = 2: subsets of {a, b} are ∅, {a}, {b}, {a,b}. Four subsets = 2² = 4. Consistent.
  • InterpretAn n-element set has 2ⁿ subsets — a familiar result now derived from a recurrence.
Answer: S_n = 2^n
Section 10.12

Recurrences in Algorithms and Computer Science

Recurrence relations are fundamental to the analysis of algorithms. When an algorithm breaks a problem of size n into smaller subproblems, the time required satisfies a recurrence. Understanding recurrences is not only a combinatorial skill — it is central to computer science.

Algorithm / ProblemRecurrenceClosed Form
Binary SearchT(n) = T(n/2) + 1T(n) = log₂ n + 1
Merge Sort (time)T(n) = 2T(n/2) + cnT(n) = O(n log n)
Tower of HanoiH_n = 2H_{n-1} + 1, H₁ = 1H_n = 2ⁿ − 1
List all subsetsC_n = 2C_{n-1}C_n = 2ⁿ
Example 10.12.1
Tower of Hanoi
  • ProblemThe Tower of Hanoi puzzle with n disks: move n-1 disks to an intermediate peg, move the largest disk, then move n-1 disks from the intermediate peg to the destination. Find a closed form for the minimum number of moves H_n.
  • RepresentRecurrence: H_n = 2H_{n-1} + 1 with H_1 = 1.
  • CountFixed point: L = 2L + 1 → L = −1. Let b_n = H_n + 1. Then b_n = 2b_{n-1}, so b_n = b_1 · 2^(n-1) = 2 · 2^(n-1) = 2^n. Therefore: H_n = 2^n − 1
  • CheckH_1 = 2 − 1 = 1 ✓. H_2 = 4 − 1 = 3. Direct: 2(1) + 1 = 3 ✓.
  • InterpretWith 64 disks, the minimum number of moves is 2⁶⁴ − 1 ≈ 1.8 × 10¹⁹. At one move per second, this would take more than 580 billion years.
Answer: H_n = 2^n − 1
Practice 10.11–10.12Counting and Algorithm Applications
  1. Three-step staircase: you can take 1, 2, or 3 steps at a time. Let s_n be the number of ways to reach step n. Write the recurrence and initial conditions, then compute s_1 through s_8.
  2. A 1×n board is tiled with red, blue, or green 1×1 tiles and colorless 1×2 dominoes. Write the recurrence for T_n. (Hint: what goes in the first position?) Compute T_1 through T_5.
  3. Let b_n be the number of subsets of {1, 2, …, n} that contain no two consecutive integers. Show that b_n = b_{n-1} + b_{n-2} and determine initial conditions.
  4. Solve the Tower of Hanoi recurrence directly by unrolling instead of the fixed-point method. Show all steps.
  5. Binary search on a list of 1024 elements. Write the recurrence T(n) = T(n/2) + 1 and unroll it to find how many steps are needed. Why is binary search fast?
  6. A rope can be cut at any of n−1 positions. Let c_n be the maximum number of pieces. Write a recurrence and find the closed form.
Sections 10.13 – 10.14
Common Mistakes and Preparing for Generating Functions
Ten Recurring Errors · Prevention Strategies · Chapter 11 Preview · Readiness Checklist
Section 10.13

Common Recurrence Mistakes

Mistake 1 — Forgetting initial conditions
a_n = 2a_{n-1} + 1   (no initial condition stated)

A recurrence alone describes a family of sequences. Always state initial conditions explicitly, and always verify they match the combinatorial meaning of the base cases.

Mistake 2 — Using wrong base cases
For the staircase problem: s₁ = 1, s₂ = 1 (wrong)

For a 2-step staircase, there are 2 ways: (1,1) and (2). So s₂ = 2, not 1. Always count the base cases directly — never guess.

Mistake 3 — Confusing a recurrence with a closed form
"The closed form is a_n = a_{n-1} + a_{n-2}."

A recurrence defines a sequence implicitly. A closed form gives a_n explicitly as a function of n, with no reference to earlier terms. These are different descriptions. Solving the recurrence produces the closed form.

Mistake 4 — Off-by-one index errors
Applying a_n = 2a_{n-1} + 1 at n = 0 when a₀ is the initial condition

Be precise about which values of n the recurrence applies to. If a₀ is an initial condition, the recurrence applies for n ≥ 1. Applying it at n = 0 gives a circular definition.

Mistake 5 — Incorrect characteristic equation
For a_n = pa_{n-1} + qa_{n-2}, writing: r = pr + q (wrong)

Substitute a_n = rⁿ and divide by r^(n-2), not r^(n-1). The correct characteristic equation is r² − pr − q = 0. Always derive it from the substitution.

Mistake 6 — Forgetting the repeated root case
When r₁ = r₂ = r: writing a_n = (A + B) · rⁿ instead of (A + Bn) · rⁿ

With a repeated root, you need two free constants to satisfy two initial conditions. The correct form is (A + Bn) · rⁿ, where A and B are determined separately.

Mistake 7 — Confusing the order of a recurrence
Treating a_n = a_{n-1} + a_{n-2} as first-order and giving only one initial condition

This recurrence involves two previous terms — it is second-order and requires two initial conditions. Always identify the order before choosing a method.

Mistake 8 — Setting up the recurrence incorrectly
Failing to check that all cases of size n are disjoint and exhaustive

Before solving, verify the recurrence is correct. Double-check that you have identified all cases, that they do not overlap, and that every configuration of size n is produced exactly once from smaller configurations.

Mistake 9 — Applying the characteristic equation to a nonhomogeneous recurrence
For a_n = 3a_{n-1} + n: writing general solution as A · 3ⁿ only

The characteristic equation gives only the homogeneous solution. For nonhomogeneous recurrences, you must find a particular solution separately and add it to get the full general solution.

Mistake 10 — Importing calculus into an algebraic setting
Asking about convergence or limits when solving a_n = 2a_{n-1} + 1

At this level, recurrences are purely algebraic. You do not need limits, convergence tests, or differential equations. Avoid importing analytic ideas into problems that are entirely algebraic in nature.

Section 10.14

Preparing for Generating Functions

Chapter 11 introduces generating functions, a powerful algebraic technique for working with sequences and recurrences. A generating function encodes the entire sequence a_0, a_1, a_2, … as the coefficients of a formal polynomial expression:

G(x) = a_0 + a_1·x + a_2·x² + a_3·x³ + ···

Recurrences become algebraic equations in G(x), which can then be solved using polynomial algebra. The coefficients of the solution give the closed-form sequence. For example, the Fibonacci recurrence becomes an equation in G(x) whose solution produces Binet's formula.

Generating functions work because a recurrence imposes a relationship between consecutive coefficients, and that relationship can be expressed algebraically. The technique is purely formal — you are not doing calculus or worrying about convergence. You are treating the sequence as an algebraic object and manipulating it symbolically.

Readiness Checklist for Chapter 11

Before moving to generating functions, you should be comfortable with: writing recurrences in standard form with initial conditions · recognizing the order of a recurrence · solving first-order arithmetic and geometric recurrences · applying the characteristic equation for second-order linear homogeneous recurrences · distinguishing homogeneous from nonhomogeneous recurrences · working with polynomial expressions and algebraic manipulation.

Chapter 10 — Back Matter

Chapter Summary

Key Terms Review

sequence
An ordered list of values indexed by non-negative or positive integers. Written as a₀, a₁, a₂, … or a₁, a₂, a₃, …
recurrence relation
An equation defining each term of a sequence in terms of one or more earlier terms. Requires initial conditions to determine the sequence uniquely.
closed-form formula
An explicit expression for the n-th term that does not reference earlier terms. Allows direct computation of any term.
initial condition
A specified value for one or more early terms needed to determine the sequence uniquely. A first-order recurrence needs one; a second-order needs two.
first-order recurrence
A recurrence where each term depends only on the immediately preceding term. Example: a_n = 2a_{n-1} + 3.
second-order recurrence
A recurrence where each term depends on the two immediately preceding terms. Example: a_n = a_{n-1} + a_{n-2}.
linear recurrence
A recurrence where earlier terms appear only to the first power and are not multiplied together. All recurrences in this chapter are linear.
homogeneous recurrence
A linear recurrence with no additional function of n added. Every term involves only a_n or an earlier a_k.
nonhomogeneous recurrence
A linear recurrence that includes an additional term f(n) that depends on n alone, not on any a_k.
characteristic equation
A polynomial equation derived from a linear homogeneous recurrence by substituting a_n = rⁿ. Its roots determine the closed-form solution.
characteristic roots
The solutions to the characteristic equation. Distinct roots give one form of general solution; a repeated root gives another.
Fibonacci sequence
The sequence defined by F_n = F_{n-1} + F_{n-2} with F₁ = 1, F₂ = 1. Begins 1, 1, 2, 3, 5, 8, 13, 21, …
golden ratio
The value φ = (1 + √5)/2 ≈ 1.618, one of the two characteristic roots of the Fibonacci recurrence. The ratio of consecutive Fibonacci numbers approaches φ.
Binet's formula
The closed-form expression F_n = (φⁿ − φ̂ⁿ)/√5 for the Fibonacci sequence, derived from the characteristic roots of its recurrence.
particular solution
Any specific solution to a nonhomogeneous recurrence. Added to the homogeneous general solution to produce the full general solution.
arithmetic recurrence
A recurrence a_n = a_{n-1} + d where d is a constant. Produces arithmetic sequences; closed form is a_n = a₁ + (n−1)d.
geometric recurrence
A recurrence a_n = r · a_{n-1} where r is a nonzero constant (the common ratio). Produces geometric sequences; closed form is a_n = a₁ · r^(n-1).

Concept Review Questions

Answer each question in complete sentences. These check your understanding of ideas, not just procedures.

  1. What is the difference between a recurrence relation and a closed-form formula? Give an example of each for the same sequence.
  2. Why are initial conditions necessary? Could the same recurrence describe two different sequences? Explain with an example.
  3. How many initial conditions does a first-order recurrence require? A second-order recurrence? Explain why.
  4. What is the characteristic equation of a second-order linear homogeneous recurrence, and where does it come from?
  5. What changes in the general solution formula when the characteristic equation has a repeated root? Why can't you just use two copies of the same root?
  6. Why does the Fibonacci recurrence appear in seemingly unrelated problems such as tiling, staircase counting, and binary strings?
  7. What is the difference between a homogeneous and a nonhomogeneous recurrence? Give an example of each.
  8. Explain in your own words why the number of subsets of an n-element set satisfies the recurrence S_n = 2S_{n-1}.
  9. How does a recurrence arise in the analysis of a recursive algorithm? Give one example.
  10. What does it mean to "solve" a recurrence relation? What form does the answer take?

Recursive Definition Practice

For each sequence, write the recursive definition (recurrence + initial conditions), then compute the first six terms.

  1. Positive multiples of 7: 7, 14, 21, …
  2. Powers of 2: 1, 2, 4, 8, 16, …
  3. Each term is 5 less than previous; start at 100.
  4. Each term is −1 times the previous; start at 3.
  5. a_n = a_{n-1} + a_{n-2}, a₁ = 2, a₂ = 5
  6. a_n = 2a_{n-1} − a_{n-2}, a₁ = 1, a₂ = 4

Recurrence Solving Practice

Solve each recurrence. Find the closed-form formula and verify using the initial conditions.

  1. a_n = a_{n-1} + 6, a₁ = 2
  2. a_n = 4a_{n-1}, a₁ = 3
  3. a_n = 2a_{n-1} + 1, a₀ = 0
  4. a_n = 3a_{n-1} − 2a_{n-2}, a₀ = 1, a₁ = 2
  5. a_n = 4a_{n-1} − 4a_{n-2}, a₀ = 1, a₁ = 4 (repeated root)
  6. a_n = 5a_{n-1} − 6a_{n-2}, a₀ = 2, a₁ = 5
  7. a_n = a_{n-1} + 2n, a₀ = 0 (guess a_n^(p) = An + B)
  8. a_n = 2a_{n-1} + 3ⁿ, a₀ = 1 (exponential nonhomogeneous)

Fibonacci-Type Practice

  1. Write the first 12 terms of the Fibonacci sequence using F₁ = 1, F₂ = 1.
  2. Write the first 10 terms of the Lucas sequence: L₁ = 1, L₂ = 3, L_n = L_{n-1} + L_{n-2}. Compare to Fibonacci.
  3. Compute F₁₀ using the recurrence.
  4. Verify Cassini's identity: F_n² − F_{n-1}·F_{n+1} = (−1)^(n-1) for n = 2, 3, 4, 5.
  5. Compute F_{n+1}/F_n for n = 1 through 10. What value is the ratio approaching?
  6. How many ways are there to climb a staircase of 10 steps taking 1 or 2 steps at a time?
  7. A 1×8 board is tiled with 1×1 squares and 1×2 dominoes. Use the tiling recurrence to find the number of tilings.
  8. The sequence a_n = a_{n-1} + a_{n-2} with a₁ = 3, a₂ = 3. Write its first 8 terms. How does it compare to the Fibonacci sequence?

Counting Applications

For each problem: define the sequence, write the recurrence and initial conditions, compute first several terms, and interpret the answer.

  1. Three-step staircase. You can take 1, 2, or 3 steps at a time. Let s_n be the number of ways to reach step n. Write the recurrence and compute s₁ through s₈.
  2. Ternary strings. Let t_n be the number of strings of length n using digits 0, 1, 2 with no two consecutive 0s. Write the recurrence, identify initial conditions, and compute t₁ through t₆.
  3. Regions of a line. A line is divided into regions by placing points on it. With 0 points, there is 1 region. Each new point adds 1 region. Write the recurrence and find the closed form.
  4. Subsets without consecutive integers. Let b_n be the number of subsets of {1, 2, …, n} containing no two consecutive integers. Show that b_n = b_{n-1} + b_{n-2} and determine initial conditions.
  5. Tower of Hanoi. H_n = 2H_{n-1} + 1, H₁ = 1. Solve and find the number of moves for n = 10.
  6. Cutting a rope. A rope can be cut at any of n−1 positions. Let c_n be the maximum number of pieces. Write a recurrence and find the closed form.
  7. Coloring a path. A path of n steps must be colored red or blue, with no two consecutive blue steps. Let p_n be the number of valid colorings. Write the recurrence and compute p₁ through p₇.

Error Analysis

Each problem contains a mistake. Identify it and write the correct solution.

Problem A
Binary strings with no two consecutive 1s: "a₁ = 1, a₂ = 1 since there's only one valid string of length 1."

Identify the error. What is the correct value of a₁ for strings using digits 0 and 1?

Problem B
For a_n = 5a_{n-1} − 4a_{n-2}: characteristic equation written as r − 5 + 4 = 0, giving r = 1.

Identify both errors. Write the correct characteristic equation and solve it.

Problem C
For a_n = 4a_{n-1} − 4a_{n-2} with repeated root r = 2: general solution written as A · 2ⁿ + B · 2ⁿ = (A+B) · 2ⁿ.

What is wrong? Write the correct general solution and explain why it has the form it does.

Problem D
"The recurrence a_n = a_{n-1} + a_{n-2} is already the closed form, so no further work is needed."

Explain why this reasoning is incorrect. What would a true closed form look like?

Problem E
For a_n = 3a_{n-1} + n: characteristic root r = 3, so general solution is A · 3ⁿ.

What step did the student skip? Complete the solution correctly.

Chapter 10 Checkpoint

Chapter 10 Checkpoint
Complete without assistance — assesses all key skills and concepts from Chapter 10
Part 1 — Recurrence Writing
  1. A sequence begins 7, 11, 15, 19, 23, … Write a recursive definition (recurrence + initial condition).
  2. A sequence begins 5, 15, 45, 135, … Write a recursive definition.
  3. A staircase problem where you can take 1, 2, or 3 steps at a time. Define the sequence being counted and write the recurrence with initial conditions.
Part 2 — Computing Terms
  1. Compute the first 8 terms of the sequence: a_n = a_{n-1} + a_{n-2} + a_{n-3}, a₁ = 1, a₂ = 1, a₃ = 2. (Tribonacci sequence.)
  2. Compute the first 6 terms of a_n = 3a_{n-1} − 2, a₁ = 5.
Part 3 — Solving Recurrences
  1. Solve a_n = 6a_{n-1} − 9a_{n-2}, a₀ = 2, a₁ = 6. (Hint: check for repeated root.)
  2. Solve a_n = a_{n-1} + 5, a₀ = 3.
  3. Solve a_n = 2a_{n-1} + 2, a₀ = 0.
Part 4 — Counting Application
  1. A 1×n board is tiled with red, blue, or green 1×1 tiles and colorless 1×2 dominoes. Let T_n be the number of tilings. Write the recurrence. (What goes in the first position?) Compute T₁ through T₅.
  2. The number of subsets of {1, 2, …, n} satisfies S_n = 2S_{n-1} with S₀ = 1. Solve for S_n and verify for n = 1, 2, 3.
Part 5 — Reflection
  1. Describe a counting problem from everyday life (not from this chapter) that naturally has a recursive structure. Define the sequence, write a plausible recurrence, and state the initial conditions. You do not need to solve it.
  2. A classmate says: "If I know the recurrence, I know the sequence." Is this statement accurate? Explain.

Answers may be placed in the answer key.

Looking Ahead
Chapter 11: Generating Functions

Chapter 10 gave you the language and methods for describing sequences recursively and solving recurrences algebraically. Chapter 11 will introduce generating functions — a systematic algebraic technique for encoding sequences as coefficients of formal expressions. Recurrences become algebraic equations in the generating function, which can be solved using polynomial methods and partial fractions. The coefficients of the solution give the closed-form sequence. Chapter 11 will also show how generating functions count selections with restrictions, distribution problems, and partition problems — extending the tools of Chapters 4 and 6 into a powerful unified framework.

MGU Library Connection
  • Recurrence Relations and Algorithm Analysis — MGU Algorithms Chapter
  • Divide-and-Conquer Recurrences and the Master Theorem — MGU Computer Science Foundations
  • Markov Chains and Random Walks — MGU Probability and Statistics textbook
  • Fibonacci Numbers in Number Theory — MGU Discrete Mathematics textbook
  • Generating Functions (systematic recurrence solution) — Chapter 11 of this textbook
  • Recurrence Reference — Appendix M of this textbook