## Introduction to Sequences

A mathematical sequence is an ordered list of objects, often numbers. Sometimes the numbers in a sequence are defined in terms of a previous number in the list.

### Learning Objectives

Differentiate between different types of sequences

### Key Takeaways

#### Key Points

• The number of ordered elements (possibly infinite ) is called the length of the sequence. Unlike a set, order matters, and a particular term can appear multiple times at different positions in the sequence.
• An arithmetic sequence is one in which a term is obtained by adding a constant to a previous term of a sequence. So the $n$th term can be described by the formula $a_n = a_{n-1} + d$.
• A geometric sequence is one in which a term of a sequence is obtained by multiplying the previous term by a constant. It can be described by the formula $a_n=r \cdot a_{n-1}$.

#### Key Terms

• sequence: An ordered list of elements, possibly infinite in length.
• finite: Limited, constrained by bounds.
• set: A collection of zero or more objects, possibly infinite in size, and disregarding any order or repetition of the objects that may be contained within it.

### Sequences

In mathematics, a sequence is an ordered list of objects. Like a set, it contains members (also called elements or terms). The number of ordered elements (possibly infinite) is called the length of the sequence. Unlike a set, order matters, and a particular term can appear multiple times at different positions in the sequence.

For example, $(M, A, R, Y)$ is a sequence of letters that differs from $(A, R, M, Y)$, as the ordering matters, and $(1, 1, 2, 3, 5, 8)$, which contains the number 1 at two different positions, is a valid sequence. Sequences can be finite, as in this example, or infinite, such as the sequence of all even positive integers $(2, 4, 6, \cdots )$. Finite sequences are sometimes known as strings or words and infinite sequences as streams.

### Finite and Infinite Sequences

A more formal definition of a finite sequence with terms in a set $S$ is a function from $\left \{ 1, 2, \cdots, n \right \}$ to $S$ for some $n > 0$. An infinite sequence in $S$ is a function from $\left \{ 1, 2, \cdots \right \}$ to $S$. For example, the sequence of prime numbers $(2,3,5,7,11, \cdots )$ is the function

$1\rightarrow 2, 2\rightarrow 3, 3\rightarrow 5, 4\rightarrow 7, 5\rightarrow 11, \cdots$

A sequence of a finite length n is also called an $n$-tuple. Finite sequences include the empty sequence $( \quad )$ that has no elements.

### Recursive Sequences

Many of the sequences you will encounter in a mathematics course are produced by a formula, where some operation(s) is performed on the previous member of the sequence $a_{n-1}$ to give the next member of the sequence $a_n$. These are called recursive sequences.

### Arithmetic Sequences

An arithmetic (or linear) sequence is a sequence of numbers in which each new term is calculated by adding a constant value to the previous term. An example is $(10,13,16,19,22,25)$. In this example, the first term (which we will call $a_1$) is $10$, and the common difference ($d$)—that is, the difference between any two adjacent numbers—is $3$. The recursive definition is therefore

$\displaystyle{a_n=a_{n-1}+3, a_1=10}$

Another example is $(25,22,19,16,13,10)$. In this example $a_1 = 25$, and $d=-3$. The recursive definition is therefore

$\displaystyle{a_n=a_{n-1}-3, a_1=25}$

In both of these examples, $n$ (the number of terms) is $6$.

### Geometric Sequences

A geometric sequence is a list in which each number is generated by multiplying a constant by the previous number. An example is $(2,6,18,54,162)$. In this example, $a_1=2$, and the common ratio ($r$)—that is, the ratio between any two adjacent numbers—is 3. Therefore the recursive definition is

$a_n=3a_{n-1}, a_1=2$

Another example is $(162,54,18,6,2)$. In this example $a_1=162$, and $\displaystyle{r=\frac{1}{3}}$. Therefore the recursive formula is

$\displaystyle{a_n=\frac13\cdot a_{n-1}, a_1=162}$

In both examples $n=5$.

### Explicit Definitions

An explicit definition of an arithmetic sequence is one in which the $n$th term is defined without making reference to the previous term. This is more useful, because it means you can find (for instance) the 20th term without finding all of the other terms in between.

To find the explicit definition of an arithmetic sequence, you begin writing out the terms. Assume our sequence is $t_1, t_2, \dots$. The first term is always $t_1$. The second term goes up by $d$, and so it is $t_1+d$. The third term goes up by $d$ again, and so it is $(t_1+d)+d,$  or in other words, $t_1+2d$. So we see that:

\displaystyle{ \begin{align} t_1 &= t_1 \\ t_2 &= t_1+d \\ t_3 &= t_1+2d \\ t_4 &= t_1+3d \\ &\vdots \end{align} }

and so on. From this you can see the generalization that:

$t_n = t_1+(n-1)d$

which is the explicit definition we were looking for.

The explicit definition of a geometric sequence is obtained in a similar way. The first term is $t_1$; the second term is $r$ times that, or $t_1r$; the third term is $r$ times that, or $t_1r^2$; and so on. So the general rule is:

$t_n=t_1 \cdot r^{n-1}$

## The General Term of a Sequence

