Skip to main content

Section 13.1 Introduction to Discrete Calculus

Subsection 13.1.1 Overview

Calculus studies functions through their rates of change. Our goal is to understand relationships between concepts and not just rules of computation. The better we understand, the easier time we will have in drawing upon those concepts to answer questions. If we can use simpler concepts that can motivate the ideas of calculus, then those ideas will make more sense. Sequences provide one possible framework through which we can motivate the ideas of calculus.

In this section, we introduce the ideas that will be explored throughout the chapter. We learn to describe the behavior of sequences in terms of monotonicity and concavity in terms of increments of change. The ideas of monotonicity will allow us to answer questions relating to extreme values. We then outline how the rest of the chapter will proceed.

Subsection 13.1.2 Behavior of Sequences

One of the results of calculus is the ability to describe the behavior of functions. We begin our discussion of the analysis of sequences with this in mind. We motivate the discussion on the behavior of sequences with some graphs.

(a) increasing, concave up
(b) increasing, concave down
(c) decreasing, concave up
(d) decreasing, concave down
Figure 13.1.1. Graphs of four short subsequences that illustrate the concepts of monotonicity and concavity.

In mathematics, monotonicity refers to the direction of change in a sequence or function. In the figure above, the two sequences that are increasing show that the values of the sequence are rising. The sequences that are decreasing have values that fall. Concavity in the graphs corresponds to how the sequence appears to be bending. Imagine the sequences as points on a bowl shape. If the curve is bending up, the sequence is concave up. If the curve is bending down, the sequence is concave down. A sequence can change behavior multiple times, as shown in the figure below. We seek for methods of analyzing a sequence that will allow us to describe the monotonicity and concavity of a sequence.

Figure 13.1.2. An example of a sequence that illustrates all four basic behaviors.

Subsection 13.1.3 Monotonicity: Increasing and Decreasing

Our goal is to establish a way to describe these behaviors without relying solely on graphs. We begin by focusing on monotonicity.

Definition 13.1.3. Monotonicity of Sequences.

For a sequence \(x\) with index \(k\text{,}\) we say that \(x\) is increasing on the interval \(\{m,\ldots,n\}\) if for every two values in the interval, \(i,j \in \{m,\ldots,n\}\) with \(i \lt j\text{,}\) we have \(x_j \gt x_i\text{.}\) That is, values later in the sequence are always greater than values earlier in the sequence.

We say that \(x\) is decreasing on the interval \(\{m,\ldots,n\}\) if for every two values in the interval, \(i,j \in \{m,\ldots,n\}\) with \(i \lt j\text{,}\) we have \(x_j \lt x_i\text{.}\) That is, values later in the sequence are always less than values earlier in the sequence.

Our definition of monotonicity is on an interval of integers for the index. We talk about increasing and decreasing on intervals for several reasons. First, monotonicity is about comparisons of values. We should not think that the sequence is increasing or decreasing at a particular point. Instead, we are looking at how the sequence changes going from one index value to another. Second, when we later discuss the monotonicity of functions, we will describe monotonicity in terms of intervals from the domain. Consequently, we want to establish that pattern of thinking now.

Inequalities are transitive. That is, if \(a \lt b\) and \(b \lt c\text{,}\) then we know \(a \lt c\text{.}\) For sequences, this means that we don't really need to look at all possible pairs of index values in the interval. We only need to look at the consecutive terms in the sequence and see if they are increasing or decreasing.

Example 13.1.4.

Consider the finite sequence

\begin{equation*} x = (x_k)_{k=0}^{9} = (-5,-8,-9,-8,-5,0,7,4,2,1)\text{.} \end{equation*}

Describe the monotonicity of \(x\text{.}\)

Solution

We look at whether the sequence values are moving to the left or to the right on the number line. You could probably just visualize it in your mind, but a number line showing the values is illustrated below.

We can see that \(x\) is decreasing on the index interval \(\{0, 1, 2\}\) because the values of the sequence move left on the number line:

\begin{equation*} x_1 \lt x_0, \quad x_2 \lt x_1\text{.} \end{equation*}

