Exponential Sequences

Section Preview

Investigation

You have a large collection of \(1\times 1\) squares and \(1\times 2\) dominoes. You want to arrange these to make a \(1 \times 15\) strip. How many ways can you do this?

What if the squares come in three different colors and the dominos come in four different colors? And why is this second question easier than the first?

In we saw that if a sequence has some sequence of differences that is constant, then the sequence has a polynomial closed formula. Are there sequences that never have constant differences? And what would their closed formulas look like?

Consider the Fibonacci sequence: \[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots\]. If we look at the first differences, we get this sequence: \[1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots\], which is the Fibonacci sequence itself. This is not surprising, since the Fibonacci sequence is defined by the recurrence relation \(F_n = F_{n-1} + F_{n-2}\). That is saying precisely that to get the next turn of the sequence, we take the current term and add... a term in the sequence!

Of course, if we take another difference, we will get the same sequence back, and again and again, so no \(n\)th differences will be constant.

Another sequence that has this behavior is the powers of 2: \[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, \ldots\] which has differences \[1, 2, 4, 8, 16, 32, 64, 128, 256, \ldots\]. We can also see this from the recurrence relation, since \[a_n = 2a_{n-1} = a_{n-1} + a_{n-1}\]. The rate of growth for this, and in fact any geometric sequence, is the sequence itself.

If you have studied calculus, you may recall that the functions that have themselves (or close) as their rate of change (derivative, in the calculus context) are exactly the exponential functions. Here too, geometric sequences, which have exponential closed formulas, have themselves as their rate of change.

In this section, we will explore sequences that are changing at a rate proportional to the sequence itself, and see how these all have an exponential closed formula, or some variation of that.

Summing Geometric Sequences: Multiply, Shift, and Subtract

Suppose a candy machine dispenses candy in a geometric sequence by first giving 1 candy, then 2 candies, then 4, then 8, and so on. How many candies will you have received in total after 10 turns of the machine?

We can create the sequence of partials sum as \(1, 1+2, 1+2+4, 1+2+4+8, \ldots\) that gives \[1, 3, 7, 15, 31, 63, \ldots\] This is not a geometric sequence, but is almost. In fact, if we add 1 to each term, we get what sure looks like the geometric sequence \(2, 4, 8, 16, 32, 64,\ldots\), so we might guess that the closed formula for the sequence of sums is \(2^{n+1} - 1\). If this is correct, then the answer to the candy question would be \(2^{11} - 1 = 2047\).

More intriguing though is the observation that the sequence of partial sums of a geometric sequence is again geometric-ish. Let's consider how to find the sum of a geometric sequence in general.

We cannot just reverse and add as we did for the sum of an arithmetic sequence. 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

What is \(3 + 6 + 12 + 24 + \cdots + 12288\)?

Solution

Multiply each term by 2, the common ratio. We get \(2S = 6 + 12 + 24 + \cdots + 24576\). Now subtract: \(2S - S = -3 + 24576 = 24573\). Since \(2S - S = S\), we have our answer.

To better see what happened in the above example, we can write 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\). 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 the new last term.

Example

Find a closed formula for \(S(n) = 2 + 10 + 50 + \cdots + 2\cdot 5^n\).

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.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

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}\). In other words, we want to find a function of \(n\) which satisfies \(a_n - a_{n-1} - 6a_{n-2} = 0\). Think about how we build up this sequence iteratively. \[\begin{aligned}a_2 \amp = a_1 + 6a_0 \\ a_3 \amp = a_2 + 6a_1 = a_1 + 6a_0 + 6a_1 \\ a_4 \amp = a_3 + 6a_2 = a_1 + 6a_0 + 6a_1 + 6^2a_0 +6a_1\end{aligned}\] Let's stop there and agree this is getting very complicated. However, we do notice that 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\).

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 \[r^n - r^{n-1} - 6r^{n-2} = 0\].

