Rate of Growth

Our goal is to find closed formulas for sequences. Our primary strategy will be to first determine how the sequence is changing from term to term. This will lead to a recurrence relation for the sequence, and from that recurrence relation, we will find a closed formula. We start with two types of sequences that are particularly common and useful: arithmetic and geometric sequences. Along the way, we will explore some techniques for solving recurrence relations.

Suppose you start a business selling prints of mathematical art. In week zero, you sell two prints. Each week after that, you sell four more prints than you did the previous week. How many prints will you sell in the \(n\)th week?

We can easily compute the first few terms of the sequence: \(2, 6, 10, 14,\ldots\). How do I know this is correct? From the problem, we see that to get from one term to the next, we must add 4. It is clear then that the recurrence relation for the sequence is \[a_n = a_{n-1} + 4\]. The rate of growth for the sequence is the constant \(4\) since the difference between any two terms is 4 (note, we could write the recurrence relation as \(a_n - a_{n-1} = 4\)).

We call sequences with a constant rate of change arithmetic sequences.

Now let's find a closed formula for our sequence. The first term is \(a_0 = 2\). To get \(a_1\), we add \(4\). The next term requires us to add \(4\) again, which means we have added \(4\) to our initial term twice. Then we add \(4\) again, for a total of three times for \(a_3\). In fact, to get \(a_n\), we will have added \(4\) to \(a_0\) a total of \(n\) times. Thus, the closed formula for the sequence is \[a_n = 2 + 4n\].

This works for any arithmetic sequence. That is, any sequence with a constant difference will have a linear closed formula, where the slope of the linear function is the common difference.

If the terms of a sequence differ by a constant, we say the sequence is arithmetic. If the initial term (\(a_0\)) of the sequence is \(a\) and the common difference is \(d\), then we have,

Recursive definition: \(a_n = a_{n-1} + d\) with \(a_0 = a\).

Closed formula: \(a_n = a + dn\).

As we did for our example above, for the recursive definition, we need to specify \(a_0\). Then we need to express \(a_n\) in terms of \(a_{n-1}\). If we call the first term \(a\), then \(a_0 = a\). For the recurrence relation, by the definition of an arithmetic sequence, the difference between successive terms is some constant, say \(d\). So \(a_n - a_{n-1} = d\), or in other words, \[a_0 = a \qquad a_n = a_{n-1} + d\].

Let's now argue why the closed formula is correct. One way we could do this is by using a technique sometimes called telescoping (a name which hopefully we become meaningful momentarily).

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

What about sequences like \(3, 6, 12, 24, 48, \ldots\)? This is not arithmetic because the difference between terms is not constant. However, the ratio between successive terms is constant: \(\frac{6}{3} = \frac{12}{6} = \frac{24}{12} = \cdots = 2\) We call such sequences geometric.

Recognizing that the sequence is geometric lets us easily write down a recursive definition. \(a_n = 2 a_{n-1}\), with \(a_0 = 3\).

A closed formula is also not difficult to reason out. How do we get the term \(a_3\) for example? We start with \(3\), then multiply by 2 to get \(a_1\), multiply by \(2\) again to get \(a_2\), and multiply by \(2\) a third time to get \(a_3\). So we multiplied \(3\) by \(2\) a total of three times, or \(a_3 = 3\cdot 2^3\). It looks like \(a_n = 3\cdot 2^n\).

In general, the recursive definition for the geometric sequence with initial term \(a\) and common ratio \(r\) will be \[a_n = a_{n-1}\cdot r; a_0 = a\]. To get the next term we multiply the previous term by \(r\).