Next, we see that \(x\) is increasing on the interval \(\{2,\ldots,6\}\) as the sequence moves to the right:

\begin{equation*} x_3 \gt x_2, \quad x_4 \gt x_3, \quad \ldots \quad x_6 \gt x_5\text{.} \end{equation*}

Finally, \(x\) is decreasing on the interval \(\{6,\ldots,9\}\text{:}\)

\begin{equation*} x_7 \lt x_6, \quad x_8 \lt x_7, \quad x_9 \gt x_8\text{.} \end{equation*}

We compare this analysis with a graph of the sequence, shown below. When the sequence is decreasing, the graph shows points of lowering heights. When the sequence is increasing, the graph shows points of rising heights.

When analyzing a sequence to determine monotonicity, we focus on inequalities involving consecutive terms. If we use \(k=n-1\) and \(k=n\) to represent consecutive index values, then the inequalities are:

  • \(x_{n} \gt x_{n-1}\) for increasing
  • \(x_{n} \lt x_{n-1}\) for decreasing.

By moving all terms to one side, the inequalities become:

  • \(x_{n}-x_{n-1} \gt 0\) for increasing
  • \(x_{n}-x_{n-1} \lt 0\) for decreasing.

This means that monotonicity can be determined by looking at the signs of the differences between terms. We call those differences the increments.

Definition 13.1.5.

Given a sequence \(x = (x_k)_{k=m}^{n}\text{,}\) the increments form a new sequence, \(\nabla x = (\nabla x_k)_{k=m+1}^{n}\text{,}\) calculated by the backward difference,

\begin{equation*} \nabla x_k = x_{k} - x_{k-1}\text{.} \end{equation*}

When computing the increments, we had to make a choice whether to do the backward difference or the forward difference,

\begin{equation*} \Delta x_k = x_{k+1} - x_k\text{.} \end{equation*}

The values of the backward differences and the forward differences are exactly the same. They differ only in terms of index values. I have chosen to use backward differences in order for our later work with accumulation sequences and summation to work out more cleanly.

Example 13.1.6.

For the sequence \(x = (x_k)_{k=3}^{10} = (1,2,4,7,11,16,22,29)\text{,}\) find the increments defined by the backward difference.

Solution

We can find the values by writing the sequence as a row of values. Then below the gaps between the values, we can write the differences.

When the increments are defined by the backward difference, the index starts one value later than the original sequence. Thus, the increments are the sequence

\begin{equation*} \nabla x = (\nabla x_k)_{k=4}^{10} = (1, 2, 3, 4, 5, 6, 7)\text{.} \end{equation*}

Because all of the increments are positive, \(x\) is increasing on the full interval \(\{3,\ldots,10\}\text{.}\)

We can therefore analyze monotonicity of a sequence if we know the signs of its increments.

Subsection 13.1.4 Concavity

We now turn our attention to the concavity of a sequence. Concavity is based on whether the sequence of increments is increasing or decreasing. When the increments are constant, we have an arithmetic sequence which follows a straight line. To be concave up, we need the graph to bend up. If an increment is positive, then the next increment needs to be a larger positive value. If an increment is negative, then the next increment needs to be a smaller magnitude negative value or a positive value. Either way, we need the increments to increase:

\begin{equation*} \nabla x_n \gt \nabla x_{n-1}\text{.} \end{equation*}

Similarly, for a sequence to be concave down, the increments need to decrease:

\begin{equation*} \nabla x_n \lt \nabla x_{n-1}\text{.} \end{equation*}
Definition 13.1.8. Concavity of a Sequence.

Suppose \(x\) is a sequence with increments \(\nabla x_k\) and \(m\) and \(n\) are index values with \(m \lt n\text{.}\)

  • If the increment sequence \(\nabla x\) is increasing on \(\{m,\ldots,n\}\text{,}\) then the sequence \(x\) is concave up on \(\{m-1,\ldots,n\}\text{.}\)
  • If the increment sequence \(\nabla x\) is decreasing on \(\{m,\ldots,n\}\text{,}\) then the sequence \(x\) is concave down on \(\{m-1,\ldots,n\}\text{.}\)
  • If the increment sequence \(\nabla x\) is constant on \(\{m,\ldots,n\}\text{,}\) then the sequence \(x\) has no concavity and is linear (i.e., straight) on \(\{m-1,\ldots,n\}\text{.}\)

