Ch 5. Recurrence Relations
5.2 Notation and Solving Recurrence Relations
While you may be familiar with mathematical equations, such as [latex]y = 3x + 2[/latex], recurrence relations are a type of equation that defines each term of a sequence based on one or more previous terms. Instead of expressing what value an output is based on an input, recurrence relations express how a sequence evolves step-by-step. This requires including the initial conditions of the recurrence relation, which specify the starting values of a sequence. Recurrence relations are widely used in IT to model recursive algorithms (see Section 5.4).
Notation
Recurrence relations typically takes the form
[latex]a_{n} = f(a_{n-1}, a_{n-2}, \dots )[/latex]
where [latex]a_{n}[/latex] is the current term and [latex]f[/latex] is a function involving previous terms. One of the most famous recurrence relations in mathematics is given in the next example.
Example 5.13
The Fibonacci sequence has the recurrence relation
[latex]f_{n} = f_{n-1} + f_{n-2}[/latex]
Notice that each term is the sum of the two preceding terms. In addition, the Fibonacci sequence has the initial conditions.
[latex]f_{0} = 0, \quad f_{1} = 1[/latex]
They allow the computation of all subsequent terms using the recurrence relation.
The next example illustrates how recurrence relations are used in business mathematics.
Example 5.14
Suppose you invest an initial amount [latex]P_{0}[/latex] dollars into a savings account that earns interest compounded annually at a fixed rate [latex]r[/latex] (expressed as a decimal). The amount of money in the account after [latex]n[/latex] years can be modelled by a recurrence relation.
Let [latex]P_{n}[/latex] represent the amount in the account after [latex]n[/latex] years. Then
[latex]P_{n} = (1 + r)P_{n-1}[/latex]
The initial condition is [latex]P_{0}[/latex] = initial investment.
Let’s say the initial investment is [latex]P_{0} = 1000[/latex] and the annual interest rate is [latex]r = 5% = 0.05[/latex]. Then the recurrence becomes
[latex]P_{n} = 1.05 P_{n-1}, \quad P_{0} = 1000[/latex]
We can compute the first few terms as
[latex]P_{1} = 1.05 \cdot 1000 = 1050[/latex]
[latex]P_{2} = 1.05 \cdot 1050 = 1102.50[/latex]
[latex]P_{3} = 1.05 \cdot 1102.50 = 1157.63[/latex]
This recurrence relation models how the investment grows over time due to compound interest.
The following example uses a result from set theory established in Chapter 4.
Example 5.15
Let’s define a recurrence relation that models the number of subsets (i.e., the size of the power set) of a finite set with [latex]n[/latex] elements. Recall Theorem 4.1:
If a set [latex]A[/latex] has [latex]n[/latex] elements, then its power set [latex]|\mathcal{P}(A)|[/latex] has [latex]2^{n}[/latex] subsets.
Let [latex]P_{n}[/latex] be the number of subsets of a set with [latex]n[/latex] elements. Then
[latex]P_{n} = 2P_{n-1}[/latex]
and the initial condition is [latex]P_{0} = 1[/latex]. This reflects the fact that the empty set has exactly one subset: itself.
Each time we add a new element to a set of size [latex]n - 1[/latex], every existing subset can either include or exclude the new element. This doubles the number of subsets.
We compute [latex]P_{n}[/latex] for [latex]n = 0[/latex] to [latex]4[/latex] as follows:
[latex]P_{0} = 1[/latex]
[latex]P_{1} = 2 P_{0} = 2[/latex]
[latex]P_{2} = 2 P_{1} = 4[/latex]
[latex]P_{3} = 2 P_{2} = 8[/latex]
[latex]P_{4} = 2 P_{3} = 16[/latex]
Note that these results match the formula for [latex]P_{n} = 2^{n}[/latex].
The examples thus far have been situated in mathematics; however, the next example demonstrates how recurrence relations are used in IT.
Example 5.16
Suppose we define a recursive process that builds a string by duplicating the previous string and appending a fixed character. Let [latex]s_{n}[/latex] be a string defined recursively as follows:
Initial condition: [latex]s_{0}[/latex] = “a”
Recurrence relation: [latex]s_{n} = s_{n-1} + s_{n-1}[/latex] + “b”
This means that each new string is formed by duplicating the previous string, concatenating it with itself, and then appending the character “b”. Building the sequence, we have
[latex]s_{0}[/latex] = “a”
[latex]s_{1}[/latex] = “a” + “a” + “b” = “aab”
[latex]s_{2}[/latex] = “aab” + “aab” + “b” = “aabaabb”
[latex]s_{3}[/latex] = “aabaabb” + “aabaabb” + “b” = “aabaabbaabaabbb”
Let [latex]L_{n} = |s_{n}|[/latex] be the length of [latex]s_{n}[/latex]. Then
[latex]L_{0} = 1[/latex]
[latex]L_{n} = 2L_{n-1} + 1[/latex]
This gives a recurrence relation for the length of the string
[latex]L_{n} = 2 L_{n-1} + 1, \quad L_{0} = 1[/latex]
Computing the first few values of this recurrence gives
[latex]L_{1} = 2 \cdot 1 + 1 = 3[/latex]
[latex]L_{2} = 2 \cdot 3 + 1 = 7[/latex]
[latex]L_{3} = 2 \cdot 7 + 1 = 15[/latex]
This recurrence models exponential string growth, a common pattern in recursive string construction algorithms.
Recurrence relations also appear in many puzzles and toys, such as the Tower of Hanoi puzzle and a Rubik’s Cube.
Example 5.17
The Tower of Hanoi is a classic puzzle consisting of three pegs arranged in a row and a stack of disks of different sizes. The goal is to move the entire stack from the left peg to the right one, following a few simple rules:
- All the disks begin on the left peg, arranged from largest at the bottom to smallest at the top.
- You can move only one disk at a time.
- A larger disk can never be placed on top of a smaller one.
The minimum number of moves needed to complete the puzzle with [latex]n[/latex] disks will be denoted by [latex]T_{n}[/latex]. The recurrence relation is
[latex]T_{n} = 2 T_{n-1} + 1[/latex]
and the initial condition is [latex]T_{1} = 1[/latex]. This means to move [latex]1[/latex] disk, you need [latex]1[/latex] move. To move [latex]n[/latex] disks, you first move [latex]n - 1[/latex] disks to an auxiliary peg, move the largest disk, then move the [latex]n - 1[/latex] disks onto the largest disk.
We will compute the first few values:
[latex]T_{2} = 2 T_{1} + 1 = 2 \cdot 1 + 1 = 3[/latex]
[latex]T_{3} = 2T_{2} + 1 = 2 \cdot 3 + 1 = 7[/latex]
[latex]T_{4} = 2T_{3} + 1 = 2 \cdot 7 + 1 = 15[/latex]
This pattern appears to be the closed-form solution [latex]T_{n} = 2^{n} - 1[/latex].
Example 5.18
A Rubik’s Cube is a well-known mechanical puzzle made up of a larger cube with six coloured faces, each divided into smaller squares. By twisting its layers, the colours become mixed. The objective is to return the cube to its solved state, where every face shows a single solid colour. This is typically done with a layer-by-layer approach, where the cube is solved in stages: first layer, middle layer, final layer.
We will define a recurrence relation that models the minimum number of moves required to solve the cube using this method, assuming each layer builds on the previous one. First, we represent the minimum number of moves required to solve [latex]n[/latex] layers of the cube, by [latex]m_{n}[/latex]. Then we define
[latex]m_{n} = m_{n-1} + f(n)[/latex]
where [latex]m_{n - 1}[/latex] is the number of moves to solve the first [latex]n - 1[/latex] layers and [latex]f(n)[/latex] is the number of moves required to solve layer [latex]n[/latex], depending on its complexity.
The initial condition is [latex]m_{1} = 8[/latex]. This assumes solving the first layer takes approximately [latex]8[/latex] moves using an efficient method.
Let’s assume [latex]f(2) = 12[/latex] moves for the middle layer and [latex]f(3) = 20[/latex] moves for the final layer. Then
[latex]m_{2} = m_{1} + f(2) = 8 + 12 = 20[/latex]
[latex]m_{3} = m_{2} + f(3) = 20 + 20 = 40[/latex]
We can see that the recurrence builds up the total move count layer by layer.
Alternatively, if we assume [latex]f(n) = 4n + 4[/latex], then
[latex]m_{n} = m_{n-1} + 4n+ 4[/latex]
Solving Recurrence Relations
There are several methods to solve recurrence relations, and in this textbook, we focus on the following three:
- Iteration
- Closed-form solution
- Characteristic equation
The first method is to use iteration, which expands the recurrence step by step to find a pattern.
Example 5.19
A company starts with [latex]$2,000[/latex] in revenue and earns an additional [latex]$3,000[/latex] each month. [latex]T_{n}[/latex] represents total revenue after [latex]n[/latex] months. The recurrence relation for this situation is
[latex]T_{n} = T_{n-1} + 3, \quad \text{with } T_{0} = 2[/latex]
To solve this recurrence relation, first expand the recurrence (iterate) by applying the recurrence repeatedly to express [latex]T_{n}[/latex] in terms of earlier terms:
[latex]T_{n} = T_{n-1} + 3[/latex]
[latex]= (T_{n-2} + 3) + 3[/latex]
[latex]= T_{n-2} + 2 \cdot 3[/latex]
[latex]= ((T_{n-3} + 3) + 3) + 2 \cdot 3[/latex]
[latex]= T_{n-3} + 3 \cdot 3[/latex]
[latex]= \dots[/latex]
[latex]= T_{n-k} + 3k[/latex]
Then identify the pattern by continuing until the initial condition [latex]T_{0} = 2[/latex] is reached. That happens when [latex]k = n[/latex], so
[latex]T_{n} = T_{0} + 3n = 2 + 3n[/latex]
Finally, identify the final answer which is [latex]T_{n} = 3n+ 2[/latex].
The second method is to find a closed-form solution, which is a formula derived that directly computes [latex]a_{n}[/latex] without recursion.
Example 5.20
A company starts with [latex]5[/latex] customers and doubles its customer base every month. Let [latex]t_{n}[/latex] represent the number of customers after [latex]n[/latex] months. The recurrence relation for this situation is
[latex]t_{n} = 2t_{n-1}, \quad \text{with } t_{0} = 5[/latex]
To solve this recurrence relation, first identify the pattern by computing the first several terms:
[latex]t_{1} = 2t_{0} = 2 \cdot 5 = 10[/latex]
[latex]t_{2} = 2t_{1} = 2 \cdot 10 = 20[/latex]
[latex]t_{3} = 2t_{2} = 2 \cdot 20 = 40[/latex]
[latex]t_{4} = 2t_{3} = 2 \cdot 40 = 80[/latex]
We can see that [latex]t_{n} = 5(2^{n})[/latex]. Next, we prove this closed-form by mathematical induction (see Section 3.6).
Basis Step: For [latex]n = 0, t_{0} = 5(2^{0}) = 5(1) = 5[/latex].
Inductive Step: Assume [latex]t_{k} = 5(2^{k})[/latex] is true for some [latex]k \geq 0[/latex]. Then
[latex]t_{k+1} = 2t_{k} = 2 \cdot 5(2^{k}) = 5(2^{k+1})[/latex]
So, the formula holds for [latex]k + 1[/latex], and by induction, it holds for all [latex]n \geq 0[/latex].
Finally, identify the final answer, which is [latex]T_{n} = 5(2^{n})[/latex].
The third method is the characteristic equation method, which is used for linear homogeneous recurrence relations with constant coefficients.
A linear homogeneous recurrence relation of order [latex]k[/latex] with constant coefficients is a recurrence relation of the form
[latex]a_{n} = c_{1}a_{n-1} + c_{2}a_{n-2} + \dots + c_{k}a_{n-k}[/latex]
where [latex]a_{n}[/latex] is the term being defined, [latex]c_{1}, c_{2}, \dots, c_{k}[/latex] are constant coefficients, [latex]k[/latex] is the order of the recurrence. The relation is homogeneous, meaning there is no additional non-zero term.
Example 5.21
A second-order linear homogeneous recurrence relation with constant coefficients is
[latex]a_{n} = 3a_{n-1} - 2a_{n-2}[/latex]
This uses the two previous terms and has constant coefficients [latex]3[/latex] and [latex]-2[/latex].
The following theorem is used to find general solutions of second-order linear homogeneous recurrence relations. Note that in this theorem, the roots of the characteristic equation must be distinct.
Theorem 5.1: General Solution for Distinct Roots
Let [latex]a_{n}[/latex] be a sequence defined by a second-order linear homogeneous recurrence relation with constant coefficients:
[latex]a_{n} = r_{1}a_{n-1} + r_{2}a_{n-2}[/latex]
for constants [latex]r_{1}[/latex], [latex]r_{2}[/latex] and for all [latex]n \geq 2[/latex]. Then the following statements hold:
- If [latex]a_{n}^{(1)}[/latex] and [latex]a_{n}^{(2)}[/latex] are two solutions to the recurrence relation, then any linear combination [latex]a_{n} = c_{1}a_{n}^{(1)} + c_{2}a_{n}^{(2)}[/latex] is also a solution, where [latex]c_{1}[/latex] and [latex]c_{2}[/latex] are constants.
- If [latex]r[/latex] is a root of the characteristic equation [latex]x^{2} - rx - r_{2} = 0[/latex] then the sequence [latex]a_{n} = r^{n}[/latex] is a solution to the recurrence relation.
- If the characteristic equation has two distinct roots [latex]r_{1}[/latex] and [latex]r_{2}[/latex], then the general solution to the recurrence relation is [latex]a_{n} = c_{1} r_{1}^{n}n + c_{2} r_{2}^{n}[/latex], where [latex]c_{1}[/latex] and [latex]c_{2}[/latex] are constants determined by the initial conditions.
Proof
- Let [latex]a_{n}^{(1)}[/latex] and [latex]a_{n}^{(2)}[/latex] be two solutions of the recurrence relation
[latex]a_{n} = r_{1}a_{n-1} + r_{2}a_{n-2}[/latex]
Define a new sequence
[latex]a_{n} = c_{1}a_{n}^{(1)} + c_{2}a_{n}^{(2)}[/latex]
Then
[latex]a_{n} = c_{1}a_{n}^{(1)} + c_{2}a_{n}^{(2)}[/latex]
[latex]= c_{1}(r_{1}a_{n-1}^{(1)} + r_{2}a_{n-2}^{(1)}) + c_{2}(r_{1}a_{n-1}^{(2)} + r_{2}a_{n-2}^{(2)})[/latex]
[latex]= r_{1}(c_{1} a_{n-1}^{(1)} + c_{2} a_{n-1}^{(2)}) + r_{2}(c_{1} a_{n-2}^{(1)} + c_{2} a_{n-2}^{(2)})[/latex]
[latex]= r_{1} a_{n-1} + r_{2} a_{n-2}[/latex]
Hence, [latex]a_{n}[/latex] also satisfies the recurrence relation.
[latex]\square[/latex]
- Suppose the characteristic equation is
[latex]x^{2} - r_{1}x - r_{2} = 0[/latex]
Let [latex]r[/latex] be a root of this equation. Define the sequence
[latex]a_{n} = r^{n}[/latex]
Then
[latex]a_{n-1} = r^{n-1}[/latex]
[latex]a_{n-2} = r^{n-2}[/latex]
Substitute into the recurrence [latex]a_{n} = r_{1}a_{n-1} + r_{2}a_{n-2}[/latex] to obtain
[latex]r^{n} = r_{1} r^{n-1} + r_{2} r^{n-2}[/latex]
Divide both sides by [latex]r^{n-2}[/latex] to get
[latex]r^{2} = r_{1}r + r_{2}[/latex]
which is exactly the characteristic equation. Thus, [latex]a_{n} = r^{n}[/latex] is a solution.
[latex]\square[/latex]
- Let the characteristic equation
[latex]x^{2} - r_{1}x - r_{2} = 0[/latex]
have two distinct roots [latex]\alpha[/latex] and [latex]\beta[/latex]. Then from b), both [latex]a_{n} = \alpha^{n}[/latex] and [latex]a_{n} = \beta^{n}[/latex] are solutions. By a), any linear combination
[latex]a_{n} = c_{1}\alpha^{n} + c_{2}\beta^{n}[/latex]
is also a solution. To determine [latex]c_{1}[/latex] and [latex]c_{2}[/latex], use the initial conditions
[latex]a_{0} = c_{1}\alpha^{0} + c_{2}\beta^{0} = c_{1} + c_{2}[/latex]
[latex]a_{1} = c_{1}\alpha^{1} + c_{2}\beta^{1} = c_{1}\alpha + c_{2}\beta[/latex]
Solve this system to find [latex]c_{1}[/latex] and [latex]c_{2}[/latex]. Thus, the general solution is
[latex]a_{n} = c_{1}\alpha^{n} + c_{2}\beta^{n} \quad[/latex]
[latex]\square[/latex]
The following example demonstrates how to apply Theorem 5.1.
Example 5.22
Solve the recurrence relation [latex]a_{n} = 5a_{n-1} - 6a_{n-2}[/latex] with initial conditions [latex]a_{0} = 2[/latex] and [latex]a_{1} = 7[/latex].
The characteristic equation is
[latex]x^{2} - 5x + 6 = 0[/latex]
Factoring the equation gives
[latex]x^{2} - 5x + 6 = (x - 2)(x - 3)[/latex]
Then the roots are [latex]r_{1} = 2[/latex] and [latex]r_{2} = 3[/latex]. These are distinct, so the general solution is
[latex]a_{n} = c_{1}(2^{n}) + c_{2}(3^{n})[/latex]
Use [latex]a_{0} = 2[/latex], and [latex]a_{1} = 7[/latex] to obtain
[latex]a_{0} = c_{1}(2^{0}) + c_{2}(3^{0}) = c_{1} + c_{2} = 2 \quad \quad[/latex](1)
[latex]a_{1} = c_{1}(2^{1}) + c_{2}(3^{1}) = 2c_{1} + 3c_{2} = 7\quad[/latex](2)
From (1),
[latex]c_{1} + c_{2} = 2 \Rightarrow c_{1} = 2 -c_{2}\quad[/latex](3)
Substitute (3) into (2) to get
[latex]2(2 -c_{2}) + 3c_{2} = 7[/latex]
[latex]4 -2c_{2} + 3c_{2} = 7[/latex]
[latex]c_{2} = 3, c_{1} = -1[/latex]
The final solution is obtained by substituting back
[latex]a_{n} = -1(2^{n}) + 3(3^{n}) = -2^{n} + 3^{n+1}[/latex]
Theorem 5.1 only applies to general solutions with distinct roots, such as in the previous example. The following theorem is used when the roots of the characteristic equation are repeated.
Theorem 5.2: General Solution for Repeated Roots
Let a sequence [latex]\{ a_{n} \}[/latex] satisfy the recurrence relation
[latex]a_{n} = r_{1}a_{n-1} + r_{2}a_{n-2}[/latex]
and suppose the characteristic equation
[latex]x^{2} -r_{1}x -r_{2} = 0[/latex]
has a repeated root [latex]r[/latex]. Then
- The sequence [latex]a_{n} = r^{n}[/latex] is a solution to the recurrence relation.
- The sequence [latex]a_{n} = nr^{n}[/latex] is also a solution to the recurrence relation.
- The general solution is [latex]a_{n} = c_{1}r^{n} + c_{2}nr^{n}[/latex], where [latex]c_{1}[/latex] and [latex]c_{2}[/latex] are constants determined by the initial conditions.
Proof
- Given the recurrence
[latex]a_{n} = r_{1}a_{n-1} + r_{2}a_{n-2}[/latex]
the characteristic equation is
[latex]x^{2} -r_{1}x -r_{2} = 0[/latex]
Suppose this has a repeated root [latex]r[/latex]. Then
[latex]x^{2} -r_{1}x -r_{2} = (x -r)^{2}[/latex]
Expanding, we have
[latex]x^{2} -2rx + r^{2} = x^{2} -r_{1}x -r_{2}[/latex]
Therefore [latex]r_{1} = 2r[/latex] and [latex]r_{2} = -r^{2}[/latex].
Let [latex]a_{n} = r^{n}[/latex]. Then the proof follows from the proof of Theorem 5.1 b).
[latex]\square[/latex]
- Let [latex]a_{n} = nr^{n}[/latex]. Then
[latex]a_{n-1} = (n -1)r^{n-1}[/latex]
[latex]a_{n-2} = (n -2)r^{n-2}[/latex]
Substituting into the recurrence and simplifying, we have
[latex]a_{n} = r_{1}a_{n-1} + r_{2}a_{n-2}[/latex]
[latex]= 2r(n -1)r^{n-1} -r^{2}(n -2)r^{n-2}[/latex]
[latex]= 2(n -1)r^{n} - (n -2)r^{n}[/latex]
[latex]= [2(n -1) - (n - 2)]r^{n}[/latex]
[latex]= (2n - 2 - n + 2)r^{n}[/latex]
[latex]= nr^{n}[/latex]
So, [latex]a_{n} = nr^{n}[/latex] satisfies the recurrence.
[latex]\square[/latex]
- According to Theorem 5.1 a), since both [latex]r^{n}[/latex] and [latex]nr^{n}[/latex] are solutions, and the recurrence is linear and homogeneous, any linear combination, such as
[latex]a_{n} = c_{1}r^{n} + c_{2}nr^{n}[/latex]
is also a solution. The constants [latex]c_{1}[/latex] and [latex]c_{2}[/latex] are determined by the initial conditions.
[latex]\square[/latex]
Real-World Example 5.2: Server Load Balancing
Suppose you're managing a server that handles incoming requests. Each minute, the number of requests doubles compared to the previous minute, and an additional [latex]100[/latex] requests come from a scheduled batch job.
Let’s define [latex]a_{n}[/latex] to be the total number of requests at minute [latex]n[/latex] with initial condition [latex]a_{0} = 50[/latex] (starting with [latex]50[/latex] requests). The recurrence relation is
[latex]a_{n} = 2a_{n-1} + 100[/latex]
We will use the closed-form solution method to solve this recurrence relation by first computing a few terms:
[latex]a_{1} = 2(50) + 100 = 200[/latex]
[latex]a_{2} = 2(200) + 100 = 500[/latex]
[latex]a_{3} = 2(500) + 100 = 1100[/latex]
Next, we guess a solution of the form
[latex]a_{n} = A(2^{n}) + B[/latex]
Substitute this into the recurrence and simplify to obtain
[latex]A(2^{n}) + B = 2(A(2^{n-1} + B) + 100[/latex]
[latex]= A(2^{n}) + 2B + 100[/latex]
[latex]\Rightarrow B = 2B + 100 \Rightarrow B = -100[/latex]
Now plug back to find [latex]A[/latex] using [latex]a_{0} = 50[/latex] to get
[latex]a_{0} = A(2^{0}) - 100 = A - 100 = 50 \Rightarrow A = 150[/latex]
The final closed-form solution is
[latex]a_{n} = 150(2^{n}) - 100[/latex]
This formula helps predict server load at any minute [latex]n[/latex]. For example, after 5 minutes
[latex]a_{5} = 150(2^{5}) - 100 = 150(32) - 100 = 4700[/latex] requests
