We have seen that it is often easier to find recursive definitions than closed formulas. Lucky for us, there are a few techniques for converting recursive definitions to closed formulas. Doing so is called . Recall that the recurrence relation is a recursive definition without the initial conditions. For example, the recurrence relation for the Fibonacci sequence is \(F_n = F_ + F_\text<.>\) (This, together with the initial conditions \(F_0 = 0\) and \(F_1 = 1\) give the entire recursive definition for the sequence.)
Find a recurrence relation and initial conditions for \(1, 5, 17, 53, 161, 485\ldots\text<.>\)
Solution
Finding the recurrence relation would be easier if we had some context for the problem (like the Tower of Hanoi, for example). Alas, we have only the sequence. Remember, the recurrence relation tells you how to get from previous terms to future terms. What is going on here? We could look at the differences between terms: \(4, 12, 36, 108, \ldots\text<.>\) Notice that these are growing by a factor of 3. Is the original sequence as well? \(1\cdot 3 = 3\text\) \(5 \cdot 3 = 15\text\) \(17 \cdot 3 = 51\) and so on. It appears that we always end up with 2 less than the next term. Aha!
So \(a_n = 3a_ + 2\) is our recurrence relation and the initial condition is \(a_0 = 1\text<.>\)
We are going to try to solve these recurrence relations. By this we mean something very similar to solving differential equations: we want to find a function of \(n\) (a closed formula) which satisfies the recurrence relation, as well as the initial condition. 2 Recurrence relations are sometimes called difference equations since they can describe the difference between terms and this highlights the relation to differential equations further. Just like for differential equations, finding a solution might be tricky, but checking that the solution is correct is easy.
Check that \(a_n = 2^n + 1\) is a solution to the recurrence relation \(a_n = 2a_ - 1\) with \(a_1 = 3\text<.>\)
Solution
First, it is easy to check the initial condition: \(a_1\) should be \(2^1 + 1\) according to our closed formula. Indeed, \(2^1 + 1 = 3\text\) which is what we want. To check that our proposed solution satisfies the recurrence relation, try plugging it in.
\begin 2a_ - 1 \amp = 2(2^ + 1) - 1 \\ \amp = 2^n + 2 - 1 \\ \amp = 2^n +1\\ \amp = a_n. \end
That's what our recurrence relation says! We have a solution.
Sometimes we can be clever and solve a recurrence relation by inspection. We generate the sequence using the recurrence relation and keep track of what we are doing so that we can see how to jump to finding just the \(a_n\) term. Here are two examples of how you might do that.
refers to the phenomenon when many terms in a large sum cancel out - so the sum “telescopes.” For example:
\begin (2 - 1) + (3 - 2) + (4 - 3) + \cdots + (100 - 99) + (101 - 100) = -1 + 101 \end
because every third term looks like: \(2 + -2 = 0\text\) and then \(3 + -3 = 0\) and so on.
We can use this behavior to solve recurrence relations. Here is an example.
Solve the recurrence relation \(a_n = a_ + n\) with initial term \(a_0 = 4\text<.>\)
Solution
To get a feel for the recurrence relation, write out the first few terms of the sequence: \(4, 5, 7, 10, 14, 19, \ldots\text<.>\) Look at the difference between terms. \(a_1 - a_0 = 1\) and \(a_2 - a_1 = 2\) and so on. The key thing here is that the difference between terms is \(n\text<.>\) We can write this explicitly: \(a_n - a_ = n\text<.>\) Of course, we could have arrived at this conclusion directly from the recurrence relation by subtracting \(a_\) from both sides.
Now use this equation over and over again, changing \(n\) each time:
\begin a_1 - a_0 \amp = 1\\ a_2 - a_1 \amp = 2\\ a_3 - a_2 \amp = 3\\ \vdots \quad \amp \quad \vdots\\ a_n - a_ \amp = n. \end
Add all these equations together. On the right-hand side, we get the sum \(1 + 2 + 3 + \cdots + n\text<.>\) We already know this can be simplified to \(\frac\text<.>\) What happens on the left-hand side? We get
\begin (a_1 - a_0) + (a_2 - a_1) + (a_3 - a_2) + \cdots (a_ - a_)+ (a_n - a_). \end
This sum telescopes. We are left with only the \(-a_0\) from the first equation and the \(a_n\) from the last equation. Putting this all together we have \(-a_0 + a_n = \frac\) or \(a_n = \frac + a_0\text<.>\) But we know that \(a_0 = 4\text<.>\) So the solution to the recurrence relation, subject to the initial condition is
(Now that we know that, we should notice that the sequence is the result of adding 4 to each of the triangular numbers.)
The above example shows a way to solve recurrence relations of the form \(a_n = a_ + f(n)\) where \(\sum_^n f(k)\) has a known closed formula. If you rewrite the recurrence relation as \(a_n - a_ = f(n)\text\) and then add up all the different equations with \(n\) ranging between 1 and \(n\text\) the left-hand side will always give you \(a_n - a_0\text<.>\) The right-hand side will be \(\sum_^n f(k)\text\) which is why we need to know the closed formula for that sum.
However, telescoping will not help us with a recursion such as \(a_n = 3a_ + 2\) since the left-hand side will not telescope. You will have \(-3a_\)'s but only one \(a_\text<.>\) However, we can still be clever if we use .
We have already seen an example of iteration when we found the closed formula for arithmetic and geometric sequences. The idea is, we iterate the process of finding the next term, starting with the known initial condition, up until we have \(a_n\text<.>\) Then we simplify. In the arithmetic sequence example, we simplified by multiplying \(d\) by the number of times we add it to \(a\) when we get to \(a_n\text\) to get from \(a_n = a + d + d + d + \cdots + d\) to \(a_n = a + dn\text<.>\)
To see how this works, let's go through the same example we used for telescoping, but this time use iteration.
Use iteration to solve the recurrence relation \(a_n = a_ + n\) with \(a_0 = 4\text<.>\)
AnswerAgain, start by writing down the recurrence relation when \(n = 1\text<.>\) This time, don't subtract the \(a_\) terms to the other side:
\begin a_1 = a_0 + 1. \end
Now \(a_2 = a_1 + 2\text\) but we know what \(a_1\) is. By substitution, we get
\begin a_2 = (a_0 + 1) + 2. \end
Now go to \(a_3 = a_2 + 3\text\) using our known value of \(a_2\text\)
\begin a_3 = ((a_0 + 1) + 2) + 3. \end
We notice a pattern. Each time, we take the previous term and add the current index. So
\begin a_n = ((((a_0 + 1) +2)+3)+\cdots + n-1) + n. \end
Regrouping terms, we notice that \(a_n\) is just \(a_0\) plus the sum of the integers from \(1\) to \(n\text<.>\) So, since \(a_0 = 4\text\)
Of course in this case we still needed to know formula for the sum of \(1,\ldots,n\text<.>\) Let's try iteration with a sequence for which telescoping doesn't work.
Solve the recurrence relation \(a_n = 3a_ + 2\) subject to \(a_0 = 1\text<.>\)
AnswerAgain, we iterate the recurrence relation, building up to the index \(n\text<.>\)
\begin a_1 \amp = 3a_0 + 2\\ a_2 \amp = 3(a_1) + 2 = 3(3a_0 + 2) + 2\\ a_3 \amp = 3[a_2] + 2 = 3[3(3a_0 + 2) + 2] + 2\\ \vdots \amp \qquad \vdots \qquad \qquad \vdots\\ a_n \amp = 3(a_) + 2 = 3(3(3(3\cdots(3a_0 + 2) + 2) + 2)\cdots + 2)+ 2. \end
It is difficult to see what is happening here because we have to distribute all those 3's. Let's try again, this time simplifying a bit as we go.
\begin a_1 \amp = 3a_0 + 2\\ a_2 \amp = 3(a_1) + 2 = 3(3a_0 + 2) + 2 = 3^2a_0 + 2\cdot 3 + 2\\ a_3 \amp = 3[a_2] + 2 = 3[3^2a_0 + 2\cdot 3 + 2] + 2 = 3^3 a_0 + 2 \cdot 3^2 + 2 \cdot 3 + 2\\ \vdots \amp \qquad\quad \vdots \hspace \vdots\\ a_n \amp = 3(a_) + 2 = 3(3^a_0 + 2 \cdot 3^ + \cdots +2)+ 2\\ \amp \qquad \qquad = 3^n a_0 + 2\cdot 3^ + 2 \cdot 3^ + \cdots + 2\cdot 3 + 2. \end
Now we simplify. \(a_0 = 1\text\) so we have \(3^n + \langle\text\rangle\text<.>\) Note that all the other terms have a 2 in them. In fact, we have a geometric sum with first term \(2\) and common ratio \(3\text<.>\) We have seen how to simplify \(2 + 2\cdot 3 + 2 \cdot 3^2 + \cdots + 2\cdot 3^\text<.>\) We get \(\frac\) which simplifies to \(3^n - 1\text<.>\) Putting this together with the first \(3^n\) term gives our closed formula:
\begin a_n = 2\cdot 3^n - 1. \end
Iteration can be messy, but when the recurrence relation only refers to one previous term (and maybe some function of \(n\)) it can work well. However, trying to iterate a recurrence relation such as \(a_n = 2 a_ + 3 a_\) will be way too complicated. We would need to keep track of two sets of previous terms, each of which were expressed by two previous terms, and so on. The length of the formula would grow exponentially (double each time, in fact). Luckily there happens to be a method for solving recurrence relations which works very well on relations like this.
Suppose we want to solve a recurrence relation expressed as a combination of the two previous terms, such as \(a_n = a_ + 6a_\text<.>\) In other words, we want to find a function of \(n\) which satisfies \(a_n - a_ - 6a_ = 0\text<.>\) Now iteration is too complicated, but think just for a second what would happen if we did iterate. In each step, we would, among other things, multiply a previous iteration by 6. So our closed formula would include \(6\) multiplied some number of times. Thus it is reasonable to guess the solution will contain parts that look geometric. Perhaps the solution will take the form \(r^n\) for some constant \(r\text<.>\)
The nice thing is, we know how to check whether a formula is actually a solution to a recurrence relation: plug it in. What happens if we plug in \(r^n\) into the recursion above? We get
Now solve for \(r\text\)
so by factoring, \(r = -2\) or \(r = 3\) (or \(r = 0\text\) although this does not help us). This tells us that \(a_n = (-2)^n\) is a solution to the recurrence relation, as is \(a_n = 3^n\text<.>\) Which one is correct? They both are, unless we specify initial conditions. Notice we could also have \(a_n = (-2)^n + 3^n\text<.>\) Or \(a_n = 7(-2)^n + 4\cdot 3^n\text<.>\) In fact, for any \(a\) and \(b\text\) \(a_n = a(-2)^n + b 3^n\) is a solution (try plugging this into the recurrence relation). To find the values of \(a\) and \(b\text\) use the initial conditions.
This points us in the direction of a more general technique for solving recurrence relations. Notice we will always be able to factor out the \(r^\) as we did above. So we really only care about the other part. We call this other part the for the recurrence relation. We are interested in finding the roots of the characteristic equation, which are called (surprise) the .
Given a recurrence relation \(a_n + \alpha a_ + \beta a_ = 0\text\) the is
\begin x^2 + \alpha x + \beta \end
\begin x^2 + \alpha x + \beta = 0. \end
If \(r_1\) and \(r_2\) are two distinct roots of the characteristic polynomial (i.e, solutions to the characteristic equation), then the solution to the recurrence relation is
\begin a_n = ar_1^n + br_2^n, \end
where \(a\) and \(b\) are constants determined by the initial conditions.
Solve the recurrence relation \(a_n = 7a_ - 10 a_\) with \(a_0 = 2\) and \(a_1 = 3\text<.>\)
Solution
Rewrite the recurrence relation \(a_n - 7a_ + 10a_ = 0\text<.>\) Now form the characteristic equation:
\begin x^2 - 7x + 10 = 0 \end
and solve for \(x\text\)
\begin (x - 2) (x - 5) = 0 \end
so \(x = 2\) and \(x = 5\) are the characteristic roots. We therefore know that the solution to the recurrence relation will have the form
\begin a_n = a 2^n + b 5^n. \end
To find \(a\) and \(b\text\) plug in \(n =0\) and \(n = 1\) to get a system of two equations with two unknowns:
\begin 2 \amp = a 2^0 + b 5^0 = a + b\\ 3 \amp = a 2^1 + b 5^1 = 2a + 5b \end
Solving this system gives \(a = \frac\) and \(b = -\frac\) so the solution to the recurrence relation is
Perhaps the most famous recurrence relation is \(F_n = F_ + F_\text\) which together with the initial conditions \(F_0 = 0\) and \(F_1= 1\) defines the Fibonacci sequence. But notice that this is precisely the type of recurrence relation on which we can use the characteristic root technique. When you do, the only thing that changes is that the characteristic equation does not factor, so you need to use the quadratic formula to find the characteristic roots. In fact, doing so gives the third most famous irrational number, \(\varphi\text\) the .
Before leaving the characteristic root technique, we should think about what might happen when you solve the characteristic equation. We have an example above in which the characteristic polynomial has two distinct roots. These roots can be integers, or perhaps irrational numbers (requiring the quadratic formula to find them). In these cases, we know what the solution to the recurrence relation looks like.
However, it is possible for the characteristic polynomial to only have one root. This can happen if the characteristic polynomial factors as \((x - r)^2\text<.>\) It is still the case that \(r^n\) would be a solution to the recurrence relation, but we won't be able to find solutions for all initial conditions using the general form \(a_n = ar_1^n + br_2^n\text\) since we can't distinguish between \(r_1^n\) and \(r_2^n\text<.>\) We are in luck though:
Characteristic Root Technique for Repeated Roots
Suppose the recurrence relation \(a_n = \alpha a_ + \beta a_\) has a characteristic polynomial with only one root \(r\text<.>\) Then the solution to the recurrence relation is
\begin a_n = ar^n + bnr^n \end
where \(a\) and \(b\) are constants determined by the initial conditions.
Notice the extra \(n\) in \(bnr^n\text<.>\) This allows us to solve for the constants \(a\) and \(b\) from the initial conditions.
Solve the recurrence relation \(a_n = 6a_ - 9a_\) with initial conditions \(a_0 = 1\) and \(a_1 = 4\text<.>\)
AnswerThe characteristic polynomial is \(x^2 - 6x + 9\text<.>\) We solve the characteristic equation
\begin x^2 - 6x + 9 = 0 \end
so \(x =3\) is the only characteristic root. Therefore we know that the solution to the recurrence relation has the form
\begin a_n = a 3^n + bn3^n \end
for some constants \(a\) and \(b\text<.>\) Now use the initial conditions:
\begin a_0 = 1 \amp = a 3^0 + b\cdot 0 \cdot 3^0 = a\\ a_1 = 4 \amp = a\cdot 3 + b\cdot 1 \cdot3 = 3a + 3b. \end
Since \(a = 1\text\) we find that \(b = \frac\text<.>\) Therefore the solution to the recurrence relation is
\begin a_n = 3^n + \fracn3^n. \end
Although we will not consider examples more complicated than these, this characteristic root technique can be applied to much more complicated recurrence relations. For example, \(a_n = 2a_ + a_ - 3a_\) has characteristic polynomial \(x^3 - 2 x^2 - x + 3\text<.>\) Assuming you see how to factor such a degree 3 (or more) polynomial you can easily find the characteristic roots and as such solve the recurrence relation (the solution would look like \(a_n = ar_1^n + br_2^n + cr_3^n\) if there were 3 distinct roots). It is also possible to solve recurrence relations of the form \(a_n = \alpha a_ + \beta a_ + C\) for some constant \(C\text<.>\) It is also possible (and acceptable) for the characteristic roots to be complex numbers.
This page titled 2.4: Solving Recurrence Relations is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Oscar Levin.
