Skip to main content

Section 13.2 Recursive Sequences and Projection Functions

Overview.

When looking for patterns in sequences, we usually explore two possibilities. One approach is to look at the values of individual terms and see if there is an explicit formula relating the index with the formula. There were several examples of this in the previous section. Another approach is to look for a pattern in how terms are generated from earlier terms. For example, the sequence \((7,10,13,16,\ldots)\) is easy to recognize that each term is found by adding \(3\) to the previous term.

In this section, we consider recursively defined sequences. Arithmetic and geometric sequences are two familiar examples of sequences with recursive definitions. We review some basic ideas about functions. We will learn about projection functions used in such recursive definitions. We visualize the role of projection functions as maps between sequence values and through cobweb diagrams.

Subsection 13.2.1 Arithmetic and Geometric Sequences

We often think of sequences in terms of a pattern for how to find the values. When a sequence can be defined so that the next value can found knowing only the previous value, we say the sequence has a recursive definition. The simplest pattern-based sequences follow simple recursive patterns.

An arithmetic sequence is a sequence whose terms change by a fixed increment or difference. For example, consider the sequence introduced above,

\begin{equation*} x = (7, 10, 13, 16, \ldots). \end{equation*}

The pattern for this sequence was that we add 3 to each term in the sequence to find the next term. The value 3 is called the increment or difference of the sequence. It is called the increment because there is a pattern of adding the same value to values in the sequence:

\begin{gather*} x_2=x_1 + 3 = 7+3,\\ x_3 = x_2 + 3 = 10+3,\\ x_4=x_3+3 = 13+3,\\ \vdots \end{gather*}

It is called the difference because each of those equations can be rewritten as a difference of values:

\begin{gather*} x_2-x_1 = 3,\\ x_3 - x_2 = 3,\\ x_4-x_3=3,\\ \vdots \end{gather*}

A geometric sequence is a sequence whose terms change by a fixed multiple or ratio. An example of a geometric sequence is given by

\begin{equation*} u= (2, 6, 18, 54, \ldots). \end{equation*}

Each term is found by multiplying the previous term by 3, which is the multiple or ratio of the sequence. We call the value 3 the multiple because of the pattern

\begin{gather*} u_2 = 3 u_1 = 3 \cdot 2,\\ u_3 = 3 u_2 = 3 \cdot 6,\\ u_4 = 3 u_3 = 3 \cdot 18,\\ \vdots \end{gather*}

It is call the ratio if we rewrite the equations as a ratio of a value to its previous value

\begin{gather*} \frac{u_2}{u_1} = 3,\\ \frac{u_3}{u_2} = 3,\\ \frac{u_4}{u_3} = 3,\\ \ldots \end{gather*}

For recursively defined sequences, the equation that describes the relationship between consecutive terms of the sequence is called the recurrence relation. When the recurrence relation for a sequence \(x\) is solved for the next value as a dependent variable in terms of an expression involving of the previous term, we call this map or function the projection function because it allows us to project future values based on current values.

Subsection 13.2.2 Functions as Maps

Before we discuss more about projection functions, we take a short diversion to review some core concepts about functions in general. Functions are at the heart of everything we do in calculus. Unfortunately, many students have subtle misconceptions about how to think about functions. We want to use our emphasis on sequences to come to terms with these ideas. Be prepared to think about functions from many different points of view. We begin by thinking of a function as a map between variables.

Definition 13.2.1. Function.

Given two related variables, say \(x\) and \(y\text{,}\) such that there is a rule or relation that defines a map \(x \mapsto y\text{,}\) we say that the map is a function. (We will make this more precise later. 1 The precise definition needs to address the domain of the function and clarify what is a map when there is no defining expression.)

