Subsection Summing Geometric Sequences: Multiply, Shift and Subtract
To find the sum of a geometric sequence, we cannot just reverse and add. Do you see why? The reason we got the same term added to itself many times is because there was a constant difference. So as we added that difference in one direction, we subtracted the difference going the other way, leaving a constant total. For geometric sums, we have a different technique.
Example 4.4.1.
What is \(3 + 6 + 12 + 24 + \cdots + 12288\text{?}\)
Solution.
Multiply each term by 2, the common ratio. You get \(2S = 6 + 12 + 24 + \cdots + 24576\text{.}\) Now subtract: \(2S - S = -3 + 24576 = 24573\text{.}\) Since \(2S - S = S\text{,}\) we have our answer.
To better see what happened in the above example, try writing it this way:
| \(S=\) |
\(3 \, +\) |
\(6 + 12 + 24 + \cdots + 12288\) |
|
| \(- \qquad 2S=\) |
|
\(6 + 12 + 24 + \cdots + 12288\) |
\(+ 24576\) |
| \(-S = \) |
\(3 \, +\) |
\(0 + 0 + 0 + \cdots + 0 \) |
\(-24576\) |
Then divide both sides by \(-1\) and we have the same result for \(S\text{.}\) The idea is, by multiplying the sum by the common ratio, each term becomes the next term. We shift over the sum to get the subtraction to mostly cancel out, leaving just the first term and new last term.
Example 4.4.2.
Find a closed formula for \(S(n) = 2 + 10 + 50 + \cdots + 2\cdot 5^n\text{.}\)
Solution.
The common ratio is 5. So we have
| \(S\) |
\(= 2 + 10 + 50 + \cdots + 2\cdot 5^n\) |
| \(- \qquad 5S\) |
\(= ~~~~~~10 + 50 + \cdots + 2\cdot 5^n + 2\cdot5^{n+1}\) |
| \(-4S\) |
\(= 2 - 2\cdot5^{n+1}\) |
Thus \(S = \dfrac{2-2\cdot 5^{n+1}}{-4}\)
Even though this might seem like a new technique, you have probably used it before.
Example 4.4.3.
Express \(0.464646\ldots\) as a fraction.
Solution.
Let \(N = 0.46464646\ldots\text{.}\) Consider \(0.01N\text{.}\) We get:
| \(N =\) |
\(0.4646464\ldots\) |
| \(- \qquad 0.01N =\) |
\(0.00464646\ldots\) |
| \(0.99N =\) |
\(0.46\) |
So \(N = \frac{46}{99}\text{.}\) What have we done? We viewed the repeating decimal \(0.464646\ldots\) as a sum of the geometric sequence \(0.46, 0.0046, 0.000046, \ldots\) The common ratio is \(0.01\text{.}\) The only real difference is that we are now computing an infinite geometric sum, we do not have the extra “last” term to consider. Really, this is the result of taking a limit as you would in calculus when you compute infinite geometric sums.
To summarize, we now can find a closed formula for a sequence \(a_n\) that has a rate of growth that is an exponential function: \(a_n - a_{n-1} = b_n\text{,}\) where \(b_n\) is a geometric sequence (i.e., and exponential function). What sort of closed formula to we get here? It’s another exponential function!
Subsection The Characteristic Root Technique
Suppose we want to solve a recurrence relation expressed as a combination of the two previous terms, such as \(a_n = a_{n-1} + 6a_{n-2}\text{.}\) In other words, we want to find a function of \(n\) which satisfies \(a_n - a_{n-1} - 6a_{n-2} = 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
\begin{equation*}
r^n - r^{n-1} - 6r^{n-2} = 0\text{.}
\end{equation*}
Now solve for \(r\text{:}\)
\begin{equation*}
r^{n-2}(r^2 - r - 6) = 0\text{,}
\end{equation*}
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^{n-2}\) as we did above. So we really only care about the other part. We call this other part the characteristic equation for the recurrence relation. We are interested in finding the roots of the characteristic equation, which are called (surprise) the characteristic roots.
Characteristic Roots.
Given a recurrence relation \(a_n + \alpha a_{n-1} + \beta a_{n-2} = 0\text{,}\) the characteristic polynomial is
\begin{equation*}
x^2 + \alpha x + \beta
\end{equation*}
giving the characteristic equation:
\begin{equation*}
x^2 + \alpha x + \beta = 0\text{.}
\end{equation*}
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{equation*}
a_n = ar_1^n + br_2^n\text{,}
\end{equation*}
where \(a\) and \(b\) are constants determined by the initial conditions.
Example 4.4.4.
Solve the recurrence relation \(a_n = 7a_{n-1} - 10 a_{n-2}\) with \(a_0 = 2\) and \(a_1 = 3\text{.}\)
Solution.
Rewrite the recurrence relation \(a_n - 7a_{n-1} + 10a_{n-2} = 0\text{.}\) Now form the characteristic equation:
\begin{equation*}
x^2 - 7x + 10 = 0
\end{equation*}
and solve for \(x\text{:}\)
\begin{equation*}
(x - 2) (x - 5) = 0
\end{equation*}
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{equation*}
a_n = a 2^n + b 5^n\text{.}
\end{equation*}
To find \(a\) and \(b\text{,}\) plug in \(n =0\) and \(n = 1\) to get a system of two equations with two unknowns:
\begin{align*}
2 \amp = a 2^0 + b 5^0 = a + b\\
3 \amp = a 2^1 + b 5^1 = 2a + 5b
\end{align*}
Solving this system gives \(a = \frac{7}{3}\) and \(b = -\frac{1}{3}\) so the solution to the recurrence relation is
\begin{equation*}
a_n = \frac{7}{3}2^n - \frac{1}{3} 5^n\text{.}
\end{equation*}
Perhaps the most famous recurrence relation is \(F_n = F_{n-1} + F_{n-2}\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 golden ratio.
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 have only 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_{n-1} + \beta a_{n-2}\) has a characteristic polynomial with only one root \(r\text{.}\) Then the solution to the recurrence relation is
\begin{equation*}
a_n = ar^n + bnr^n
\end{equation*}
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.
Example 4.4.5.
Solve the recurrence relation \(a_n = 6a_{n-1} - 9a_{n-2}\) with initial conditions \(a_0 = 1\) and \(a_1 = 4\text{.}\)
Solution.
The characteristic polynomial is \(x^2 - 6x + 9\text{.}\) We solve the characteristic equation
\begin{equation*}
x^2 - 6x + 9 = 0
\end{equation*}
by factoring:
\begin{equation*}
(x - 3)^2 = 0
\end{equation*}
so \(x =3\) is the only characteristic root. Therefore we know that the solution to the recurrence relation has the form
\begin{equation*}
a_n = a 3^n + bn3^n
\end{equation*}
for some constants \(a\) and \(b\text{.}\) Now use the initial conditions:
\begin{align*}
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\text{.}
\end{align*}
Since \(a = 1\text{,}\) we find that \(b = \frac{1}{3}\text{.}\) Therefore the solution to the recurrence relation is
\begin{equation*}
a_n = 3^n + \frac{1}{3}n3^n\text{.}
\end{equation*}
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_{n-1} + a_{n-2} - 3a_{n-3}\) 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 that the characteristics roots are complex numbers.
However, the characteristic root technique is only useful for solving recurrence relations in a particular form: \(a_n\) is given as a linear combination of some number of previous terms. These recurrence relations are called linear homogeneous recurrence relations with constant coefficients. The “homogeneous” refers to the fact that there is no additional term in the recurrence relation other than a multiple of \(a_j\) terms. For example, \(a_n = 2a_{n-1} + 1\) is non-homogeneous because of the additional constant 1. There are general methods of solving such things, but we will not consider them here, other than through the use of telescoping or iteration described above.
