2.1: Definitions

\( \def\d{\displaystyle}\)
\( \newcommand{\f}[1]{\mathfrak #1}\)
\( \newcommand{\s}[1]{\mathscr #1}\)
\( \def\N{\mathbb N}\)
\( \def\B{\mathbf{B}}\)
\( \def\circleA{(-.5,0) circle (1)}\)
\( \def\Z{\mathbb Z}\)
\( \def\circleAlabel{(-1.5,.6) node[above]{$A$}}\)
\( \def\Q{\mathbb Q}\)
\( \def\circleB{(.5,0) circle (1)}\)
\( \def\R{\mathbb R}\)
\( \def\circleBlabel{(1.5,.6) node[above]{$B$}}\)
\( \def\C{\mathbb C}\)
\( \def\circleC{(0,-1) circle (1)}\)
\( \def\F{\mathbb F}\)
\( \def\circleClabel{(.5,-2) node[right]{$C$}}\)
\( \def\A{\mathbb A}\)
\( \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\)
\( \def\X{\mathbb X}\)
\( \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\)
\( \def\E{\mathbb E}\)
\( \def\O{\mathbb O}\)
\( \def\U{\mathcal U}\)
\( \def\pow{\mathcal P}\)
\( \def\inv{^{-1}}\)
\( \def\nrml{\triangleleft}\)
\( \def\st{:}\)
\( \def\~{\widetilde}\)
\( \def\rem{\mathcal R}\)
\( \def\sigalg{$\sigma$-algebra }\)
\( \def\Gal{\mbox{Gal}}\)
\( \def\iff{\leftrightarrow}\)
\( \def\Iff{\Leftrightarrow}\)
\( \def\land{\wedge}\)
\( \def\And{\bigwedge}\)
\( \def\entry{\entry}\)
\( \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\)
\( \def\Vee{\bigvee}\)
\( \def\VVee{\d\Vee\mkern-18mu\Vee}\)
\( \def\imp{\rightarrow}\)
\( \def\Imp{\Rightarrow}\)
\( \def\Fi{\Leftarrow}\)
\( \def\var{\mbox{var}}\)
\( \def\Th{\mbox{Th}}\)
\( \def\entry{\entry}\)
\( \def\sat{\mbox{Sat}}\)
\( \def\con{\mbox{Con}}\)
\( \def\iffmodels{\bmodels\models}\)
\( \def\dbland{\bigwedge \!\!\bigwedge}\)
\( \def\dom{\mbox{dom}}\)
\( \def\rng{\mbox{range}}\)
\( \def\isom{\cong}\)
\(\DeclareMathOperator{\wgt}{wgt}\)
\( \newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}}\)
\( \newcommand{\va}[1]{\vtx{above}{#1}}\)
\( \newcommand{\vb}[1]{\vtx{below}{#1}}\)
\( \newcommand{\vr}[1]{\vtx{right}{#1}}\)
\( \newcommand{\vl}[1]{\vtx{left}{#1}}\)
\( \renewcommand{\v}{\vtx{above}{}}\)
\( \def\circleA{(-.5,0) circle (1)}\)
\( \def\circleAlabel{(-1.5,.6) node[above]{$A$}}\)
\( \def\circleB{(.5,0) circle (1)}\)
\( \def\circleBlabel{(1.5,.6) node[above]{$B$}}\)
\( \def\circleC{(0,-1) circle (1)}\)
\( \def\circleClabel{(.5,-2) node[right]{$C$}}\)
\( \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\)
\( \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\)
\( \def\ansfilename{practice-answers}\)
\( \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\)
\( \renewcommand{\bar}{\overline}\)
\( \newcommand{\card}[1]{\left| #1 \right|}\)
\( \newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}\)
\( \newcommand{\lt}{<}\)
\( \newcommand{\gt}{>}\)
\( \newcommand{\amp}{&}\)

\( \newcommand{\hexbox}[3]{
  \def\x{-cos{30}*\r*#1+cos{30}*#2*\r*2}
  \def\y{-\r*#1-sin{30}*\r*#1}
  \draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
  \draw (\x,\y) node{#3};
}\)

\(\renewcommand{\bar}{\overline}\)
\(\newcommand{\card}[1]{\left| #1 \right|}\)
\(\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}\)
\(\newcommand{\lt}{<}\)
\(\newcommand{\gt}{>}\)
\(\newcommand{\amp}{&}\)

Investigate!

What comes next:

\begin{equation*} 1, ~~11, ~~21, ~~1211, ~~111221, ~~312211, ~~\ldots \end{equation*}

A sequence is simply an ordered list of numbers. For example, here is a sequence: 0, 1, 2, 3, 4, 5, …. This is different from the set \(\N\) because, while the sequence is a complete list of every element in the set of natural numbers, in the sequence we very much care what order the numbers come in. For this reason, when we use variables to represent terms in a sequence they will look like this:

\begin{equation*} a_0, a_1, a_2, a_3, \ldots \end{equation*}

To refer to the entire sequence at once, we will write \((a_n)_{n\in\N}\) or \((a_n)_{n\ge 0}\text{,}\) or sometimes if we are being sloppy, just \((a_n)\) (in which case we assume we start the sequence with \(a_0\)).

We might replace the \(a\) with another letter, and sometimes we omit \(a_0\text{,}\) starting with \(a_1\text{,}\) in which case we would use \((a_n)_{n \ge 1}\) to refer to the sequence as a whole. The numbers in the subscripts are called indices (the plural of index).

While we often just think of sequences as an ordered list of numbers, they really are a type of function. Specifically, the sequence \((a_n)_{n\ge 0}\) is a function with domain \(\N\) where \(a_n\) is the image of the natural number \(n\text{.}\) Later we will manipulate sequences in much the same way you have manipulated functions in algebra or calculus. We can shift a sequence up or down, add two sequences, or ask for the rate of change of a sequence. These are done exactly as you would for functions.

That said, while keeping the rigorous mathematical definition in mind is helpful, we often describe sequences by writing out the first few terms.

Example \(\PageIndex{1}\)

Can you find the next term in the following sequences?

1. \(7,7,7,7,7, \ldots\)
2. \(3, -3, 3, -3, 3, \ldots\)
3. \(1, 5, 2, 10, 3, 15, \ldots\)
4. \(1, 2, 4, 8, 16, 32, \ldots\)
5. \(1, 4, 9, 16, 25, 36, \ldots\)
6. \(1, 2, 3, 5, 8, 13, 21, \ldots\)
7. \(1, 3, 6, 10, 15, 21, \ldots\)
8. \(2, 3, 5, 7, 11, 13, \ldots\)
9. \(3, 2, 1, 0, -1, \ldots\)
10. \(1, 1, 2, 6, \ldots\)

Solution

No you cannot. You might guess that the next terms are:

1. \(7\)
2. \(-3\)
3. \(4\)
4. 64
5. 49
6. 34
7. 28
8. 17
9. \(-2\)
10. \(24\)

In fact, those are the next terms of the sequences I had in mind when I made up the example, but there is no way to be sure they are correct.

Still, we will often do this. Given the first few terms of a sequence, we can ask what the pattern in the sequence suggests the next terms are.

Given that no number of initial terms in a sequence is enough to say for certain which sequence we are dealing with, we need to find another way to specify a sequence. We consider two ways to do this:

Closed formula

A closed formula for a sequence \((a_n)_{n\in\N}\) is a formula for \(a_n\) using a fixed finite number of operations on \(n\text{.}\) This is what you normally think of as a formula in \(n\text{,}\) just like if you were defining a function in terms of \(n\) (because that is exactly what you are doing).

Recursive definition

A recursive definition (sometimes called an inductive definition) for a sequence \((a_n)_{n\in\N}\) consists of a recurrence relation: an equation relating a term of the sequence to previous terms (terms with smaller index) and an initial condition: a list of a few terms of the sequence (one less than the number of terms in the recurrence relation).

It is easier to understand what is going on here with an example:

Example \(\PageIndex{2}\)

Here are a few closed formulas for sequences:

• \(a_n = n^2\text{.}\)
• \(\d a_n = \frac{n(n+1)}{2}\text{.}\)
• \(\d a_n = \frac{\left(\frac{1 + \sqrt 5}{2}\right)^n - \left(\frac{1 + \sqrt 5}{2}\right)^{-n}}{5}\text{.}\)

Note in each case, if you are given \(n\text{,}\) you can calculate \(a_n\) directly: just plug in \(n\text{.}\) For example, to find \(a_3\) in the second sequence, just compute \(a_3 = \frac{3(3+1)}{2} = 6\text{.}\)

Here are a few recursive definitions for sequences:

• \(a_n = 2a_{n-1}\) with \(a_0 = 1\text{.}\)
• \(a_n = 2a_{n-1}\) with \(a_0 = 27\text{.}\)
• \(a_n = a_{n-1} + a_{n-2}\) with \(a_0 = 0\) and \(a_1 = 1\text{.}\)

In these cases, if you are given \(n\text{,}\) you cannot calculate \(a_n\) directly, you first need to find \(a_{n-1}\) (or \(a_{n-1}\) and \(a_{n-2}\)). In the second sequence, to find \(a_3\) you would take \(2a_2\text{,}\) but to find \(a_2 = 2a_1\) we would need to know \(a_1 = 2a_0\text{.}\) We do know this, so we could trace back through these equations to find \(a_1 = 54\text{,}\) \(a_2 = 108\) and finally \(a_3 = 216\text{.}\)

Investigate!

You have a large collection of \(1\times 1\) squares and \(1\times 2\) dominoes. You want to arrange these to make a \(1 \times 15\) strip. How many ways can you do this?

1. Start by collecting data. How many length \(1\times 1\) strips can you make? How many \(1\times 2\) strips? How many \(1\times 3\) strips? And so on.
2. How are the \(1\times 3\) and \(1 \times 4\) strips related to the \(1\times 5\) strips?
3. How many \(1\times 15\) strips can you make?
4. What if I asked you to find the number of \(1\times 1000\) strips? Would the method you used to calculate the number fo \(1 \times 15\) strips be helpful?

You might wonder why we would bother with recursive definitions for sequences. After all, it is harder to find \(a_n\) with a recursive definition than with a closed formula. This is true, but it is also harder to find a closed formula for a sequence than it is to find a recursive definition. So to find a useful closed formula, we might first find the recursive definition, then use that to find the closed formula.

This is not to say that recursive definitions aren't useful in finding \(a_n\text{.}\) You can always calculate \(a_n\) given a recursive definition, it might just take a while.

Example \(\PageIndex{3}\)

Find \(a_6\) in the sequence defined by \(a_n = 2a_{n-1} - a_{n-2}\) with \(a_0 = 3\) and \(a_1 = 4\text{.}\)

Solution

We know that \(a_6 = 2a_5 - a_4\text{.}\) So to find \(a_6\) we need to find \(a_5\) and \(a_4\text{.}\) Well

\begin{equation*} a_5 = 2a_4 - a_3 \qquad \text{and} \qquad a_4 = 2a_3 - a_2, \end{equation*}

so if we can only find \(a_3\) and \(a_2\) we would be set. Of course

\begin{equation*} a_3 = 2a_2 - a_1 \qquad \text{and} \qquad a_2 = 2a_1 - a_0, \end{equation*}

so we only need to find \(a_1\) and \(a_0\text{.}\) But we are given these. Thus

\begin{align*} a_0 & = 3\\ a_1 & = 4\\ a_2 & = 2\cdot 4 - 3 = 5\\ a_3 & = 2\cdot 5 - 4 = 6\\ a_4 & = 2\cdot 6 - 5 = 7\\ a_5 & = 2\cdot 7 - 6 = 8\\ a_6 & = 2\cdot 8 - 7 = 9. \end{align*}

Note that now we can guess a closed formula for the \(n\)th term of the sequence: \(a_n = n+3\text{.}\) To be sure this will always work, we could plug in this formula into the recurrence relation:

\begin{align*} 2a_{n-1} - a_{n-2} & = 2((n-1) + 3) - ((n-2) + 3)\\ & = 2n + 4 - n - 1 \\ & = n + 3\\ & = a_n. \end{align*}

That is not quite enough though, since there can be multiple closed formulas that satisfy the same recurrence relation; we must also check that our closed formula agrees on the initial terms of the sequence. Since \(a_0 = 0 + 3 = 3\) and \(a_1 = 1+3 = 4\) are the correct initial conditions, we can now conclude we have the correct closed formula.

Finding closed formulas, or even recursive definitions, for sequences is not trivial. There is no one method for doing this. Just like in evaluating integrals or solving differential equations, it is useful to have a bag of tricks you can apply, but sometimes there is no easy answer.

One useful method is to relate a given sequence to another sequence for which we already know the closed formula.

Example \(\PageIndex{4}\)

Use the formulas \(T_n = \frac{n(n+1)}{2}\) and \(a_n = 2^n\) to find closed formulas for the following sequences.

1. \((b_n)\text{:}\) \(1, 2, 4, 7, 11, 16, 22, \ldots \text{.}\)
2. \((c_n)\text{:}\) \(3, 5, 9, 17, 33,\ldots \text{.}\)
3. \((d_n)\text{:}\) \(0, 2, 6, 12, 20, 30, 42,\ldots \text{.}\)
4. \((e_n)\text{:}\) \(3, 6, 10, 15, 21, 28, \ldots\text{.}\)
5. \((f_n)\text{:}\) \(0, 1, 3, 7, 15, 31, \ldots \text{.}\)
6. \((g_n)\) \(3, 6, 12, 24, 48, \ldots \text{.}\)
7. \((h_n)\text{:}\) \(6, 10, 18, 34, 66, \ldots \text{.}\)
8. \((j_n)\text{:}\) \(15, 33, 57, 87, 123, \ldots\text{.}\)

Solution

1. Before you say this is impossible, what we are asking for is simply to find a closed formula which agrees with all of the initial terms of the sequences. Of course there is no way to read into the mind of the person who wrote the numbers down, but we can at least do this.
2. The first few terms of \((T_n)_{n\ge 0}\) are \(0, 1, 3, 6, 10, 15, 21, \ldots\) (these are called the triangular numbers). The first few terms of \((a_n)_{n\ge 0}\) are \(1, 2, 4, 8, 16, \ldots\text{.}\) Let's try to find formulas for the given sequences:
3. \((1, 2, 4, 7, 11, 16, 22, \ldots)\text{.}\) Note that if subtract 1 from each term, we get the sequence \((T_n)\text{.}\) So we have \(b_n = T_n + 1\text{.}\) Therefore a closed formula is \(b_n = \frac{n(n+1)}{2} + 1\text{.}\) A quick check of the first few \(n\) confirms we have it right.
4. \((3, 5, 9, 17, 33, \ldots )\text{.}\) Each term in this sequence is one more than a power of 2, so we might guess the closed formula is \(c_n = a_n+1 = 2^n + 1\text{.}\) If we try this though, we get \(c_0 2^0 + 1 = 2\) and \(c_1 = 2^1 + 1 = 3\text{.}\) We are off because the indices are shifted. What we really want is \(c_n = a_{n+1}+1\) giving \(c_n = 2^{n+1} + 1\text{.}\)
5. (\(0, 2, 6, 12, 20, 30, 42,\ldots \)). Notice that all these terms are even. What happens if we factor out a 2? We get \((T_n)\text{!}\) More precisely, we find that \(d_n/2 = T_n\text{,}\) so this sequence has closed formula \(d_n = n(n+1)\text{.}\)
6. \((3, 6, 10, 15, 21, 28, \ldots)\text{.}\) These are all triangular numbers. However, we are starting with 3 as our initial term instead of as our third term. So if we could plug in 2 instead of 0 into the formula for \(T_n\text{,}\) we would be set. Therefore the closed formula is \(e_n = \frac{(n+2)(n+3)}{2}\) (where \(n+3\) came from \((n+2)+1\)). Thinking about sequences as functions, we are doing a horizontal shift by 2: \(e_n = T_{n+2}\) which would cause the graph to shift 2 units to the left.
7. \((0, 1, 3, 7, 15, 31, \ldots )\text{.}\) Try adding 1 to each term and we get powers of 2. You might guess this because each term is a little more than twice the previous term (the powers of 2 are exactly twice the previous term). Closed formula: \(f_n = 2^{n} - 1\text{.}\)
8. \((3, 6, 12, 24, 48, \ldots )\text{.}\) These numbers are also doubling each time, but are also all multiples of 3. Dividing each by 3 gives 1, 2, 4, 8, …. Aha. We get the closed formula \(g_n = 3\cdot 2^{n}\text{.}\)
9. \((6, 10, 18, 34, 66, \ldots )\text{.}\) To get from one term to the next, we almost double each term. So maybe we can relate this back to \(2^n\text{.}\) Yes, each term is 2 more than a power of 2. So we get \(h_n = 2^{n+2} + 2\) (the \(n+2\) is because the first term is 2 more than \(2^2\text{,}\) not \(2^0\)). Alternatively, we could have related this sequence to the second sequence in this example: starting with 3, 5, 9, 17, … we see that this sequence is twice the terms from that sequence. That sequence had closed formula \(c_n = 2^{n+1} + 1\text{.}\) Our sequence here would be twice this, so \(h_n = 2(2^n + 1)\text{,}\) which is the same as we got before.
10. \((15, 33, 57, 87, 123, \ldots)\text{.}\) Try dividing each term by 3. That gives the sequence \(5, 11, 19, 29, 41,\ldots\text{.}\) Now add 1: \(6, 12, 20, 30, 42, \ldots\text{,}\) which is \((d_n)\) in this example, except starting with 6 instead of 0. So let's start with the formula \(d_n= n(n+1)\text{.}\) To start with the 6, we shift: \((n+2)(n+3)\text{.}\) But this is one too many, so subtract 1: \((n+2)(n+3) - 1\text{.}\) That gives us our sequence, but divided by 3. So we want \(j_n = 3((n+2)(n+3) - 1)\text{.}\)