Similar to other mathematical objects like variables and sequences, functions are usually represented by symbols for their names. Letter symbols like \(f\) or \(g\) are particularly common. We would write \(f : x \mapsto y\) to say that the name of the function representing the map from a variable \(x\) to \(y\) is \(f\text{.}\) The independent variable \(x\) is the input for the function; the dependent variable \(y\) is the output of the function.

We often use function notation, writing \(y = f(x)\text{.}\) The parentheses in function notation indicate that whatever is inside is the value for the input, not multiplication. So this equation says that the dependent variable \(y\) is equal to the output of the function \(f\) when the input has the value represented by \(x\text{.}\) We usually read the equation, “\(y\) equals the value of \(f\) of \(x\text{.}\)” When we have an equation expressing \(y\) as an explicit expression involving \(x\text{,}\) that expression can be used to define the function.

Example 13.2.2.

Consider the equation \(2x+5y = 10\text{,}\) which relates the variables \(x\) and \(y\text{.}\) Because we can solve for the variable \(y\) to be a dependent variable,

\begin{equation*} y = -\frac{2}{5}x + 2, \end{equation*}

the equation defines a function \(x \mapsto y\text{.}\) We can choose any name for this function (other than the symbols \(x\) or \(y\text{,}\) obviously). We might choose to use the name \(P\) and write this as a map

\begin{equation*} P : x \mapsto y = -\frac{2}{5}x+2\text{.} \end{equation*}

Using the usual function notation, we would instead write

\begin{equation*} y = P(x) = -\frac{2}{5}x+2\text{.} \end{equation*}

When we wrote explicit formulas for the value of a sequence with the index as the independent variable, we noted that we had a map from the index to the value of the sequence. That was an example of a function.

Example 13.2.3.

For the explicitly defined sequence \(x_n = 3n-2\text{,}\) \(n=1, 2, 3, \ldots\text{,}\) the equation defines a map \(n \mapsto x_n = 3n-2\text{.}\) We could name the function \(S\text{,}\) for example, and write \(S(n) = 3n-2\) so that \(x_n = S(n)\text{.}\)

Subsection 13.2.3 Projection Functions

We now return to the concept of a recursively defined sequence and the projection function. A sequence is recursive if the same rule is used to go from one value of the sequence to the next. For our earlier example of an arithmetic sequence, we had a pattern of equations

\begin{gather*} x_2 = x_1 + 3,\\ x_3 = x_2 + 3,\\ x_4=x_3+3,\\ \vdots \end{gather*}

The rule was always the same, but the symbols were different because they involved different index values.

We need some notation to capture the idea of consecutive values of a sequence. If \(n\) represents the value of the index for a sequence, then \(n+1\) represents the value of the index for the subsequent term of the sequence and \(n-1\) represents the value of the index for the preceding term of the sequence. For example, if \(n=3\text{,}\) then \(x_n\) would be \(x_3\text{,}\) \(x_{n+1}\) would be \(x_4\text{,}\) and \(x_{n-1}\) would be \(x_2\text{.}\) All of our equations follow the pattern

\begin{equation*} x_{n} = x_{n-1} + 3\text{,} \end{equation*}

where the first equation corresponds to \(n=2\text{,}\) the second to \(n=3\text{,}\) and so forth. Equivalently, we could think of all of the equations as following the pattern

\begin{equation*} x_{n+1} = x_{n} + 3\text{,} \end{equation*}

but now the first equation comes from \(n=1\) and the second from \(n=2\text{.}\) This equation which relates \(x_{n}\) and \(x_{n-1}\) is called a recurrence relation or recursive equation for the sequence. Because the equation has been written with \(x_{n}\) as a dependent variable in terms of the value of \(x_{n-1}\text{,}\) we actually have a projection function.

Definition 13.2.4. Projection Function.

Suppose a sequence \(x\) is defined by a recurrence relation of the form

\begin{equation*} x_{n} = f(x_{n-1}). \end{equation*}

The function \(f\) defining the relation \(x_{n-1} \mapsto x_{n}\) is called the projection function. Equivalently, we could write the recurrence relation in terms of a previous value as

