Sequences

$\newenvironment {prompt}{}{} \newcommand {\ungraded }[0]{} \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}}}\hspace {0in}} \newcommand {\point }[1]{\left (#1\right )} \newcommand {\pt }[1]{\mathbf {#1}} \newcommand {\Lim }[2]{\lim _{\point {#1} \to \point {#2}}} \DeclareMathOperator {\proj }{\mathbf {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 }$

We investigate sequences.

A researcher wants to study how the the concentration of methane present in the atmosphere changes over time. To chronicle the data, the researcher takes a measurement every day and records the data in a table.

A college student wants to begin preparing to pay back student loans before graduating. Starting as a freshman, the student puts $100 each month into a high yield savings account that pays an annual rate of return of $1.85\%$ . At the beginning of every month, the student records the amount of money in the account.

In the early thirteenth century, Leonardo Pisano Bigollo, who has since come to be known by his nickname of Fibonacci, posed the following question:

If a pair of rabbits is placed in an enclosed area, how many rabbits will have been born at any month in the future if we assume that every month a pair of rabbits produces another pair, and that rabbits begin to bear young two months after their birth?

While these scenarios may seem unrelated on the surface, they have something in common; each scenario can be modeled by a sequence.

We start with some formality before discussing more practical matters involving sequences.

The definition of a sequence

A real-valued sequence is a function whose domain is an interval of integers $\{n_0,n_{0+1},n_{0+2}, \ldots \}$ and whose range is a subset of the real numbers.

We denote a sequence by

$\begin{align*} f : \{n_0,n_{0+1},n_{0+2}, \ldots\} & \to \R \\ n &\mapsto f(n) \end{align*}$

where the first line indicates the domain and range and the second line gives the rule that defines the terms in the sequence.

Suppose that the domain of a sequence is the set of natural numbers $\{1,2,3,\ldots \}$ , which we denote by $\N$ and the sequence maps each natural number to two times itself. We would write $\begin{align*} f : \N & \to \R \\ n &\mapsto 2n \end{align*}$

We can denote this more succinctly using the formula $f(n)=2n$ .

Most of the time, we take $n_0=0$ or $n_0=1$ ; that is, our domain will either be $\{0,1,2,\ldots \}$ , or $\{1,2,3,\ldots \}$ , respectively. We also take the domain of a sequence to be an infinite interval, but other texts might consider sequences whose domain is finite. In this text, we generally consider sequences whose domain is an infinite subset of the natural numbers, and unless otherwise specified, the domain of a sequence will have a smallest element and include all larger natural numbers.

Thus, we can represent sequences of interest as an ordered list of real numbers, where there is an assumed smallest starting index. For instance, returning to the question posed by Fibonacci, we can keep track of the number of rabbits present at the start of the $n$ -th month in a table.

$\begin {array}{| c | c | c | c | c | c| c| c| c| } \hline \textrm {Month} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & \textrm { and so on} \\ \hline \textrm {Number of Rabbits} & 1 & 1 & 3 & 5 & 8 &13 &21 & \textrm { and so on} \\ \hline \end {array}$

We can more succinctly denote this by arranging the number of rabbits in the ordered list

$1,1,2,3,5,8,13,21, \ldots$

where it is understood that the first number in the list is the number of rabbits at the start of month $1$ , the second number in the list is the number of rabbits at the start of month $2$ , and so on. The dots “…” signify that the list keeps 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=n_0}$ will be used to denote the infinite ordered list of numbers below.

$a_{n_0}, a_{n_0+1}, a_{n_0+2}, \ldots$

The subscript in the above notation is called the index and describes how we reference the first term. In many instances, we index sequences starting at $n_0=0$ or $n_0=1$ . When $n_0=0$ , the list looks like this:

$a_0,a_1,a_2, \ldots ,$

and when $n_0=1$ , the list is denoted below.

$a_1,a_2,a_3, \ldots$

While we usually prefer our starting index to be $0$ or $1$ , we would like to have the freedom to make other choices should it be convenient and this notation allows us that flexibility.

Many authors denote sequences using other notation. Some other common ones you may see are listed here. $\begin{align*} &a_n = f(n), n \geq 1 \\ & \left\{a_n\right\}_{n=1}^\infty, \\ & \left(f(n)\right)_{n=1}^\infty \\ \end{align*}$

In this text, we will use $\left \{a_n\right \}_{n=n_0}$ to refer to the sequence and the notation $a_n$ to refer to a specific term in the sequence.

An important, yet subtle note, two different sequences can be represented by the same ordered list of numbers. For example, the sequences $f_1$ and $f_2$ below

$\begin {array}{rl} f_1 : \{0,1,2,\ldots \} & \to \R \qquad \textrm { where } f_1(n) =2(n+1) \\ f_2 : \{1,2,3, \ldots \} & \to \R \qquad \textrm { where } f_2(n) =2n \\ \end {array}$

both can be represented by the ordered list $2, 4, 6, 8, 10, \ldots$ , but since the domains of $f_1$ and $f_2$ are different, they are not the same sequence even though they model the same phenomenon.

Let’s now briefly summarize what has been discussed so far.

A sequence is a function that can be represented by an ordered list. The notation $\{a_n\}_{n=n_0}$ will be used to denote the ordered list whose first term is $a_{n_0}$ , whose second term is $a_{n_0+1}$ , and so on.

In the instance where $n_0=1$ , we denote the sequence by $\{a_n\}_{n=1}$ and can represent the sequence by the ordered list of numbers below.

$a_1, a_2, a_3, \ldots$

Exploring sequences

We now explore an interesting scenario that highlights an important idea while working with sequences.

Consider the sequence represented by the list of numbers below. $1, 2, 4, 8, 16, \dots .$ Which number comes next? $32$ $31$ $18$ There is no way to know.

While there seems to be a pattern, without giving a rule that defines the successive terms, it’s impossible to establish what the next one is.

To explore further, here are two different sequences whose first five 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$ .

By using the given formula, we find the following. $\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$ .

A good way to approach this problem is to 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 reader 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 write out all of the infinitely many terms is impossible to do! In general, we want to define a sequence by specifying something that will allow us to write down any term that we want.

Two common methods of representing the terms of a sequence

Consider the examples presented at the beginning of the section. While it doesn’t seem likely that we can find a good pattern to describe the concentration of methane present in the atmosphere over time, there are actual patterns that can be found that predict future terms in the financial scenario as well as Fibonacci’s example.

Explicit formulas

Just as real-valued functions were usually expressed by a formula $f(x)$ , we often encounter sequences that can be expressed by a formula $f(n)$ . When all terms $a_n$ in a sequence are described by a formula that only involves $n$ , we say the sequence is defined by an explicit formula. It is fairly easy to work with explicit formulas.

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

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*}$