Because the increments themselves form a sequence, we can look at the signs of the increments of the increments to analyze concavity. Computing the backward difference of a backward difference is called the second backward difference.

Definition 13.1.9.

Suppose \(x\) is a sequence with increments \(\nabla x_k\text{.}\) The second backward difference of \(x\text{,}\) written \(\nabla^2 x_k\text{,}\) measures the backward difference of the increments,

\begin{equation*} \nabla^2 x_k = \nabla(\nabla x_k) = \nabla x_k - \nabla x_{k-1}\text{.} \end{equation*}

The first index of \(\nabla^2 x_k\) is two greater than the first index of \(x\text{.}\) (A second forward difference \(\delta^2 x\) is defined similarly but will not be used.)

Having defined the second backward difference, we can state the test that allows us to analyze the concavity of a sequence.

Example 13.1.11.

The values for the subsequence shown in Figure 13.1.2 are shown in the table below, rounded to the nearest ten-thousandth. Determine the intervals of monotonicity and concavity.

\(n\) \(u_n\)
0 6
1 3.5376
2 2.3136
3 2.0016
4 2.3136
5 3
6 3.8496
7 4.6896
8 5.3856
9 5.8416
10 6
\(n\) \(u_n\)
11 5.8416
12 5.3856
13 4.6896
14 3.8496
15 3
16 2.3136
17 2.0016
18 2.3136
19 3.5376
20 6
Solution

We can augment the table with additional columns for the first and second backward differences. Then we can look at the signs of those increments to determine intervals for monotonicity and concavity. With as many terms as we are working with, we would definitely want to use a computer to assist here.

\(n\) \(u_n\) \(\nabla u_n\) \(\nabla^2 u_n\)
0 6
1 3.5376 -2.4624
2 2.3136 -1.224 1.2384
3 2.0016 -0.312 0.912
4 2.3136 0.312 0.624
5 3 0.6864 0.3744
6 3.8496 0.8496 0.1632
7 4.6896 0.84 -0.0096
8 5.3856 0.696 -0.144
9 5.8416 0.456 -0.24
10 6 0.1584 -0.2976
\(n\) \(u_n\) \(\nabla u_n\) \(\nabla^2 u_n\)
11 5.8416 -0.1584 -0.3168
12 5.3856 -0.456 -0.2976
13 4.6896 -0.696 -0.24
14 3.8496 -0.84 -0.144
15 3 -0.8496 -0.0096
16 2.3136 -0.6864 0.1632
17 2.0016 -0.312 0.3744
18 2.3136 0.312 0.624
19 3.5376 1.224 0.912
20 6 2.4624 1.2384

We begin by looking at the signs of the increments based on the first backward difference. Again, it is more compact to use a table to summarize our results.

Sign of \(\nabla u_n\) Interval Behavior of \(u_n\) Interval
negative \(\{1,2,3\}\) decreasing \(\{0,\ldots,3\}\)
positive \(\{4,\ldots,10\}\) increasing \(\{3,\ldots,10\}\)
negative \(\{11,\ldots,17\}\) decreasing \(\{10,\ldots,17\}\)
positive \(\{18,19,20\}\) increasing \(\{17,\ldots,20\}\)

We perform a similar analysis on the second backward differences to describe the concavity of the sequence.

Sign of \(\nabla^2 u_n\) Interval Behavior of \(u_n\) Interval
positive \(\{2,\ldots,6\}\) concave up \(\{0,\ldots,6\}\)
negative \(\{7,\ldots,15\}\) concave down \(\{5,\ldots,15\}\)
positive \(\{16,\ldots,20\}\) concave up \(\{14,\ldots,20\}\)

When doing this analysis, if you discover that an increment equals zero, remember that is neither positive nor negative. Do not include the index in the interval for the signs of increments. An increment of zero indicates that the sequence was not changing. If the second difference is zero, this indicates the increments are not changing and the sequence is linear.

Subsection 13.1.5 Extreme Values