Now solve for \(r\): \[r^{n-2}(r^2 - r - 6) = 0\], so by factoring, \(r = -2\) or \(r = 3\) (or \(r = 0\), 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\). Which one is correct? They both are, unless we specify initial conditions. Notice we could also have \(a_n = (-2)^n + 3^n\). Or \(a_n = 7(-2)^n + 4\cdot 3^n\). In fact, for any \(a\) and \(b\), \(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\), 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.

Suppose the recurrence relation \(a_n = \alpha a_{n-1} + \beta a_{n-2}\) has a characteristic polynomial with only one root \(r\). Then the solution to the recurrence relation is \[a_n = ar^n + bnr^n\] where \(a\) and \(b\) are constants determined by the initial conditions.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Practice (13)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

1. Which of the following recurrence relations would be good candidates to try the characteristic root technique on? Select all that apply

2. At what step do you need to refer to the initial conditions when completing the characteristic root technique? What would happen if you didn't use these? Explain.

3. What questions do you have? Write at least one question about the content of this section that you or a classmate might be curious about.

4. Find the next two terms in \((a_n)_{n\ge 0}\) beginning \(3, 5, 11, 21, 43, 85\ldots\). Then give a recursive definition for the sequence. Finally, use the characteristic root technique to find a closed formula for the sequence.

   Die Antwort aufzeigen

   171 and 341. \(a_n = a_{n-1} + 2a_{n-2}\) with \(a_0 = 3\) and \(a_1 = 5\). Closed formula: \(a_n = \frac{8}{3}2^n + \frac{1}{3}(-1)^n\). To find this solve the characteristic equation, \(x^2 - x - 2 = 0\), to get characteristic roots \(x = 2\) and \(x=-1\). Then solve the system \[\begin{aligned}3 \amp = a + b \\ 5 \amp = 2a - b\end{aligned}\]

5. Consider the sequences \(2, 5, 12, 29, 70, 169, 408,\ldots\) (with \(a_0 = 2\)).

   1. Describe the rate of growth of this sequence.

   2. Find a recursive definition for the sequence.

   3. Find a closed formula for the sequence.

   4. If you look at the sequence of differences between terms, and then the sequence of second differences, the sequence of third differences, and so on, will you ever get a constant sequence? Explain how you know.

6. Show that \(4^n\) is a solution to the recurrence relation \(a_n = 3a_{n-1} + 4a_{n-2}\).

   Die Antwort aufzeigen

   We claim \(a_n = 4^n\) works. Plug it in: \(4^n = 3(4^{n-1}) + 4(4^{n-2})\). This works; just simplify the right-hand side.

7. Suppose that \(r^n\) and \(q^n\) are both solutions to a recurrence relation of the form \(a_n = \alpha a_{n-1} + \beta a_{n-2}\). Prove that \(c\cdot r^n + d \cdot q^n\) is also a solution to the recurrence relation, for any constants \(c, d\).

8. Think back to the magical candy machine at your neighborhood grocery store. Suppose that the first time a quarter is put into the machine 1 Skittle comes out. The second time, 4 Skittles, the third time 16 Skittles, the fourth time 64 Skittles, etc.

   1. Find both a recursive and closed formula for how many Skittles the nth customer gets.

   2. Check your solution for the closed formula by solving the recurrence relation using the characteristic root technique.

9. Let \(a_n\) be the number of \(1 \times n\) tile designs you can make using \(1 \times 1\) squares available in 4 colors and \(1 \times 2\) dominoes available in 5 colors.

   1. First, find a recurrence relation to describe the problem. Explain why the recurrence relation is correct (in the context of the problem).

   2. Write out the first 6 terms of the sequence \(a_1, a_2, \ldots\).

   3. Solve the recurrence relation. That is, find a closed formula for \(a_n\).

   Die Antwort aufzeigen

   1. \(a_n = 4a_{n-1} + 5a_{n-2}\).

   2. 4, 21, 104, 521, 2604, 13021

   3. \(a_n = \frac{5}{6} 5^n + \frac{1}{6}(-1)^n\).