Similarly, we find that $a_{500} = 2(500)+3 = \answer {1003}$ .

Note that the formula $a_n = 2n+3, n \geq 1$ generates the ordered list

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

and there is certainly a suggested pattern. Now that we have an actual rule that gives the terms in the sequence, we can use it to verify that the pattern holds.

Recursive formulas

Sometimes, we have to know previous terms in a sequence in order to find the terms that come next. Terms in the Fibonacci sequence stated in the introduction are easily found this way. For instance, by taking $a_1=1$ and $a_2=1$ , we find the next several terms.

$\begin{align*} a_3 = a_2+a_1 & = 1+1=2 \\ a_4 = a_3+a_2 &= 2+1 = 3 \\ a_5 = a_4+a_3 &= 3+2 = 5 \\ \end{align*}$

When we have an equality that relates the next term in a sequence to the previous ones, we say that we have a recursive formula for the sequence. Let’s see another example.

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

Substituting in $n=2$ gives the following.

$a_2 = a_{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_{2}+2 = \answer [given]{7}+2 = \answer [given]{9}$ Continuing, we find $a_4 = \answer [given]{11}$ and $a_5 = \answer [given]{13}$ .

Note here that the rule $a_{n+1} = a_n+2, n \geq 1$ generates the ordered list below.

$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. While writing out more and more terms suggests this is the case, it is not a sufficient argument to conclude that both rules generate the same sequence.

In order to verify that any term $a_n$ in the sequence whose terms are given by the formula $a_n = 2n+3$ is equal to the term $a_n$ obtained from the recursive relationship $a_{n+1}=a_n+2, a_1=5$ , we first note that the first term in both sequences, $a_1$ is the same. Now, we proceed as follows.

We start with the formula $a_n=2n+3$ and use this formula to write down an expression for $a_{n+1}$ .
We verify that, after some algebra, the expression for $a_{n+1}$ satisfies the recursive relationship $a_{n+1} = a_n+2$ .

Let’s get started!

Since $a_n=2n+3$ , we have that $a_{n+1} = 2\left (\answer [given]{n+1}\right )+3$ .
Notice that $a_n = 2n+3$ , so we want to try to simplify the expression above and isolate $2n+3$ . Letting $a_n = 2n+3$ , we find the following.

$\begin{align*} a_{n+1} &= 2\left(n+1\right)+3 \\ &= 2n+5 \\ &= \left(2n+3\right) +2 \\ &= a_n+2 \end{align*}$

The term $a_n = 2n+3$ satisfies the requirement $a_{n+1}=a_n+2$ , so the different looking formulas $a_n = 2n+3, n \geq 1$ and $a_{n+1}=a_n+2, a_1=5$ actually represent the same sequence.

Generating new sequences from other sequences

Once we have defined a given sequence, we can make new sequences from it. Some of the new sequences we can generate allow us to answer important questions about the original sequence. Many of the results we obtain later on will require that we analyze sequences that we generate from others. For now we will look at a few of these important sequences in the context of specific examples.

Suppose that $\{a_n\}_{n=1}$ is defined by the explicit formula below.

$a_n = 3n-1, n \geq 1$

Write out the first six terms in the sequence $\{a_n\}$ .

The first few terms can be computed from the formula. $\begin{align*} a_1 &= 3(1)-1=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*}$