\begin{equation*} x_{n+1} = f(x_{n})\text{.} \end{equation*}

For a sequence with a recurrence relation \(x_{n} = x_{n-1} + 3\text{,}\) the projection function is \(f : x_{n-1} \mapsto x_{n} = x_{n-1} + 3\text{.}\) The function \(f\) takes a value as an input and maps it to an output that is that value plus 3. I find it useful to imagine the independent variable in a function as if it were a box, as in

\begin{equation*} f(x_{n-1}) = x_{n-1} + 3 \quad \Leftrightarrow \quad f(\square) = \square + 3\text{.} \end{equation*}

Whatever is between the parentheses for the input of a function will go in the box of the formula. With this understanding, any variable can be used as a placeholder for the input: \(f(x) = x+3\) and \(f(a)=a+3\) describe the same mapping rule.

When we have a projection function for a sequence defined recursively, we can apply the function repeatedly to calculate values for the sequence. Many sequences can use the same projection function. We need an initial value to begin the process.

Example 13.2.5.

A sequence \(u = (u_n)_{n=0}^{\infty}\) is defined recursively by the projection function \(f(x)=2x-5\) and an initial value \(u_0 = 3\text{.}\) Find the next four terms of the sequence.

Solution

The projection function defines the map \(u_{n-1} \mapsto u_{n}\) according to the rule \(f(x)=2x-5\) or \(f(\square) = 2 \cdot \square - 5\text{.}\) It tells us that if we use an input coming from a sequence value, the output of the function will be the next sequence value. We were given an initial value \(u_0 = 3\text{.}\) Using the recursive equation for \(n=1\) and the preceding value \(u_0=3\) as the input to \(f\text{,}\) the output will be the value \(u_1\text{:}\)

\begin{equation*} u_1 = f(u_0) = f(3) = 2(3) - 5 = 1\text{.} \end{equation*}

Now that we know \(u_1\text{,}\) we can use that value as an input to get \(u_2\text{,}\) and so on:

\begin{align*} u_2 &= f(u_1) = 2(1) - 5 = -3,\\ u_3 &= f(u_2) = 2(-3) - 5 = -11,\\ u_4 &= f(u_3) = 2(-11) - 5 = -27. \end{align*}

Sometimes, a recurrence relation is not written with the new sequence value isolated. To identify the projection function, we need to solve for the new value of the sequence.

Example 13.2.6.

A sequence is defined by the recurrence relation

\begin{equation*} w_{n+1}-w_n = 1.4 w_n - \frac{3}{w_n}, \quad n \ge -1, \end{equation*}

and an initial value \(w_{-1}=1\text{.}\) Find the recursive equation corresponding to the projection function, \(w_n \mapsto w_{n+1}\text{,}\) and find \(f(x)\text{.}\) Use this to find \(w_0\) and \(w_1\text{.}\)

Solution

To find the recursive equation, we need to solve for \(w_{n+1}\text{.}\)

\begin{gather*} w_{n+1}-w_n = 1.4 w_n - \frac{3}{w_n}\\ w_{n+1} = 2.4 w_n - \frac{3}{w_n} \end{gather*}

This recursive equation gives us a map from a current value \(w_n\) to the next value \(w_{n+1}\) in the sequence, \(w_n \mapsto w_{n+1}\text{,}\) which is the projection function

\begin{equation*} w_{n+1} = f(w_n) = 2.4 w_n - \frac{3}{w_n}. \end{equation*}

This means that using an input \(x\) gives

\begin{equation*} f(x) = 2.4 x - \frac{3}{x}. \end{equation*}

Once we have the map, we can repeatedly use the projection function to find subsequent values of the sequence.