10. You have access to \(1 \times 1\) tiles which come in 2 different colors and \(1\times 2\) tiles which come in 3 different colors. We want to figure out how many different \(1 \times n\) path designs we can make out of these tiles.

    1. Find a recursive definition for the sequence \(a_n\) of paths of length \(n\).

    2. Solve the recurrence relation using the characteristic root technique.

11. Solve the recurrence relation \(a_n = 2a_{n-1} - a_{n-2}\).

    1. What is the solution if the initial terms are \(a_0 = 1\) and \(a_1 = 2\)?

    2. What do the initial terms need to be in order for \(a_9 = 30\)?

    3. For which \(x\) are there initial terms which make \(a_9 = x\)?

    Die Antwort aufzeigen

    We have characteristic polynomial \(x^2 - 2x + 1\), which has \(x = 1\) as the only repeated root. Thus, using the characteristic root technique for repeated roots, the general solution is \(a_n = a + bn\) where \(a\) and \(b\) depend on the initial conditions.

    1. \(a_n = 1 + n\)

    2. For example, we could have \(a_0 = 21\) and \(a_1 = 22\).

    3. For every \(x\). Take \(a_0 = x-9\) and \(a_1 = x-8\).

12. Consider the recurrence relation \(a_n = 4a_{n-1} - 4a_{n-2}\).

    1. Find the general solution to the recurrence relation (beware the repeated root).

    2. Find the solution when \(a_0 = 1\) and \(a_1 = 2\).

    3. Find the solution when \(a_0 = 1\) and \(a_1 = 8\).

13. Here is a surprising use of sequences to answer a counting question: How many license plates consist of 6 symbols, using only the three numerals 1, 2, and 3 and the four letters a, b, c, and d, so that no numeral appears after any letter? For example, 31ddac, 123321, and ababab are each acceptable license plates, but 13ba2c is not.

    1. First answer this question by considering different cases: how many of the license plates contain no numerals? How many contain one numeral, etc.

    2. Now use the techniques of this section to show why the answer is \(4^7 - 3^7\).

Symbols used here

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

n!

factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.

\binom{n}{k}

binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).

\sum_{k=1}^{n} a_k

summation
Add a_k for k = 1 up to n.

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

A \cup B,\ A \cap B,\ A \setminus B

union, intersection, difference
In either; in both; in A but not B.

\emptyset,\ |A|

empty set, cardinality
The set with no elements; the number of elements of A.

\forall,\ \exists

for all, there exists
Quantifiers: every x; at least one x.

\neg,\ \wedge,\ \vee,\ \Rightarrow,\ \Leftrightarrow

not, and, or, implies, iff
Logical connectives.

\blacksquare\ \text{or}\ \square

end of proof (halmos)
Marks the point where the statement has been established.

a \equiv b \pmod n

congruent modulo n
n divides a − b; a and b have the same remainder.

O(n^2),\ \Theta,\ \Omega

big-O notation
Grows no faster than n² (up to a constant), for large n.

a \bmod n

remainder
What is left after dividing a by n.

How to: Exponential Sequences

1. Identify a sequence as exponential based on its recurrence relation.
2. Apply the characteristic root technique to solve appropriate recurrence relations.

Questions people ask

What makes mathematics "discrete"?

It deals with separate, countable objects — integers, graphs, statements — rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.

How does a proof by induction work?

Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.

Versuch es selbst.

⌨ Type ✎ Draw

Dein Matheproblem

Lösen

x²√÷×π( )=∫d/dxlim[ ]sinlogeˣ

Parts of this page are adapted from Levin, Discrete Mathematics: An Open Introduction (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Mehr in Discrete Math & Logic

Truth tablesSums and inductionProof by inductionAlgorithms and growth of functions