Having discussed monotonicity, we turn our attention to the extreme values of a sequence. An extreme value refers to a maximum or minimum value in the sequence. Of course, when we have a list of the sequence values, we can scan through the list of values to find the highest or lowest value. We want some methods of analysis that will not require checking all of the values.

On an interval where a sequence is monotone, an extreme value will never occur within that interval. Extreme values can only occur at the edge of such an interval. To find a maximum value, we look for where a sequence transitions from increasing to decreasing. To find a minimum value, we look for where it transitions from decreasing to increasing. These turning points identify local extreme values.

Definition 13.1.12. Local Extreme Values for Sequences.

A sequence \(x\) has a local maximum at index value \(k\) if there are index values \(m \lt k \lt n\) so that

\begin{equation*} x_k \ge x_i, \end{equation*}

for all \(i \in \{m,\ldots,n\}\text{.}\)

A sequence \(x\) has a local minimum at index value \(k\) if there are index values \(m \lt k \lt n\) so that

\begin{equation*} x_k \le x_i, \end{equation*}

for all \(i \in \{m,\ldots,n\}\text{.}\)

A sequence can have multiple local extremes. The example shown in Figure 13.1.2 has two local minima and one local maximum. The two minima happen to have the same value. However, even if one was higher than the other, they would both still be minima because they would be where the sequence transitioned from decreasing to increasing.

A global extreme value describes a value in the sequence that is either the largest value of all (the global maximum) or the lowest value of all (the global minimum). To describe the global extreme values, we would compare all of the local extremes as well as check if the sequence increased or decreased without bound. To describe that in more depth, we need to wait until we talk about limits.

Subsection 13.1.6 Patterns in the Increments

Backward differences are not only useful for describing the monotonicity and concavity of a sequence. There are many sequences where patterns in the increments can be used to create non-recursive recurrence relations. A recurrence relation describes how to go from the previous value in a sequence to the next value. It is recursive if the relation is the same for every index. A non-recursive recurrence relation will have a relation that depends on the index. Sometimes, we can still identify a pattern by looking at the higher-order differences.

An arithmetic sequence is a sequence where the backward difference is a constant sequence. More complicated sequences arise where it is not the backward difference but the second difference or higher that is constant. If we can identify a higher-order backward difference that is constant, then we can use that pattern to predict additional terms.

Example 13.1.13.

Consider the sequence \(w = (0,-23,-40,-45,-32,5,72,175,\ldots)\text{.}\) Identify a pattern and find the next two values in the sequence.

Solution

This sequence is not arithmetic, nor is it geometric. To look for a pattern, we proceed to generate the backward differences.

The pattern of backward differences shows that the third-order backward difference is a constant value, \(\nabla^3 w_n = 6\text{.}\) We can use this pattern to find the next few values of the sequence. We do this by extending the table, adding the increments one at a time. The last term in \(\nabla^2 w_n\) shown was \(\nabla^2 w_8 = 36\text{.}\) So the next term will be \(\nabla^2 w_9 = 36 + 6 =42\text{.}\) We can use that to find \(\nabla w_9 = \nabla w_8 + 42 =103 + 42 = 145\text{.}\) That allows us to obtain \(w_9 = w_8 + 145 = 175 + 145 = 320\text{.}\) Repeating the process allows us to find \(w_{10} = 513\text{,}\) as illustrated in the extended table below.

Subsection 13.1.7 Where Do We Go From Here?

In this section, we have introduced the ideas of the characterizing a sequence in terms of monotonicity and concavity. We considered examples of sequences with given values to find the backward differences by hand. In the next section, we will consider how to find an explicit formula for the backward differences when we know an explicit formula for the sequence itself. This will allow us to analyze the monotonicity and concavity of a sequence without needing all of the values being tabulated. Knowing monotonicity will allow us to identify extreme values, again without computing all of the values. The ideas of backward differences are analogous to the concepts of derivatives in calculus.