We can make new sequences from this sequence. Here are a few examples.

By noting that none of the terms in the last sequence are $0$ , we define a new sequence $\{b_n\}_{n=1}$ by the rule below. $b_n = \frac {a_{n+1}}{a_n}.$ Write out the first five terms in this new sequence.

Starting with $n=1$ we find the next few terms.

$b_1 = \frac {a_2}{a_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*}$

Since none of the terms in the original sequence $\{a_n\}$ were negative, we define another new sequence $\{c_n\}_{n=1}$ by the rule below. $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 &= 5^{1/2} & c_3 &= \answer[given]{8^{1/3}} & c_4 &= \answer[given]{11^{1/4}} & c_5 &= \answer[given]{14^{1/5}} \end{align*}$

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

$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 the next few terms.

$\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*}$

The following observation will be important later on, so we offer it here to give the reader a little exposure. Note that there are two ways to compute each of the terms above. One way is to perform the explicit addition each time, but the clever reader may notice that there is a faster way. For instance, if we have already computed $s_3$ , there is a way to use it to find $s_4$ quickly.

Of course, there is a more general observation.

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$ It can be shown that the recursive rule $s_n = s_{n-1} + (3n-1), s_1 =2$ and the explicit formula $s_n = \frac {3n^2+n}{2} , n \geq 1$ represent the same sequence. We leave this to the curious reader as an exercise.

In the preceding example, there were many new sequences that we could form from a given one. As it turns out, these particular new sequences play an important role in answering questions about the original sequence. We will explore these questions in later sections.