Sequences

$\newenvironment {prompt}{}{} \newcommand {\todo }[0]{} \newcommand {\oiint }[0]{{\large \bigcirc }\kern -1.56em\iint } \newcommand {\mooculus }[0]{\textsf {\textbf {MOOC}\textnormal {\textsf {ULUS}}}} \newcommand {\npnoround }[0]{\nprounddigits {-1}} \newcommand {\npnoroundexp }[0]{\nproundexpdigits {-1}} \newcommand {\npunitcommand }[1]{\ensuremath {\mathrm {#1}}} \newcommand {\RR }[0]{\mathbb R} \newcommand {\R }[0]{\mathbb R} \newcommand {\N }[0]{\mathbb N} \newcommand {\Z }[0]{\mathbb Z} \newcommand {\sagemath }[0]{\textsf {SageMath}} \newcommand {\d }[0]{\mathop {}\!d} \newcommand {\l }[0]{\ell } \newcommand {\ddx }[0]{\frac {d}{\d x}} \newcommand {\zeroOverZero }[0]{\ensuremath {\boldsymbol {\tfrac {0}{0}}}} \newcommand {\inftyOverInfty }[0]{\ensuremath {\boldsymbol {\tfrac {\infty }{\infty }}}} \newcommand {\zeroOverInfty }[0]{\ensuremath {\boldsymbol {\tfrac {0}{\infty }}}} \newcommand {\zeroTimesInfty }[0]{\ensuremath {\small \boldsymbol {0\cdot \infty }}} \newcommand {\inftyMinusInfty }[0]{\ensuremath {\small \boldsymbol {\infty -\infty }}} \newcommand {\oneToInfty }[0]{\ensuremath {\boldsymbol {1^\infty }}} \newcommand {\zeroToZero }[0]{\ensuremath {\boldsymbol {0^0}}} \newcommand {\inftyToZero }[0]{\ensuremath {\boldsymbol {\infty ^0}}} \newcommand {\numOverZero }[0]{\ensuremath {\boldsymbol {\tfrac {\#}{0}}}} \newcommand {\dfn }[0]{\textbf } \newcommand {\unit }[0]{\mathop {}\!\mathrm } \newcommand {\eval }[1]{\bigg [ #1 \bigg ]} \newcommand {\seq }[1]{\left ( #1 \right )} \newcommand {\epsilon }[0]{\varepsilon } \newcommand {\phi }[0]{\varphi } \newcommand {\iff }[0]{\Leftrightarrow } \DeclareMathOperator {\arccot }{arccot} \DeclareMathOperator {\arcsec }{arcsec} \DeclareMathOperator {\arccsc }{arccsc} \DeclareMathOperator {\si }{Si} \DeclareMathOperator {\scal }{scal} \DeclareMathOperator {\sign }{sign} \newcommand {\arrowvec }[1]{{\overset {\rightharpoonup }{#1}}} \newcommand {\vec }[1]{{\overset {\boldsymbol {\rightharpoonup }}{\mathbf {#1}}}} \DeclareMathOperator {\proj }{\vec {proj}} \newcommand {\veci }[0]{{\boldsymbol {\hat {\imath }}}} \newcommand {\vecj }[0]{{\boldsymbol {\hat {\jmath }}}} \newcommand {\veck }[0]{{\boldsymbol {\hat {k}}}} \newcommand {\vecl }[0]{\vec {\boldsymbol {\l }}} \newcommand {\uvec }[1]{\mathbf {\hat {#1}}} \newcommand {\utan }[0]{\mathbf {\hat {t}}} \newcommand {\unormal }[0]{\mathbf {\hat {n}}} \newcommand {\ubinormal }[0]{\mathbf {\hat {b}}} \newcommand {\dotp }[0]{\bullet } \newcommand {\cross }[0]{\boldsymbol \times } \newcommand {\grad }[0]{\boldsymbol \nabla } \newcommand {\divergence }[0]{\grad \dotp } \newcommand {\curl }[0]{\grad \cross } \newcommand {\lto }[0]{\mathop {\longrightarrow \,}\limits } \newcommand {\bar }[0]{\overline } \newcommand {\surfaceColor }[0]{violet} \newcommand {\surfaceColorTwo }[0]{redyellow} \newcommand {\sliceColor }[0]{greenyellow} \newcommand {\vector }[1]{\left \langle #1\right \rangle } \newcommand {\sectionOutcomes }[0]{} \newcommand {\HyperFirstAtBeginDocument }[0]{\AtBeginDocument } \newcommand {\epstopdfsetup }[0]{\setkeys {ETE}} changed the theorem header of amsthm failed\MessageBreak }}} \newcommand {\GetTitleStringSetup }[0]{\setkeys {gettitlestring}} \newcommand {\Sectionformat }[2]{#1}$

A sequence is an ordered list of numbers.

Let’s get to the heart of the matter:

A sequence is an ordered list of numbers.

For example, here is a sequence: $1,1, 2, 3, 5, 8, 13, 21, \ldots$ Here is another sequence:

$e, 3\pi , \arctan (27), \frac {1}{42}, \ldots$

Note that numbers in the list can repeat. The dots “…” signify that the list keeps going, and going...and going forever. We often want to refer to a specific term in this list, so we introduce some standard notation:

The notation: $\left \{a_n\right \}_{n=1}$ will be used to denote the following ordered list of numbers:

$a_1, a_2, a_3, \ldots ,$

The subscript in the above notation is called the index and describes how we reference the first term. In general, we like to index sequences starting at $n=0$ or $n=1$ , but would like to have the freedom to make other choices should it be convenient. Thus, there is no unique way to describe a given list of numbers; for example, for the sequence:

$1,1, 2, 3, 5, 8, 13, 21, \ldots$ we could define this by $\left \{a_n\right \}_{n=1}$ , where $a_1=1$ , $a_2=1$ , $a_3=2$ , etc or by $\left \{b_n\right \}_{n=3}$ , where $b_3=1$ , $b_4=1$ , $b_5=2$ , etc.

Many authors denote sequences using other conventions. Some other common notations you may see are: $\begin{align*} &a_n = f(n), n \geq 1 \\ & \left(a_n\right)_{n \in \N}, \\ & \left\{a_n\right\}_{n=1}^\infty, \\ & \left\{f(n)\right\}_{n=1}^\infty, \quad \text{or} \\ & \left(f(n)\right)_{n \in \N}, \end{align*}$ where $\N = \{1,2,3, \ldots \}$ denotes the set of natural numbers. In this text, we will usually write $\left \{a_n\right \}$ if we want to speak of the sequence as a whole and we will write $a_n$ if we are referring to a specific element, or “term”, in the sequence.

Consider the sequence $1, 2, 4, 8, 16, \dots .$ What number comes next?

$32$ $31$ $18$ there is no way to know

While there seems to be a pattern, without explicitly listing more terms (or giving a rule that defines the successive terms), it’s impossible to establish what the next term is!

In fact, here are two different sequences whose first 5 terms are the same as the example above:

Let $a_n = 2^{n-1}$ . Write down $a_1$ , $a_2$ , $a_3$ , $a_4$ , $a_5$ , and $a_6$ .

Use the formula to see: $\begin{align*} a_1 &= \answer[given]{1} & a_2 &= \answer[given]{2} & a_3 &= \answer[given]{4} & a_4 &= \answer[given]{8} & a_5 &= \answer[given]{16} & a_6 &= \answer[given]{32} \end{align*}$

Consider a circle with $n$ points on it. Let $b_n$ be the maximum number of regions produced by connecting these points with chords. Write down $b_1$ , $b_2$ , $b_3$ , $b_4$ , $b_5$ , and $b_6$ .

There is only one way to solve this problem: start drawing pictures and counting regions.

We see that $b_1 = \answer [given]{1}$
We see that $b_2 = \answer [given]{2}$
We see that $b_3 = \answer [given]{4}$
We see that $b_4 = \answer [given]{8}$
We see that $b_5 = \answer [given]{16}$
We see that $b_6 = \answer [given]{31}$

While we have made no real argument that these are the maximum number of regions, we believe that if the young mathematician draws more pictures they will be convinced.

From the two sequences we’ve just considered, the method of “finding a pattern” is not enough when dealing with sequences unless you understand exactly how the sequence was produced. However, having to define each term explicitly is quite cumbersome. In general, we want to define a sequence by specifying a rules that will allow us to write down any term that we want. There are two important ways that are generally used to describe a sequence:

Two common methods of representing sequences

We say that a sequence $\{a_n\}_{n=1}$ is described by an explicit formula the term $a_n$ is expressed as a function of $n$ only.

Just as real-valued functions were usually expressed by a formula, we will most often encounter sequences that can be expressed by a formula. We say that such sequences are defined explicitly, or that we have an explicit formula for the sequence.

Suppose $\{a_n\}_{n=1}$ is a sequence defined by the formula $a_n = 2n+3$ . Write down $a_1$ , $a_2$ , $a_3$ , $a_4$ , and $a_5$ .

By substituting $n=1, 2, 3, 4$ and $5$ into the formula above, we see: $\begin{align*} a_1 &= \answer[given]{5} & a_2 &= \answer[given]{7} & a_3 &= \answer[given]{9} & a_4 &= \answer[given]{11} & a_5 &= \answer[given]{13} \end{align*}$

Thus, the rule $a_n = 2n+3, n \geq 1$ thus generates the ordered list:

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

and we can use pattern recognition to generate more terms since we have a rule that defines the pattern.

A common misconception is to confuse the sequence with the rule for generating the sequence. The sequences $\{a_n\}$ and $\{b_n\}$ given by the rules $a_n = (-1)^n$ and $b_n = \cos (\pi \cdot n)$ are, despite appearances, different rules which give rise to the same sequence. These are just different names for the same object!

Suppose $(a_n)$ and $(b_n)$ are sequences starting at $1$ . These sequences are equal if for all natural numbers $n$ , we have $a_n = b_n$ .

More generally, two sequences $(a_n)$ and $(b_n)$ are equal if they have the same initial index $N$ and for every integer $n \geq N$ , the $n$ th terms have the same value, that is, $a_n = b_n \quad \text {for all $n \geq N$.}$

We say that a sequence $\{a_n\}_{n=1}$ is described by a recursive formula if the term $a_n$ is expressed as a function of $n$ and at least one of the previous terms in the sequence.

We start by defining the first few elements of the sequence, and then describe how later elements are computed in terms of previous elements.

Suppose that $\{a_n\}_{n=1}$ is a sequence defined by the formula $a_n = a_{n-1}+2$ , where $a_1 = 5$ . Write down $a_2$ , $a_3$ , $a_4$ , and $a_5$ .

Substituting in $n=2$ gives:

$a_2 = a_{\answer [given]{1}}+2 = \answer [given]{5}+2 = \answer [given]{7}$ We can now plug in $n=3$ and use the previous result for $a_2$ to find $a_3$ : $a_3 = a_{\answer [given]{2}}+2 = \answer [given]{7}+2 = \answer [given]{9}$ Continuing, we find $a_4 = \answer [given]{11}$ and $a_5 = \answer [given]{13}$ .

Thus, the rule $a_n = a_{n-1}+2, n \geq 1$ thus generates the ordered list:

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

Note that both the explicit formula and recursive formula in the previous examples seem to generate the same list of numbers. By writing out more and more terms, the young mathematician will find that it indeed seems like these seemingly different rules generate the same sequence!

The idea of “recognizing a pattern” and using it to generate more terms for the above example can be made more mathematically explicit through the notion of mathematical induction. The young mathematician may hypothesize that based on the pattern in the recursive formula:

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

the explicit rule $a_n = 2n+3$ for $n \geq 1$ generates the same sequence, and may prove beyond doubt that this is indeed the case by using induction. We leave it to the curious young mathematician to research and explore this idea further.

Two important types of sequences

The previous example of a sequence is actually an example of a very common type of sequence called an arithmetic sequence .

An arithmetic sequence (sometimes called an arithmetic progression) is a sequence for which the difference between subsequent elements is constant.

Here is an example of an arithmetic sequence.

This sequence is given explicitly by the function $a_n=\answer [given]{4n-9}$ , or recursively by the rule $a_1 = \answer [given]{-5}$ and $a_{n+1} = a_n + \answer [given]{4}$ . The difference between subsequent elements in this sequence is always four.

In general, an arithmetic sequence in which subsequent terms differ by $m$ can be written as $a_n = m (n-1) + a_1.$ Alternatively, we could describe an arithmetic sequence recursively, by giving a starting value $a_1$ , and using the rule that $a_{n} = a_{n-1} + m$ . You should check that this general statement holds for our two previous examples!

Why are arithmetic sequences called arithmetic? Note that every term is the arithmetic mean or average of its two neighbors. The arithmetic mean of two numbers $a$ and $b$ is defined to be $\frac {a+b}{2}$ .

A second family of sequences we consider are “geometric” sequences. These will play an important role later on, so we start with a definition:

A geometric sequence (sometimes called a geometric progression) is a sequence for which the ratio between subsequent elements is constant.

Here is an example of a geometric sequence:

This sequence is given explicitly by the function $a_n=\answer [given]{10\cdot 3^{n-1}}$ , or recursively by the rule $a_1 = \answer [given]{10}$ and $a_{n+1} = \answer [given]{3}\cdot a_n$ . The ratio between any subsequent elements of our sequence is three.

A geometric sequence can also decrease as it progresses.

Here is an example of a geometric sequence:

This sequence is given by the function $a_n=\answer [given]{\left (\frac {7}{5}\right )\cdot \left (\frac {1}{2}\right )^{n-1}}$ , or the recursive rule $a_1 = \answer [given]{\frac {7}{5}}$ and $a_{n+1} = \answer [given]{\left (\frac {1}{2}\right )}\cdot a_n$ . The ratio between subsequent terms of this sequence is always one half.

In general, a geometric sequence $\{a_n\}_{n=0}$ in which the ratio between subsequent terms is $r$ can be written as $a_n = a_0 \cdot r^{n-1}.$ Alternatively, we could describe a geometric sequence recursively, by giving a starting value $a_0$ , and using the rule that $a_{n} = r \cdot a_{n-1}$ . As usual, you should check that these general rules hold for the specific examples we’ve considered!

Why are geometric sequences called geometric? Note that every term is the geometric mean of its two neighbors. The geometric mean of two numbers $a$ and $b$ is defined to be $\sqrt {ab}$ .

Generating new sequences from other sequences

Once we have defined a given sequence, we can define new sequences using it. This is an absolutely fundamental idea that will appear again and again later!

Suppose that $\{a_n\}_{n=1}$ is defined by the rule:

$a_n = 3n-1$

We are going to build new sequences from this one, so let’s write out some terms in the sequence $\{a_n\}$ :

$\begin{align*} a_1 &= \answer[given]{2} & a_2 &= \answer[given]{5} & a_3 &= \answer[given]{8} & a_4 &= \answer[given]{11} & a_5 &= \answer[given]{14} & a_6 &= \answer[given]{17} \end{align*}$

Define a new sequence: $\{b_n\}_{n=1}$ by the rule:

$b_n = \frac {a_{n+1}}{a_n}$ Write out the first five terms in this new sequence.

Starting with $n=1$ we find:

$b_1 = \frac {a_{\answer {2}}}{a_{\answer {1}}} = \answer [given]{\frac {5}{2}}$

Continuing in the same way, we find:

$\begin{align*} b_2 &= \answer[given]{\frac{8}{5}} & b_3 &= \answer[given]{\frac{11}{8}} & b_4 &= \answer[given]{\frac{14}{11}} & b_5 &= \answer[given]{\frac{17}{14}} & \end{align*}$

Define another new sequence: $\{c_n\}_{n=1}$ by the rule:

$c_n = \sqrt [n]{a_n}$ Write out the first five terms in this new sequence.

Starting with $n=1$ we find:

$c_1 = \sqrt [1]{a_1} = \answer [given]{2}$

Continuing in the same way, we find:

$\begin{align*} c_2 &= \answer[given]{\sqrt[2]{5}} & c_3 &= \answer[given]{\sqrt[3]{8}} & c_4 &= \answer[given]{\sqrt[4]{11}} & c_5 &= \answer[given]{\sqrt[5]{14}} & \end{align*}$

Define another new sequence: $\{s_n\}_{n=1}$ by the rule:

$s_n = \sum _{k=1}^n a_k$ Write out the first five terms in this new sequence.

Recall that the notation $\sum _{k=1}^n a_k$ is shorthand notation used to represent the sum: $a_1+a_2+\ldots a_n$

Starting with $n=1$ we find:

$s_1 = a_1 = \answer [given]{2}$

Continuing in the same way, we find:

$\begin{align*} s_2 &= a_1 +a_2 = \answer[given]{7} \\ s_3 &= a_1 +a_2 + a_3 = \answer[given]{15} \\ s_4 &= a_1 +a_2 +a_3 +a_4= \answer[given]{26} \\ s_5 &= a_1 +a_2 +a_3+a_4+a_5= \answer[given]{40} \end{align*}$ Note that there are 2 ways to compute each of the terms above. One way is to perform the explicit addition each time, but the clever young mathematician may notice that there is a faster way. For instance, if we have already computed $s_3$ , we may notice:

The astute young mathematician may go as far as to notice that in general:

so that in this example, where $a_n = 3n-1$ , we have a recursive formula for $\{s_n\}_{n=1}$ :

$s_n = s_{n-1} + (3n-1), \qquad s_1 =2$

With more work, an explicit formula may also be developed:

$s_n = \frac {3n^2+n}{2}$

It can be shown that the recursive rule $s_n = s_{n-1} + (3n-1), \qquad s_1 =2$ and the explicit formula $s_n = \frac {3n^2+n}{2} , n \geq 1$ represent the same sequence. To do this, we must verify first that the sequences start at the same value. Indeed, by setting $n=1$ into the explicit formula, we find $s_1 = \answer [given]{2}$ . To proceed, we can show that the sequence given by the explicit formula also satisfies the recursive one. We do this by taking the explicit formula and substituting it into the recursive one.

For $n \geq 2$ , by setting $s_n = \frac {3n^2+n}{2}$ , we find $s_{n-1} = \frac {3(\answer {n-1})^2+(\answer {n-1})}{2}$ , and after a little algebra: $s_{n-1} = \frac {3n^2-5n+2}{2}$ . Thus, we can check whether this satisfies $s_n = s_{n-1} + (3n-1)$ :

$\begin{align*} s_{n-1} + (3n-1) = \frac{3n^2-5n+2}{2} +3n-1 \\ &= \frac{3n^2-5n+2}{2} +(3n-1) \cdot \frac{2}{2} \\ &= \frac{3n^2-5n+2}{2} + \frac{6n-2}{2} \\ &= \frac{3n^2+n}{2} \end{align*}$

This is precisely the expression for $s_n$ !

Note that establishing that the sequences start at the same value is important here. The general philosophy here was to show that the first term in each sequence is the same, and the above computations verify that for any term with $n \geq 2$ , both rules generate the same result. Had we specified a different starting value for the recursive formula, the rule $s_n = \frac {3n^2+n}{2}$ would still satisfy the recursive relationship $s_n = s_{n-1} + (3n-1)$ , but each expression would generate a different list of numbers!

The sequences in the previous example will all play an important role in the development that follows. We will see how they arise in the context of answering a fundamental question introduced in the next section, but it is worth mentioning them now as new sequences that can be constructed from a given sequence!

“Obvious” is the most dangerous word in mathematics” -E.T. Bell