\begin{align*} w_{-1} &= 1\\ w_{0} &= f(w_{-1}) = f(1)\\ &= 2.4(1)-\frac{3}{1} = -0.6\\ w_{1} &= f(w_0) = f(-0.6)\\ &= 2.4(-0.6)-\frac{3}{-0.6} = 3.56 \end{align*}

Subsection 13.2.4 Arithmetic and Geometric Sequences Revisited

The arithmetic and geometric sequences have simple explicit formulas. We use these formulas to illustrate the idea of a sequence as a map from the index to the sequence value.

The explicit formula for an arithmetic sequence is a special case of a linear function. The increment of the sequence represents the slope. The initial value gives us a known point. Knowing how many steps away from the given point along with the increment allows us to compute other sequence values.

Example 13.2.7.

Find the explicit formula for the arithmetic sequence \(x=(7,10,13,16,\ldots)\text{.}\) Use the formula to find \(x_{100}\text{.}\)

Solution

The initial value \(x_1=7\) means our function will be a map \(n \mapsto x_n\) that takes an input \(n=1\) to an output \(x_1=7\text{.}\) The increment of 3 that appears in the recursive equation \(x_{n} = x_{n-1} + 3\) means that the function increases by 3 for every increment of the index by 1. That is, the slope is \(m=+3\text{.}\) The value of \(x_n\) will equal 7 plus 3 times the number of increments in the index,

\begin{equation*} x_n = 7 + 3(n-1)\text{.} \end{equation*}

We could find an equivalent expression after using the distributive property,

\begin{equation*} x_n = 4 + 3n\text{.} \end{equation*}

Because we now have the function \(n \mapsto x_n\text{,}\) we can find the value of the sequence for any index using this expression. To find \(x_{100}\text{,}\) we use \(n=100\) and the map \(n \mapsto x_n\text{,}\)

\begin{equation*} x_{100} = 4 + 3 \cdot 100 = 304\text{.} \end{equation*}

The following theorem provides the formula for the explicit formula of any arithmetic sequence.

The explicit formula for a geometric sequence is a special case of an exponential function. The multiple for the sequence corresponds to the base of the exponential. An initial value gives us a known point. The formula will count how many increments the index has changed and multiply by the base to that power.

Example 13.2.9.

Find the explicit formula for the geometric sequence \(u=(48,24,12,6,3,\ldots)\text{.}\) Use the formula to find \(u_{20}\text{.}\)

Solution

The sequence \(u\) is geometric because the ratio of the sequence value to its predecessor is always the same.

\begin{gather*} \frac{u_2}{u_1} = \frac{24}{48} = \frac{1}{2}\\ \frac{u_3}{u_2} = \frac{12}{24} = \frac{1}{2}\\ \frac{u_4}{u_3} = \frac{6}{12} = \frac{1}{2}\\ \frac{u_5}{u_4} = \frac{3}{6} = \frac{1}{2} \end{gather*}

The recursive formula for the sequence multiplies the previous sequence value by \(\rho=\frac{1}{2}\text{,}\)

\begin{equation*} u_{n} = \frac{1}{2} \cdot u_{n-1}\text{.} \end{equation*}

The initial value \(u_1=48\) means our function will be a map \(n \mapsto x_n\) that takes an input \(n=1\) to an output \(x_1=48\text{.}\)

Each time the index is incremented by 1, the value of the sequence is multiplied by \(\rho=\frac{1}{2}\text{.}\) We can count the number of increments for the index \(n\) by the expression \(n-1\text{.}\) Because repeated multiplication is a power, we obtain an explicit formula

\begin{equation*} u_{n} = u_1 \cdot \rho^{n-1} = 48 \cdot \left( \frac{1}{2} \right)^{n-1}\text{.} \end{equation*}

Using the properties of powers, this is equivalent to

\begin{equation*} u_{n} = \frac{48}{2^{n-1}}. \end{equation*}

With the function \(n \mapsto u_n\text{,}\) we can find the value of the sequence for any index using this expression. To find \(u_{20}\text{,}\) we use \(n=20\) and the map \(n \mapsto u_n\text{,}\)