For the general closed formula, we could try something like telescoping again, although we would need to cancel fractions. Instead, let's illustrate another technique for solving recurrence relations called iteration. The idea here is that we work our way up to \(a_n\) and notice the pattern. Write \[\begin{aligned}a_0 \amp = a \\ a_1 \amp = a_0\cdot r \\ a_2 \amp = a_1 \cdot r = a_0\cdot r\cdot r = a_0\cdot r^2 \\ a_3 \amp = a_2 \cdot r = a_0 \cdot r^2 \cdot r = a_0 \cdot r^3 \\ \amp \vdots \\ a_n \amp = a_{n-1} \cdot r = a_0 \cdot r^{n-1}\cdot r = a_0 r^n\end{aligned}\]. We must multiply the first term \(a\) by \(r\) a number of times, \(n\) times to be precise. We get \(a_n = a\cdot r^{n}\).

A sequence is called geometric if the ratio between successive terms is constant. Suppose the initial term \(a_0\) is \(a\) and the common ratio is \(r\). Then we have,

Recursive definition: \(a_n = ra_{n-1}\) with \(a_0 = a\).

Closed formula: \(a_n = a\cdot r^{n}\).

Geometric sequences are those which have a growth rate that is proportional to the sequence itself. Just like you might have seen in calculus, it is exactly the exponential functions that have this property.

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

Look at the sequence \((T_n)_{n\ge 1}\) which starts \(1, 3, 6, 10, 15,\ldots\). These are called the triangular numbers since they represent the number of dots in an equilateral triangle (think of how you arrange 10 bowling pins: a row of 4 plus a row of 3 plus a row of 2 and a row of 1).

Is this sequence arithmetic? No, since \(3-1 = 2\) and \(6-3 = 3 \ne 2\), so there is no common difference. Is the sequence geometric? No. \(3/1 = 3\) but \(6/3 = 2\), so there is no common ratio. What to do?

Notice that the differences between terms do form an arithmetic sequence: \(2, 3, 4, 5, 6,\ldots\). In other words, the rate of change of this sequence is arithmetic: \(T_n - T_{n-1} = n\), which immediately gives us the recurrence relation \(T_n = T_{n-1} + n\).

Another way to think of this is that the \(n\)th term of the sequence \((T_n)\) is the sum of the first \(n\) terms in the sequence \(1,2,3,4,5,\ldots\). Thus \((T_n)\) is the sequence of partial sums of the sequence \(1,2,3,\ldots\) (partial sums because we are not taking the sum of all infinitely many terms).

This should become clearer if we expand the recurrence relation to write the triangular numbers like this: \[\begin{aligned}T_1 = 1 \amp = 1 \\ T_2 = 3 \amp = 1+2 \\ T_3 = 6 \amp = 1 + 2 + 3 \\ T_4 = 10 \amp = 1+ 2 + 3+ 4 \\ \vdots \amp \qquad \vdots \\ T_n \amp = 1 + 2 + 3 + \cdots + n\end{aligned}\]. We are really using iteration here. We could also have seen this by using telescoping, taking \(T_0 = 0\): \[\begin{aligned}T_1-T_0 = \amp 1 \\ T_2 - T_1 = \amp 2 \\ T_3 - T_2 = \amp 3 \\ \vdots \amp \\ T_n - T_{n-1} = \amp n\end{aligned}\]. Summing these equations, the right-hand side becomes \(1+2+3+\cdots + n\); the left-hand side cancels to leave just \(T_n - T_0 = T_n\).

If we know how to add up the terms of an arithmetic sequence, we can find a closed formula for a sequence whose differences are the terms of that arithmetic sequence. Consider how we could find the sum of the first 100 positive integers (that is, \(T_{100}\)). Instead of adding them in order, we regroup and add \(1+100 = 101\). The next pair to combine is \(2+99 = 101\). Then \(3+98 = 101\). Keep going. This gives 50 pairs which each add up to \(101\), so \(T_{100} = 101\cdot 50 = 5050\). This insight is usually attributed to Carl Friedrich Gauss, one of the greatest mathematicians of all time, who discovered it as a child when his unpleasant elementary teacher thought he would keep the class busy by requiring them to compute the lengthy sum.

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