A counting argument that builds today's answer out of yesterday's is a recurrence, and this course is about to lean on that idea constantly — divide-and-conquer costs, generating-function coefficients, and the Catalan numbers later this chapter all start life as a recurrence before anything gets a closed form.
Unfolding a recurrence is like tracing a chain of IOUs. a_n owes its value to a_{n-1}. That term owes it to a_{n-2}, and so on. The chain ends wherever a_0 or a_1 anchors it. Write out the first few terms by hand first. The pattern usually shows up in the numbers before it shows up in the algebra. This trick only works when the pattern is simple enough to notice by eye after a few unfoldings. Nothing guarantees the pattern will show up quickly, or at all. That's why a more reliable method is worth having in reserve.
A recurrence relation is a rule that defines a sequence by expressing a_n in terms of earlier terms, together with enough initial conditions to anchor it. Solving by iteration means unfolding that definition repeatedly — substituting the recurrence into itself — until a pattern in terms of n alone becomes visible, then confirming that pattern by induction rather than trusting the pattern on sight. It's a guess-and-verify method, not a guaranteed algorithm: it works whenever a closed form is simple enough to spot after a few unfoldings, and it says nothing about how long that might take for a messier recurrence. Chapter 7 replaces it with the characteristic-equation method for the cases where a closed form must be found reliably, not just spotted by eye.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
How many initial conditions does the order-1 recurrence a_n=a_(n-1)+7 need?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
An order-1 recurrence needs exactly one initial condition, such as a_1.
Correct answer
Also accepted:
Why
From Discrete Mathematics I — Logic, Proof, and Structure
What is the order of a_n = 2*a_(n-1) - a_(n-3)?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The relation reaches back to a_(n-3), three positions before a_n, so its order is 3.
Correct answer
Also accepted:
Why
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
What does solving a recurrence by iteration involve?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Iteration is a systematic unfolding process, not an unjustified guess.
Iteration keeps unfolding well past the first two terms, until the general pattern is visible.
Iteration finds a formula so that no term ever needs computing directly, let alone infinitely many.
Why
Iteration substitutes the recurrence into itself repeatedly, revealing the general pattern in terms of n.
From Discrete Mathematics I — Logic, Proof, and Structure
Solve a_n=a_(n-1)+3 with a_1=2 by iteration. Give a_n as an expression in n.
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Any equivalent form counts — 2x+3, 3 + 2·x, … Use the keypad below the field for fractions, roots, and other symbols.
Why
Iterating gives a_n=a_1+3(n-1)=2+3(n-1)=3n-1.
Correct answer
Also accepted:
Why
Watch the running total an unfolding produces
Slide n up and watch how the bar heights track the sum an iterated recurrence unfolds into.
Loading interactive…
Fill in the next unfolding layer
For a_n = a_(n-1) + 3n with a_1 = 1, fill in the next substitution layer.
Loading interactive…
Worked example
Unfolding a recurrence to a closed form
-
1
Solve a_n = a_{n-1} + 2 with a_1 = 1 by iteration.
-
2
Unfold twice: a_n = a_{n-1}+2 = (a_{n-2}+2)+2 = a_{n-2}+2\cdot 2. Continuing the pattern, k unfoldings give a_{n-k} + 2k.
-
3
The chain bottoms out at a_1=1 when n-k=1, i.e. k=n-1: a_n = a_1 + 2(n-1) = 1 + 2(n-1).
-
4\boxed{a_n = 2n-1}
Checking against a_1=1, a_2=3, a_3=5 confirms the pattern before trusting it for every n.
Loading interactive…
Where this goes next
Recursive algorithms
A recursive function's running time is almost always stated as a recurrence before it's ever a formula — T(n) = T(n-1) + c for a function that peels off one element per call, or T(n) = 2T(n/2) + n for one that splits its input in half. Chapter 8 solves recurrences of exactly that second shape with the master theorem; the plain iteration method here already handles the first, simpler kind completely.
Check your understanding (counts toward your progress)
What does a recurrence relation need, beyond the rule relating a_n to earlier terms, to fully define a sequence?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Without an anchor (a_1, a_0, or similar), the same recurrence rule describes infinitely many different sequences.
An unfolded pattern suggests a_n = 3n - 1. What must happen before trusting this closed form for every n?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A pattern spotted from a few terms is a conjecture, not a proof -- induction confirms it holds for every n.
A pattern noticed from the first few unfolded terms is only a guess about every n -- think about what's still missing before it counts as established.
Recall the standard technique for confirming a conjectured closed form actually holds for every n, not just the terms already checked.
Solve a_n = a_(n-1) + 5 with a_1 = 2 by iteration. What is a_10?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Unfolding gives a_n = a_1 + 5(n-1) = 2 + 5(9) = 47.
Correct answer
Also accepted:
Why
Solving by iteration is best described as:
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Iteration is guess-and-verify, not guaranteed -- Chapter 7's characteristic-equation method is the reliable alternative.
A spotted pattern still needs to be confirmed, typically by induction, before it's trusted.
Why
Iteration unfolds the definition repeatedly to spot a pattern, which then needs independent verification.
Think about whether unfolding a recurrence a few times, by itself, counts as a finished proof or just a way to notice a pattern.
Practice: Unfolding a recurrence to find (and verify) a pattern (5 problems · doesn’t affect your progress)
A sequence is defined by a_n = 2a_(n-1) - 3 with a_1 = 4. What do you need to find a_5 -- besides the recurrence rule itself?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
The rule alone describes infinitely many different sequences -- without an anchor term, a_5 isn't pinned down.
A closed form is often the GOAL of solving a recurrence, not a prerequisite for simply computing one term by unfolding.
Induction verifies a conjectured pattern; it isn't needed just to compute one specific term by direct unfolding.
Why
a_1 = 4 is already given here -- that's exactly the initial condition the recurrence needs as its anchor before unfolding can produce a_5.
The value(s) of one or more initial terms, to anchor the unfolding
Solve a_n = a_(n-1) + 5 with a_1 = 2 by iteration. What is a_10?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Unfolding gives a_n = a_1 + 5(n-1) = 2 + 5(9) = 47.
Correct answer
Also accepted:
Why
What does a recurrence relation need, beyond the rule relating a_n to earlier terms, to fully define a sequence?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Without an anchor (a_1, a_0, or similar), the same recurrence rule describes infinitely many different sequences.
One or more initial conditions
A sequence is defined by b_n = 2*b_(n-1) with b_1 = 3. Unfold the recurrence to find b_5.
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Each step doubles the previous term: b_1=3, b_2=6, b_3=12, b_4=24, b_5=48 -- equivalently b_n = 3*2^(n-1).
Correct answer
Also accepted:
Why
Unfold a few terms to see the constant multiplier applied at each step, then apply that pattern directly at n=5.
Unfolding a_n = a_(n-1) + a_(n-2) a few terms suggests the sequence is arithmetic (a constant difference between consecutive terms). Should this be trusted?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A pattern glimpsed from a few unfolded terms is only a conjecture -- interactions between two prior terms can easily break an apparent pattern later. It needs verification (typically induction), not just a hopeful glance.
Recall the general rule about trusting an unfolded pattern from just a few terms, regardless of the recurrence's order.
No -- a handful of early terms rarely confirms that a pattern continues forever, and this needs independent verification before it's trusted