\begin{equation*} u_{20} = \frac{48}{2^{19}}. \end{equation*}

If we rewrite \(48 = 16 \cdot 3 = 2^4 \cdot 3\) and then simplify the fraction, this is equivalent to

\begin{equation*} u_{20} = \frac{3}{2^{15}} = \frac{3}{32768}. \end{equation*}

The general formula for a geometric sequence is provided in the following theorem.

Subsection 13.2.5 Graphical Representations of Projections

If we think about a function as a map between two number lines, then the process of using a projection function to find values in a sequence can be visualized using such a mapping. Consider two number lines. The top number line will represent the current value of the sequence or the input of the function. The bottom number line will represent the next value of the sequence or the output of the function. The projection function defines the rule for how we go from the input to the output. Because the process repeats, we also go from the output number line to the same value on the input number line.

Example 13.2.11.

For the sequence defined by the projection function \(f(x) = 2x-5\) and initial value \(u_0 = 3\text{,}\) the mapping used to generate the first few terms of the sequence can be represented graphically as shown below.

Example 13.2.12.

For the sequence defined by the projection function

\begin{equation*} w_{n+1} = 2.4 w_n - \frac{3}{w_n} \end{equation*}

and initial value \(w_{-1} = 1\text{,}\) the mapping used to generate the first few terms of the sequence can be represented graphically as shown below.

The graph of a function \(f\) shows all points \((x,y)\) in the plane where \(y=f(x)\text{.}\) Where a mapping visualizes a function as going from the input number line to the output number line, a graph visualizes a function by thinking of the \(x\)-axis as the input number line and the vertical position of the graph in the \(y\)-direction as the output. It is as if there were a separate vertical number line parallel to the \(y\)-axis (and perpendicular to the \(x\)-axis) through every value on the \(x\)-axis. The point on the graph corresponds precisely to the location of the output for the function.

We can use the graph of a projection function to visualize how to generate a recursive sequence. The algorithm we use follows the same pattern as we used in the mapping and generates what is called a cobweb diagram in the plane.

Example 13.2.14.

Draw the first four iterations of the cobweb diagram for the sequence \(u\) with projection function \(f(x) = 2x-5\) and initial value \(u_0=3\text{.}\)

Solution

We start by drawing the graphs \(y=f(x)=2x-5\) and \(y=x\) on the same graph. We then start with a point on the \(x\)-axis at \(x=3\) corresponding to the value of \(u_0=3\text{.}\) We want to use this value to find the next value in the sequence \(u_1\text{.}\) This use the projection function, so we go up to the value of the function \(f(3)=1\text{,}\) drawing a vertical line segment to the point \((3,1)\text{.}\) We now know \(u_1=1\) and we need to use this as a new input for the projection function. So the next step is to draw a horizontal segment to \(y=x\) at the point \((1,1)\text{.}\) Now that our \(x\)-value is \(1\text{,}\) we can repeat the process and use the function to find \(u_2=f(1)=-3\text{,}\) drawing a vertical segment down to the point \((1,-3)\) and then a horizontal segment to \((-3,-3)\text{.}\)

