STEP-BY-STEP LESSON · §5.7
Solving Recurrence Relations by Iteration
Derive an explicit formula by unfolding a recurrence, then verify it.
Before you begin
Defining Sequences Recursively
A recurrence relates terms but does not by itself specify where to start.
a_0=2
The rule a_n=2a_(n−1)+1 means: take the previous value, double it, and add 1.
a_n=2a_(n−1)+1, n≥1
Mathematical Induction I: Proving Formulas
P(n) must be a specific statement for every integer n in the stated range.
P(n): 1+2+…+n = n(n+1)/2, n≥1
Verify P(1) separately. Then choose arbitrary k≥1 and temporarily assume P(k).
1 = 1·2/2
Split the sum through k+1 into the known sum through k and the final term.
k(k+1)/2+(k+1)=(k+1)(k+2)/2
Symbols
- a_n
- value directly from n
- n,m,j
- integer indices or numbers of unfolding steps, within the stated bounds
Definitions and notation for this topic
Recurrence relation
A rule expressing terms in terms of preceding terms.
The initial value and the range where the rule applies belong to the definition. This recurrence is an example, not a universal symbol for recurrence relations.
Separate glossary example
a₁=3 and a_n=a_(n−1)+2 for integers n≥2 define 3,5,7,9,… .
a₁=2; aₙ=aₙ₋₁+2 for n≥2.
Recursive and explicit sequence formulas
A recursive rule defines later terms using earlier ones and initial values. An explicit formula gives a_n directly in terms of n and fixed parameters.
Check an explicit candidate against both the recurrence and the initial values. Matching a few terms alone does not prove the formulas agree for every index.
Separate glossary example
a₀=3, a_n=a_(n−1)+2 for n≥1 describes the same sequence as a_n=3+2n for n≥0.
Solve
For an equation, find all allowed values of its unknowns that make it true.
Substitution checks the value: 3+2=5.
In this course solve can also mean finding an explicit sequence satisfying a recurrence and its initial values; read the object named after the verb.
Separate glossary example
Solve x+2=5: x=3.
Step by step
Step 1 / 6
Unfold the previous term
Replace a_(n−1) using the same rule until the repeated contribution becomes visible.
a_n=a_(n−1)+3=a_(n−2)+6
Each unfolding adds another three.
Worked example
a_0=2, a_n=a_(n−1)+3. Derive a formula.
- Unfold n times: a_n=a_0+3n=2+3n.
- At n=0 the formula gives 2, as required.
- Substituting the previous term gives [2+3(n−1)]+3=2+3n, so the rule is satisfied.
Optional self-check
If c_1=4 and c_n=c_(n−1)+2, what is the explicit formula?
Show answer
c_n=4+2(n−1)=2n+2 for n≥1.