\(\def\d{\displaystyle} \def\course{Math 228} \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}}} \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}{ & } \)

Section2.1Basics

Investigate!16

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}\), 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\), starting with \(a_1\), 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\). Later we will manipulate sequences in much the same way you have manipulated functions in algebra or calculus. We shift a sequence up or down, add two sequences, or ask for the rate of change of a sequence. These are done exactly has 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.

Example2.1.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

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\). This is what you normally think of as a formula in \(n\), 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:

Example2.1.2

Here are a few closed formulas for sequences:

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

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

Here are a few recursive definitions for sequences:

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

In these cases, if you are given \(n\), 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\), but to find \(a_2 = 2a_1\) we would need to know \(a_1 = 2a_0\). We do know this, so we could trace back through these equations to find \(a_1 = 54\), \(a_2 = 108\) and finally \(a_3 = 216\).

Investigate!17

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?

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.

How are the \(1\times 3\) and \(1 \times 4\) strips related to the \(1\times 5\) strips?

How many \(1\times 15\) strips can you make?

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\). You can always calculate \(a_n\) given a recursive definition, it might just take a while.

Example2.1.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\).

Solution

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.

Example2.1.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)\): \(1, 2, 4, 7, 11, 16, 22, \ldots \).

  2. \((c_n)\): \(3, 5, 9, 17, 33,\ldots \).

  3. \((d_n)\): \(0, 2, 6, 12, 20, 30, 42,\ldots \).

  4. \((e_n)\): \(3, 6, 10, 15, 21, 28, \ldots\).

  5. \((f_n)\): \(0, 1, 3, 7, 15, 31, \ldots \).

  6. \((g_n)\) \(3, 6, 12, 24, 48, \ldots \).

  7. \((h_n)\): \(6, 10, 18, 34, 66, \ldots \).

  8. \((j_n)\): \(15, 33, 57, 87, 123, \ldots\).

Solution

Subsection2.1.1Exercises

1

Find the closed formula for each of the following sequences by relating them to a well know sequence. Assume the first term given is \(a_1\).

  1. \(2, 5, 10, 17, 26, \ldots\)
  2. \(0, 2, 5, 9, 14, 20, \ldots\)
  3. \(8, 12, 17, 23, 30,\ldots\)
  4. \(1, 5, 23, 119, 719,\ldots\)
2

The Fibonacci sequence is \(0, 1, 1, 2, 3, 5, 8, 13, \ldots\) (where \(F_0 = 0\)).

  1. Give the recursive definition for the sequence.

  2. Write out the first few terms of the sequence of partial sums.

  3. Give a closed formula for the sequence of partial sums in terms of \(F_n\) (for example, you might say \(F_0 + F_1 + \cdots + F_n = 3F_{n-1}^2 + n\), although that is definitely not correct).

3

Consider the three sequences below. For each, find a recursive definition. How are these sequences related?

  1. \(2, 4, 6, 10, 16, 26, 42, \ldots\).
  2. \(5, 6, 11, 17, 28, 45, 73, \ldots\).
  3. \(0, 0 , 0 , 0 , 0 , 0 , 0 ,\ldots\).
4

Write out the first few terms of the sequence given by \(a_1 = 3\); \(a_n = 2a_{n-1} + 4\). Then find a recursive definition for the sequence \(10, 24, 52, 108, \ldots\).

5

Write out the first few terms of the sequence given by \(a_n = n^2 - 3n + 1\). Then find a closed formula for the sequence (starting with \(a_1\)) \(0, 2, 6, 12, 20, \ldots\).

6

Find a closed formula for the sequence with recursive definition \(a_n = 2a_{n-1} - a_{n-2}\) with \(a_1 = 1\) and \(a_2 = 2\).

7

Find a recursive definition for the sequence with closed formula \(a_n = 3 + 2n\). Bonus points if you can give a recursive definition in which makes use of two previous terms and no constants.