Solving Simple Recurrences
students, imagine you are watching a video of a rabbit population grow or tracking how many tiles a robot places on the floor each day 🐇🤖. Often, the total on one day depends on the total from the previous day. That “depends on the past” idea is exactly what a recurrence relation describes. In this lesson, you will learn how to solve simple recurrences, which means finding a direct formula for the $n$th term instead of calculating every earlier term one by one.
Why simple recurrences matter
A recurrence relation is an equation that defines a sequence using earlier terms. For example, a sequence might satisfy $a_n = a_{n-1} + 3$ with $a_0 = 2$. This tells us how to build each term from the previous one. The challenge is that recurrences are often easy to write but not always easy to use. If you want to know $a_{100}$, calculating all the terms from $a_0$ to $a_{100}$ may be slow and messy.
That is why solving recurrences is important. A solved recurrence gives a closed-form formula, which means a formula that directly computes $a_n$ from $n$ alone. Closed forms help in computer science, economics, biology, and anywhere patterns grow step by step. They also connect to algorithm analysis, where recurrence relations model the running time of recursive algorithms. 📈
In this lesson, students, you will focus on simple recurrences first. These are the easiest kinds to solve and they build the foundation for more advanced methods later.
Core idea: turn repeated steps into a pattern
A simple recurrence usually has three parts:
- a rule linking one term to earlier term or terms,
- an initial condition such as $a_0 = 5$ or $a_1 = 2$,
- and a goal of finding a formula for $a_n$.
One of the most useful methods is called repeated substitution or iteration. The idea is to keep replacing the earlier term with the recurrence rule until a pattern appears.
Example 1: additive recurrence
Suppose
$$a_n = a_{n-1} + 4, \quad a_0 = 3.$$
Let’s expand the first few terms:
$$a_1 = a_0 + 4 = 3 + 4 = 7,$$
$$a_2 = a_1 + 4 = 7 + 4 = 11,$$
$$a_3 = a_2 + 4 = 11 + 4 = 15.$$
The pattern suggests that each step adds $4$. After $n$ steps, starting from $3$, we get
$$a_n = 3 + 4n.$$
You can check this formula:
- when $n = 0$, $a_0 = 3 + 4(0) = 3$,
- when $n = 1$, $a_1 = 3 + 4(1) = 7$,
- when $n = 2$, $a_2 = 3 + 4(2) = 11$.
This is a simple arithmetic sequence, and solving the recurrence reveals its closed form.
Example 2: multiplicative recurrence
Now consider
$$b_n = 2b_{n-1}, \quad b_0 = 5.$$
Expanding terms gives
$$b_1 = 2b_0 = 10,$$
$$b_2 = 2b_1 = 20,$$
$$b_3 = 2b_2 = 40.$$
Here each term is multiplied by $2$. That means
$$b_n = 5 \cdot 2^n.$$
This is a geometric sequence. A recurrence of the form $a_n = ra_{n-1}$ usually leads to exponential growth or decay, depending on $r$.
Solving by repeated substitution
Repeated substitution is especially useful when the recurrence combines a previous term with a simple added amount. Let’s see how it works carefully.
Suppose
$$c_n = c_{n-1} + 2, \quad c_0 = 1.$$
Substitute the recurrence into itself:
$$c_n = (c_{n-2} + 2) + 2 = c_{n-2} + 4.$$
Substitute again:
$$c_n = c_{n-3} + 6.$$
After $k$ steps, the pattern is
$$c_n = c_{n-k} + 2k.$$
If we choose $k = n$, then $c_{n-k} = c_0$, so
$$c_n = c_0 + 2n = 1 + 2n.$$
This method works because each substitution reveals how many times the same change is repeated. It is a very important reasoning skill in discrete mathematics because it connects the recursive rule to the total effect after many steps.
Recognizing common simple forms
Simple recurrences often fit one of these common types:
1. Constant addition
$$a_n = a_{n-1} + d$$
This produces an arithmetic sequence. The solution is
$$a_n = a_0 + dn.$$
2. Constant multiplication
$$a_n = ra_{n-1}$$
This produces a geometric sequence. The solution is
$$a_n = a_0r^n.$$
3. Additive plus multiplicative form
$$a_n = ra_{n-1} + d$$
This is still simple enough to solve in many cases by iteration or by looking for a pattern. Such recurrences appear in algorithm analysis and population models. For example, if
$$a_n = 3a_{n-1} + 2, \quad a_0 = 1,$$
then expanding gives
$$a_1 = 3(1) + 2 = 5,$$
$$a_2 = 3(5) + 2 = 17,$$
$$a_3 = 3(17) + 2 = 53.$$
Try to spot the pattern. Repeated substitution gives
$$a_n = 3^na_0 + 2(3^{n-1} + 3^{n-2} + \cdots + 3 + 1).$$
The sum in parentheses is a geometric series. Using the formula
$$1 + 3 + 3^2 + \cdots + 3^{n-1} = \frac{3^n - 1}{3 - 1},$$
we get
$$a_n = 3^n + 2\cdot\frac{3^n - 1}{2} = 3^n + 3^n - 1 = 2\cdot 3^n - 1.$$
So the closed form is
$$a_n = 2\cdot 3^n - 1.$$
Checking your answer
A smart habit in discrete mathematics is to verify your closed form. You can do this in two ways:
- Check the initial condition: does the formula give the correct starting value?
- Check the recurrence: if you replace $a_n$ and $a_{n-1}$ using the formula, does the equation hold?
For the example
$$a_n = 2\cdot 3^n - 1,$$
check the recurrence:
$$a_{n-1} = 2\cdot 3^{n-1} - 1.$$
Then
$$3a_{n-1} + 2 = 3\left(2\cdot 3^{n-1} - 1\right) + 2 = 2\cdot 3^n - 3 + 2 = 2\cdot 3^n - 1 = a_n.$$
This confirms the formula is correct ✅
Checking is important because it catches mistakes in algebra and pattern recognition. In recurrence relations, a beautiful-looking answer is not enough; it must satisfy both the recurrence and the starting value.
Connection to algorithms and real-world growth
Simple recurrences are not just abstract math. They appear in real systems.
Algorithmic example
Suppose a computer algorithm does $5$ units of work on the first input size and then adds $3$ units of work each time the size increases by one. That can be modeled by
$$T(n) = T(n-1) + 3, \quad T(1) = 5.$$
The solution is
$$T(n) = 5 + 3(n-1) = 3n + 2.$$
This tells us the work grows linearly. In algorithm analysis, linear growth is much better than quadratic or exponential growth.
Real-world example
Imagine a savings jar where you start with $20 and add $5 each week. Let $S(n)$ be the amount after $n$ weeks:
$$S(n) = S(n-1) + 5, \quad S(0) = 20.$$
Then
$$S(n) = 20 + 5n.$$
If you want the amount after $12$ weeks, you can calculate it directly:
$$S(12) = 20 + 5(12) = 80.$$
This is much faster than listing every weekly amount.
Common mistakes to avoid
When solving simple recurrences, watch out for these issues:
- Forgetting the initial condition. Without it, there may be many possible formulas.
- Mixing up $a_{n-1}$ and $a_n$. The recurrence describes how to build the next term from the previous one.
- Guessing a formula without checking it. A pattern can look right but still be wrong.
- Dropping indices too early during substitution. Keep track of how many times you expand.
A helpful strategy is to write the first few terms before attempting a formula. Small examples often reveal the pattern clearly.
Conclusion
students, solving simple recurrences means turning a step-by-step rule into a direct formula. The main tools are repeated substitution, pattern recognition, and verification. For recurrences like $a_n = a_{n-1} + d$ and $a_n = ra_{n-1}$, the closed forms are straightforward and very useful. More complicated recurrences in discrete mathematics and computer science are built from the same thinking: understand how each step depends on earlier steps, then summarize that process with a formula. That is why solving simple recurrences is a key part of the broader study of recurrence relations.
Study Notes
- A recurrence relation defines a sequence using earlier term or terms.
- A closed-form formula gives $a_n$ directly in terms of $n$.
- For $a_n = a_{n-1} + d$, the solution is $a_n = a_0 + dn$.
- For $a_n = ra_{n-1}$, the solution is $a_n = a_0r^n$.
- Repeated substitution expands the recurrence until a pattern appears.
- A recurrence of the form $a_n = ra_{n-1} + d$ often leads to a geometric-series expression.
- Always check both the initial condition and the recurrence to confirm your answer.
- Simple recurrences model real processes like savings growth, population change, and algorithm running time.
- Solving simple recurrences is a foundational skill for understanding recurrence relations in discrete mathematics.