# Recurrence Relations

Computer Science I · Discrete Mathematics · https://tryals.app/learn/computer-science-i/recurrence-relations

## Defining Recurrence Relations

A **recurrence relation** defines each term of a sequence using earlier terms, paired with **initial conditions** to start. Without initial conditions, the sequence is undetermined, just like a recursive function without a base case.

| Component | Description | Example |
| --- | --- | --- |
| **Recursive Rule** | How a term depends on earlier ones | $F(n) = F(n-1) + F(n-2)$ |
| **Initial Conditions** | The starting values needed to begin | $F(0) = 0, F(1) = 1$ |

To **unfold** a recurrence, you compute it forward from the initial conditions. A **closed form** is a direct formula for $F(n)$ avoiding earlier terms, such as $a(n) = 2^n$ for $a(n) = 2\,a(n-1)$ with $a(0) = 1$.

## Why Recurrences Matter

Recurrences model processes building on previous states, mirroring **recursion** in programming. They are central to **algorithm analysis**, describing running times like $T(n) = 2\,T(n/2) + n$.

| Task | Method | Outcome |
| --- | --- | --- |
| **Evaluation** | Unfolding forward | Exact sequence values |
| **Solving** | Characteristic equation or **Master Theorem** | Closed-form complexity ($n \log n$) |

**Common Pitfall:** Supplying too few initial conditions. A recurrence reaching back $k$ steps needs $k$ starting values. $F(n) = F(n-1) + F(n-2)$ requires two starting values, or the sequence remains undefined.

## Practice questions

3 of this lesson's 9 practice questions, with answers. The full set is in the app.

### 1. A recurrence like a(n) = 3a(n−1) − 2 with a(0) = 3 defines the sequence completely, yet a closed form is usually preferred. Why bother deriving one?

A. Because a recurrence needs all preceding terms; a closed form does not.
B. Because closed forms are exact while recurrences are approximations.
C. Because a recurrence cannot be used for values of n beyond a few hundred.
D. Because a recurrence can give the wrong value if the initial condition is imprecise.

**Answer:** A. Because a recurrence needs all preceding terms; a closed form does not.

**Why:** Both describe the same sequence; the difference is cost and visibility. A recurrence is a procedure, so a(1000) requires every preceding term. The second advantage matters more in algorithm analysis: the recurrence does not display its growth, and unfolding it makes the 3ⁿ visible, which is exactly what the Master Theorem provides without solving in full.

Page: https://tryals.app/practice/computer-science-i/recurrence-relations/a-recurrence-like-a-n-3a-n-1-2-with-a-0-3-defines-the

### 2. Order the steps of evaluating a recurrence by unfolding it.

**Answer:**

1. Read off the initial conditions, which give the earliest terms outright
2. Apply the recursive rule to the known terms to obtain the next term
3. Add that new term to the list of known terms
4. Repeat the rule, each time using the terms just computed
5. Stop once the term you were asked for has been reached

**Why:** Unfolding runs forward from the initial conditions, each new term built from ones already known. Without the initial conditions there is nothing to start from and the recurrence defines no particular sequence at all, exactly like a recursive function with no base case.

Page: https://tryals.app/practice/computer-science-i/recurrence-relations/order-the-steps-of-evaluating-a-recurrence-by-unfolding-it

### 3. Merge sort's cost recurrence is T(n) = 2T(n/2) + O(n). Which part of that expression produces the log n factor, and which produces the n?

A. Neither, the n log n comes from the number of comparisons, not the recurrence
B. The halving gives log n levels, the merge gives the n
C. The O(n) term produces both, since merging dominates
D. The 2 produces the n, and the division produces the log n

**Answer:** B. The halving gives log n levels, the merge gives the n

**Why:** Halving gives log n levels; merging touches every element once per level, giving O(n) each. Their product is the answer, and reading a recurrence this way, depth times work per level, is what the Master Theorem formalises and what lets you predict a design change before implementing it.

Page: https://tryals.app/practice/computer-science-i/recurrence-relations/merge-sorts-cost-recurrence-is-t-n-2t-n-2-o-n-which-part-of