Induction for Recurrence Relations
A recurrence relation like $u_{n+1} = 3u_n + 1$ builds each term from the last — useful, but slow to evaluate. A closed-form formula like $u_n = \frac{5 \cdot 3^{n-1}-1}{2}$ lets you jump straight to any term. Mathematical induction is how you prove a closed form is correct, and the key move is using the recurrence relation itself inside the inductive step.
Given $u_1 = 1$ and $u_{n+1} = 2u_n + 1$, compute $u_1, u_2, u_3, u_4$ by hand. Before using any formula — write down what you think the pattern might be for $u_n$ in terms of $n$.
Every recurrence induction proof comes down to two key moves: recognise the recurrence connecting $u_{k+1}$ to $u_k$, then substitute the inductive hypothesis to reach the target formula.
The inductive step always begins: "By the recurrence, $u_{k+1} = f(u_k)$." You then replace $u_k$ with the assumed closed form. This is the critical move that distinguishes recurrence induction from ordinary summation induction.
Use recurrence → substitute IH → simplify → match target
Key facts
- A recurrence relation defines $u_{n+1}$ (or $u_{n+2}$) in terms of earlier terms
- A closed form gives $u_n$ directly from $n$ without iteration
- Second-order recurrences need two base cases
Concepts
- Why the recurrence must be used explicitly in the inductive step
- How to connect $u_{k+1}$ to $u_k$ via the recurrence, then use the IH
- The difference between first- and second-order recurrences
Skills
- Prove a closed-form formula for a linear recurrence by induction
- Prove an inequality for a Fibonacci-type recurrence
- Identify and fix errors in incomplete recurrence induction proofs
A recurrence relation defines each term from previous ones. For example:
This gives $u_2 = 7$, $u_3 = 22$, $u_4 = 67$, but computing $u_{100}$ requires 99 iterations. A closed form — a direct formula in $n$ — solves this:
Mathematical induction proves that the closed form is correct for all positive integers $n$. The strategy is:
- Base case: verify the formula holds for $n = 1$ (or $n = 1$ and $n = 2$ for second-order).
- Inductive hypothesis: assume $u_k = \text{[closed form at } k\text{]}$.
- Inductive step: write $u_{k+1}$ using the recurrence, substitute the IH, then simplify to reach the closed form at $k+1$.
A recurrence relation defines each term from previous ones. For example:
Pause — copy the definitions of recurrence relation and closed form, plus the two-step process: conjecture the closed form, prove it by induction into your book.
Quick check: When proving a closed form for $u_{n+1} = 3u_n + 1$ by induction, which is the correct first line of the inductive step?
We just saw that a recurrence like $u_{n+1}=3u_n+1$ defines the sequence implicitly, while a closed form gives $u_n$ directly. That raises a question: once you suspect the closed form $u_n=\frac{5\cdot3^{n-1}-1}{2}$, how does the inductive step substitute $u_k$ into $u_{k+1}=3u_k+1$ to verify $u_{k+1}=\frac{5\cdot3^k-1}{2}$? This card answers it → by computing $3\cdot\frac{5\cdot3^{k-1}-1}{2}+1=\frac{5\cdot3^k-1}{2}$.
Prove that if $u_1 = 2$ and $u_{n+1} = 3u_n + 1$, then $u_n = \dfrac{5 \cdot 3^{n-1} - 1}{2}$ for all $n \geq 1$.
LHS $= u_1 = 2$. RHS $= \dfrac{5 \cdot 3^{0} - 1}{2} = \dfrac{4}{2} = 2$. LHS = RHS. ✓
Assume true for $n = k$: $u_k = \dfrac{5 \cdot 3^{k-1} - 1}{2}$.
By the recurrence: $u_{k+1} = 3u_k + 1$
$= 3 \cdot \dfrac{5 \cdot 3^{k-1} - 1}{2} + 1 \quad$ (substitute IH)
$= \dfrac{5 \cdot 3^{k} - 3}{2} + 1$
$= \dfrac{5 \cdot 3^{k} - 3 + 2}{2}$
$= \dfrac{5 \cdot 3^{k} - 1}{2}$ ✓ (this is the formula with $n = k+1$).
By the principle of mathematical induction, $u_n = \dfrac{5 \cdot 3^{n-1} - 1}{2}$ for all $n \geq 1$. ∎
Prove that if $u_1 = 2$ and $u_{n+1} = 3u_n + 1$, then $u_n = \dfrac{5 \cdot 3^{n-1} - 1}{2}$ for all $n \geq 1$.
Pause — copy the complete induction proof for $u_n=\frac{5\cdot3^{n-1}-1}{2}$, highlighting the substitution of $u_k$ into the recurrence $u_{k+1}=3u_k+1$ into your book.
Did you get this? True or false: When proving a closed form for a first-order recurrence, you only need one base case.
Worked examples · 3 in a row, reveal as you go
Given $u_1 = 1$ and $u_{n+1} = 2u_n + 1$, prove by induction that $u_n = 2^n - 1$ for all $n \geq 1$.
Inductive step: By recurrence, $u_{k+1} = 2u_k + 1 = 2(2^k - 1) + 1 = 2^{k+1} - 2 + 1 = 2^{k+1} - 1$
Given $u_1 = 1$, $u_2 = 1$, $u_{n+2} = u_{n+1} + u_n$, prove $u_n \leq 2^{n-1}$ for all $n \geq 1$.
Given $u_1 = 3$ and $u_{n+1} = 2u_n - 1$, find a closed form for $u_n$ and prove it by induction.
Fill the gap: For $u_1 = 1$, $u_{n+1} = 2u_n + 1$, the inductive step gives $u_{k+1} = 2(2^k - 1) + 1 = 2^{k+1} - $ .
Misconceptions to fix · the 3 traps that cost marks
Did you get this? True or false: A recurrence of the form $u_{n+2} = u_{n+1} + u_n$ requires two base cases in an induction proof.
Activities · practice with the ideas
Given $u_1 = 1$ and $u_{n+1} = 2u_n + 1$, compute $u_1, u_2, u_3, u_4$ and verify they match $u_n = 2^n - 1$.
Write out in full the inductive step for the proof that $u_n = 2^n - 1$ given $u_{n+1} = 2u_n + 1$. Start with "By the recurrence…"
Given $u_1 = 3$ and $u_{n+1} = 2u_n - 1$, compute the first four terms and state the closed form.
Explain in your own words why you need two base cases for $u_{n+2} = u_{n+1} + u_n$ but only one for $u_{n+1} = 3u_n + 1$.
A student writes: "Assume $u_k = \frac{5 \cdot 3^{k-1}-1}{2}$. Therefore $u_{k+1} = \frac{5 \cdot 3^k - 1}{2}$." What is wrong with this proof?
Odd one out: Three of these statements about recurrence induction are correct. Which one is NOT?
Earlier you computed $u_1, u_2, u_3, u_4$ for $u_{n+1} = 2u_n + 1$, $u_1 = 1$ and guessed a pattern.
The closed form is $u_n = 2^n - 1$. The values are $1, 3, 7, 15, \ldots$ — always one less than a power of 2. The inductive step shows why: each application of the recurrence multiplies by 2 and adds 1, which is exactly what happens when you move from $2^k - 1$ to $2^{k+1} - 1$.
Pick your answer, then rate your confidence — that tells the system what to drill next. Each retry pulls a fresh mix from the bank.
Q1. Given $u_1 = 1$ and $u_{n+1} = 2u_n + 1$, prove by induction that $u_n = 2^n - 1$ for all positive integers $n$. (3 marks)
Q2. Given $u_1 = 3$ and $u_{n+1} = 2u_n - 1$, find a closed-form formula for $u_n$ and prove it by induction. (3 marks)
Q3. Given $u_1 = u_2 = 1$ and $u_{n+2} = u_{n+1} + u_n$ (Fibonacci sequence), prove by induction that $u_n \leq 2^{n-1}$ for all $n \geq 1$. (4 marks)
Comprehensive answers (click to reveal)
Activity answers: 1. $u_1=1, u_2=3, u_3=7, u_4=15$ — all match $2^n-1$ ✓ · 2. Start "By the recurrence, $u_{k+1}=2u_k+1=2(2^k-1)+1=2^{k+1}-1$" · 3. $u_1=3, u_2=5, u_3=9, u_4=17 \Rightarrow u_n = 2^n+1$ · 4. First-order only needs $u_k$; second-order needs both $u_k$ and $u_{k+1}$ in IH · 5. The student skipped the recurrence step — circular argument.
Q1 (3 marks): Base: $u_1=1=2^1-1$ ✓ [1]. IH: $u_k=2^k-1$. Step: $u_{k+1}=2u_k+1=2(2^k-1)+1=2^{k+1}-1$ [1]. Conclusion [1]. ∎
Q2 (3 marks): Compute: $3,5,9,17 \Rightarrow u_n = 2^n+1$ [1]. Base: $2^1+1=3$ ✓. Step: $u_{k+1}=2(2^k+1)-1=2^{k+1}+1$ [1]. Conclusion [1]. ∎
Q3 (4 marks): Base cases $n=1,2$ ✓ [1]. IH: $u_k\leq2^{k-1}$ and $u_{k+1}\leq2^k$ [1]. Step: $u_{k+2}=u_{k+1}+u_k\leq 2^k+2^{k-1}=3\cdot2^{k-1}\leq4\cdot2^{k-1}=2^{k+1}$ [1]. Conclusion [1]. ∎
Five timed questions on recurrence induction. Beat the boss to bank a tier — gold (90% + speed), silver (75%), or bronze (50%). Replays welcome.
⚔ Enter the arenaClimb platforms by answering recurrence and induction questions. Lighter alternative to the boss.
Mark lesson as complete
Tick when you've finished the practice and review.