Given terms in a sequence, it is often possible to find a formula for the general term of the sequence, if the formula is a polynomial.

### Learning Objectives

Practice finding a formula for the general term of a sequence

### Key Takeaways

#### Key Points

• Given terms in a sequence generated by a polynomial, there is a method to determine the formula for the polynomial.
• By hand, one can take the differences between each term, then the differences between the differences in terms, etc. If the differences eventually become constant, then the sequence is generated by a polynomial formula.
• Once a constant difference is achieved, one can solve equations to generate the formula for the polynomial.

#### Key Terms

• sequence: A set of things next to each other in a set order; a series
• general term: A mathematical expression containing variables and constants that, when substituting integer values for each variable, produces a valid term in a sequence.

Given several terms in a sequence, it is sometimes possible to find a formula for the general term of the sequence. Such a formula will produce the $n$th term when a value for the integer $n$ is put into the formula.

If a sequence is generated by a polynomial, this fact can be detected by noticing whether the computed differences eventually become constant.

### Linear Polynomials

Consider the sequence:

$5, 7, 9, 11, 13, \dots$

The difference between $7$ and $5$ is $2$. The difference between $7$ and $9$ is also $2$. In fact, the difference between each pair of terms is $2$. Since this difference is constant, and this is the first set of differences, the sequence is given by a first-degree (linear) polynomial.

Suppose the formula for the sequence is given by $an+b$ for some constants $a$ and $b$. Then the sequence looks like:

$a+b, 2a+b, 3a+b, \dots$

The difference between each term and the term after it is $a$. In our example, $a=2$. It is possible to solve for $b$ using one of the terms in the sequence. Using the first number in the sequence and the first term:

\displaystyle{ \begin{align} 5 &= a+b \\ b &= 5-a \\ b &= 5-(2)\\ b &= 3 \end{align} }

So, the $n$th term of the sequence is given by $2n+3$.

Suppose the $n$th term of a sequence was given by $an^2+bn+c$. Then the sequence would look like:

$a+b+c, 4a+2b+c, 9a+3b+c, \dots$

This sequence was created by plugging in $1$ for $n$, $2$ for $n$, $3$ for $n$, etc.

If we start at the second term, and subtract the previous term from each term in the sequence, we can get a new sequence made up of the differences between terms. The first sequence of differences would be:

$3a+b, 5a+b, 7a+b, \dots$

Now, we take the differences between terms in the new sequence. The second sequence of differences is:

$2a, 2a, 2a, 2a, \dots$

The computed differences have converged to a constant after the second sequence of differences. This means that it was a second-order (quadratic) sequence. Working backward from this, we could find the general term for any quadratic sequence.

### Example

Consider the sequence:

$4, -7, -26, -53, -88, -131, \dots$

The difference between $-7$ and $4$ is $-11$, and the difference between $-26$ and $-7$ is $-19$. Finding all these differences, we get a new sequence:

$-11, -19, -27, -35, -43, \dots$

This list is still not constant. However, finding the difference between terms once more, we get:

$-8, -8, -8, -8, \dots$

This fact tells us that there is a polynomial formula describing our sequence. Since we had to do differences twice, it is a second-degree (quadratic) polynomial.

We can find the formula by realizing that the constant term is $-8$, and that it can also be expressed by $2a$. Therefore $a=-4$.

Next we note that the first item in our first list of differences is $-11$, but that generically it is supposed to be $3a+b$, so we must have $3(-4)+b=-11$, and $b=1$.

Finally, note that the first term in the sequence is $4$, and can also be expressed by

$a+b+c = -4+1+c$

So, $c=7$, and the formula that generates the sequence is $-4a^2+b+7c$.

### General Polynomial Sequences

This method of finding differences can be extended to find the general term of a polynomial sequence of any order. For higher orders, it will take more rounds of taking differences for the differences to become constant, and more back-substitution will be necessary in order to solve for the general term.

### General Terms of Non-Polynomial Sequences

Some sequences are generated by a general term which is not a polynomial. For example, the geometric sequence $2, 4, 8, 16,\dots$ is given by the general term $2^n$. Because this term is not a polynomial, taking differences will never result in a constant difference.

General terms of non-polynomial sequences can be found by observation, as above, or by other means which are beyond our scope for now. Given any general term, the sequence can be generated by plugging in successive values of $n$.

## Series and Sigma Notation

Sigma notation, denoted by the uppercase Greek letter sigma $\left ( \Sigma \right ),$ is used to represent summations—a series of numbers to be added together.

### Learning Objectives

Calculate the sum of a series represented in sigma notation

### Key Takeaways

#### Key Points

• A series is a summation performed on a list of numbers. Each term is added to the next, resulting in a sum of all terms.
• Sigma notation is used to represent the summation of a series. In this form, the capital Greek letter sigma $\left ( \Sigma \right )$ is used. The range of terms in the summation is represented in numbers below and above the $\Sigma$ symbol, called indices. The lowest index is written below the symbol and the largest index is written above.

#### Key Terms

• summation: A series of items to be summed or added.
• sigma: The symbol $\Sigma$, used to indicate summation of a set or series.