At the end of this section, we considered an example where we used a pattern in the backward differences to generate additional values for the sequence. In a future section, we will consider the idea of starting with a known sequence at the level of increments and using that sequence to generate a corresponding sequence. We call the generated sequence an accumulation sequence, named this because the new value is an accumulation of increments. An important topic raised in that section is how to show that two sequences are the same. We often have multiple methods of describing a sequence, such as an explicit definition and a recursive definition. We want to know that the sequences really agree because we can't (and wouldn't want to) compute and compare infinitely many values. The ideas of accumulation are analogous to the concepts of integration in calculus.

One of the most important applications of accumulation is summation. Summation formulas will continue to generalize our last example in this section. Where accumulation allows us to take a known sequence of increments and generate the original sequence, summation formulas will allow us to take the formula of an increment sequence and compute an explicit formula for the original sequence. Summation formulas will be critical in generating the explicit formulas of integration later.

Finally, we will end the chapter by introducing limits of sequences. Limits are the key tool that generates all of calculus. A limit in a sequence corresponds to having the values in a sequence converge to some value. We will then be ready to begin a new chapter that begins our look at calculus.

Subsection 13.1.8 Summary

  • Monotonicity of a sequence describes where the sequence is increasing or decreasing. We say that a sequence is increasing or decreasing on intervals of integers. The sequence is increasing if the sequence values move to the right on the number line. The sequence is decreasing if the sequence values move to the left on the number line.

  • We calculate the increments of the sequence using the backward difference to analyze monotonicity,

    \begin{equation*} \nabla x_k = x_k - x_{k-1}\text{.} \end{equation*}
    • If the increments are positive, \(\nabla x_k \gt 0\) for all \(k\) on an interval \(\{m,\ldots,n\}\text{,}\) then the values of the sequence \(x_k\) are increasing on the interval \(\{m-1,\ldots,n\}\text{.}\)
    • If the increments are negative, \(\nabla x_k \lt 0\) for all \(k\) on an interval \(\{m,\ldots,n\}\text{,}\) then the values of the sequence \(x_k\) are decreasing on the interval \(\{m-1,\ldots,n\}\text{.}\)
  • Concavity of a sequence describes where the increments are increasing or decreasing. A sequence whose increments are increasing is concave up. A sequence whose increments are decreasing is concave down.

  • We can analyze concavity by computing the increments of the increments using the second backward difference,

    \begin{equation*} \nabla^2 x_k = \nabla x_k - \nabla x_{k-1}\text{.} \end{equation*}
    • If the second increments are positive, \(\nabla^2 x_k \gt 0\) for all \(k\) on an interval \(\{m,\ldots,n\}\text{,}\) then the values of the sequence \(x_k\) are concave up on the interval \(\{m-2,\ldots,n\}\text{.}\)
    • If the second increments are negative, \(\nabla^2 x_k \lt 0\) for all \(k\) on an interval \(\{m,\ldots,n\}\text{,}\) then the values of the sequence \(x_k\) are concave down on the interval \(\{m-2,\ldots,n\}\text{.}\)
  • We can also use the increments and higher-order increments to find patterns in some sequences. Following these patterns can be used to predict later terms in the sequence with index-dependent recurrence relations.

Exercises 13.1.9 Exercises

For the following finite sequences, find the intervals of monotonicity and concavity. Also, identify the index and values of the local maximum and minimum points. Graph the sequences and compare with your results.

1.

\(a = (a_n)_{n=1}^{10} = (35, 55, 70, 80, 85, 85, 80, 70, 55, 35)\)

2.

\(b = (b_i)_{i=0}^{9} = (-8,-5,-4,-5,-8,-9,-8,-5,-1,4)\)

3.

\(c = (c_t)_{t=-3}^{6} = (5,8,10,10,10,9,8,7,8,10)\)

For the following sequences, identify a pattern using backward differences. Use the pattern to predict the next two values of the sequence.

4.

\(u = (u_k)_{n=0}^{\infty} = (-8,-13,-16,-17,-16,-13,-8,\ldots)\)

5.

\(v = (v_j)_{j=1}^{\infty} = (6,0,-6,-10,-10,-4,10,\ldots)\)

6.

\(w = (w_n)_{n=0}^{\infty} = (-3,-6,-5,1,12,27,44,60,71,\ldots)\)