Subsection 13.2.6 Summary

  • A sequence \(x\) is recursive when the relation between consecutive values of the sequence is the same for every index. An equation describing this relation is called a recurrence relation. If we can solve for \(x_{n}\) as a dependent variable with \(x_{n-1}\) as the independent variable, the corresponding equation is called the recursive equation.
  • An arithmetic sequence with common difference \(c\) has a projection function \(f(x)=x+c\text{,}\) a recursive relation
    \begin{equation*} x_{n}=x_{n-1} + c\text{,} \end{equation*}
    and an explicit formula given a known value for \(x_k\text{,}\)
    \begin{equation*} x_n = x_k + \beta(n-k). \end{equation*}
  • A geometric sequence with common ratio \(\rho\) has a projection function \(f(x)=\rho x\text{,}\) a recursive relation
    \begin{equation*} x_{n}=\rho \cdot x_{n-1}\text{,} \end{equation*}
    and an explicit formula given a known value for \(x_k\text{,}\)
    \begin{equation*} x_n = x_k \cdot \rho^{n-k}. \end{equation*}
  • We think of functions as maps from the value of one variable to the value of another variable. For a sequence \(x\text{,}\) the map from the index \(n\) to the sequence value \(x_n\) is called the explicit function of the sequence. For a recursive sequence, the map from one sequence value \(x_{n-1}\) to the next sequence value \(x_{n}\) is called the projection function.
  • The graph of a function uses values on the \(x\)-axis as input values and the vertical position of the graph as output values. A cobweb diagram uses the graph of a projection function with repeatedly updated inputs to generate a visual representation of a recursive sequence.

Exercises 13.2.7 Exercises

Determine if each sequence is arithmetic, geometric, or neither. For each sequence that is arithmetic or geometric, (i) state the recursive equation for the sequence, (ii) find the projection function \(f(x)\text{,}\) (iii) state an explicit formula for the sequence, and (iv) use the explicit formula to find the value with index 20.

1.

\(u = (u_n)_{n=0}^{\infty} = (-8, -2, 4, 10, \ldots)\)

2.

\(t = (t_k)_{k=2}^{\infty} = (27, 23, 19, 15, \ldots)\)

3.

\(v = (v_k)_{k=-2}^{\infty} = (12, 16, 21, 27, \ldots)\)

4.

\(w = (w_k)_{k=1}^{\infty} = (4, 20, 100, 500, \ldots)\)

5.

\(z = (z_i)_{i=0}^{\infty} = (27, 18, 12, 8, \ldots)\)

Each problem gives a projection function and an initial value that together determine a sequence recursively. Find the four terms following the initial value. Illustrate the sequence as a map between two number lines.

6.

\(P = (P_t)_{t=0}^{\infty}\) with \(P_0 = 400\) and projection function \(f(x) = x + 25\text{.}\)

7.

\(u = (u_n)_{n=0}^{\infty}\) with \(u_0 = 3\) and projection function \(f(x) = 1.5x + 1\text{.}\)

8.

\(u = (u_n)_{n=0}^{\infty}\) with \(u_0 = -3\) and projection function \(f(x) = 1.5x + 1\text{.}\)

9.

\(w = (w_i)_{i=1}^{\infty}\) with \(w_{1} = 4\) and projection function \(f(x) = 2.5x - 6\text{.}\)

10.

\(w = (w_i)_{i=1}^{\infty}\) with \(w_{1} = 5\) and projection function \(f(x) = 2.5x - 6\text{.}\)

11.

\(z = (z_j)_{j=0}^{\infty}\) with \(z_{0} = 16\) and projection function \(f(x) = \sqrt{x}\text{.}\)

Each problem defines a sequence recursively. Give the formula of the projection function \(f(x)\text{.}\) Create the cobweb diagram for the sequence corresponding to the first five values of the sequence.

12.

\(Q = (Q_t)_{t=0}^{\infty}\) with \(Q_{0} = 3\) and \(Q_{t} = Q_{t-1} + 4\text{.}\)

13.

\(c = (c_k)_{k=0}^{\infty}\) with \(c_{0} = 10\) and \(c_{k+1} = 0.75 c_k\text{.}\)

14.

\(S = (S_n)_{n=0}^{\infty}\) with \(S_{0} = 10\) and \(S_{n} = 0.8 S_{n-1} + 4\text{.}\)

15.

\(P = (P_t)_{t=0}^{\infty}\) with \(P_{0} = 1\) and \(\displaystyle P_{t+1} = \frac{20 P_t}{P_t + 10}\text{.}\)

login