Summation is the operation of adding a sequence of numbers, resulting in a sum or total. If numbers are added sequentially from left to right, any intermediate result is a partial sum. The numbers to be summed (called addends, or sometimes summands) may be integers, rational numbers, real numbers, or complex numbers. For finite sequences of such elements, summation always produces a well-defined sum.

A series is a list of numbers—like a sequence—but instead of just listing them, the plus signs indicate that they should be added up.

For example, $4+9+3+2+17$ is a series. This particular series adds up to $35$. Another series is $2+4+8+16+32+64$. This series sums to $126$.

### Sigma Notation

One way to compactly represent a series is with sigma notation, or summation notation, which looks like this:

$\displaystyle{\sum _{n=3}^{7}{n^2}}$

The main symbol seen is the uppercase Greek letter sigma. It indicates a series. To “unpack” this notation, $n=3$ represents the number at which to start counting ($3$), and the $7$ represents the point at which to stop. For each term, plug that value of $n$ into the given formula ($n^2$). This particular formula, which we can read as “the sum as $n$ goes from $3$ to $7$ of $n^2$,” means:

$\displaystyle{3^2 + 4^2 + 5^2 + 6^2 + 7^2}$

More generally, sigma notation can be defined as:

$\displaystyle{\sum _{ i=m }^{ n }{ x_i }=x_m+x_{m+1}+x_{m+2}+…+x_{n-1}+x_n}$

In this formula, i represents the index of summation, $x_i$ is an indexed variable representing each successive term in the series, $m$ is the lower bound of summation, and $n$ is the upper bound of summation. The “$i = m$” under the summation symbol means that the index $i$ starts out equal to $m$. The index, $i$, is incremented by $1$ for each successive term, stopping when $i=n$.

Another example is:

\displaystyle{ \begin{align} \sum_{i=3}^6 (i^2+1) &= (3^2+1)+(4^2+1)+(5^2+1)+(6^2+1) \\ &=10+17+26+37 \\ &=90 \end{align} }

This series sums to $90.$ So we could write:

$\displaystyle \sum_{i=3}^6 (i^2+1)=90$

### Other Forms of Sigma Notation

Informal writing sometimes omits the definition of the index and bounds of summation when these are clear from context. For example:

$\displaystyle{\sum x_i^2=\sum _{ i=1 }^n x_i^2}$

## Recursive Definitions

A recursive definition of a function defines its values for some inputs in terms of the values of the same function for other inputs.

### Learning Objectives

Use a recursive formula to find specific terms of a sequence

### Key Takeaways

#### Key Points

• In mathematical logic and computer science, a recursive definition, or inductive definition, is used to define an object in terms of itself.
• The recursive definition for an arithmetic sequence is: $a_n=a_{n-1}+d$. The recursive definition for a geometric sequence is: $a_n=r \cdot a_{n-1}$.

### Recursion

In mathematical logic and computer science, a recursive definition, or inductive definition, is used to define an object in terms of itself. A recursive definition of a function defines values of the function for some inputs in terms of the values of the same function for other inputs.

For example, the factorial function $n!$ is defined by the rules:

$0!=1$

$(n+1)!=(n+1)n!$

This definition is valid because, for all $n$, the recursion eventually reaches the base case of $0$.

For example, we can compute $5!$ by realizing that $5!=5\cdot 4!$, and that $4!=4\cdot 3!$, and that $3!=3\cdot 2!$, and that $2!=2\cdot 1!,$ and that:

\displaystyle{ \begin{align} 1! &=1\cdot 0! \\ &= 1\cdot 1 \\ &=1 \end{align} }

Putting this all together we get:

\displaystyle{ \begin{align} 5! &=5\cdot 4\cdot 3\cdot 2 \cdot 1 \\ &= 120 \end{align} }

### Recursive Formulas for Sequences

When discussing arithmetic sequences, you may have noticed that the difference between two consecutive terms in the sequence could be written in a general way:

$a_n=a_{n-1}+d$

The above equation is an example of a recursive equation since the $n$th term can only be calculated by considering the previous term in the sequence. Compare this with the equation:

$a_n=a_1+d(n-1).$

In this equation, one can directly calculate the nth-term of the arithmetic sequence without knowing the previous terms. Depending on how the sequence is being used, either the recursive definition or the non-recursive one might be more useful.

A recursive geometric sequence follows the formula:

$a_n=r\cdot a_{n-1}$

An applied example of a geometric sequence involves the spread of the flu virus. Suppose each infected person will infect two more people, such that the terms follow a geometric sequence.

The flu virus is a geometric sequence: Each person infects two more people with the flu virus, making the number of recently-infected people the nth term in a geometric sequence.

Using this equation, the recursive equation for this geometric sequence is:

$a_n=2 \cdot a_{n-1}$

Recursive equations are extremely powerful. One can work out every term in the series just by knowing previous terms. As can be seen from the examples above, working out and using the previous term $a_{n−1}$ can be a much simpler computation than working out $a_{n}$ from scratch using a general formula. This means that using a recursive formula when using a computer to manipulate a sequence might mean that the calculation will be finished quickly.