Skip to main content
Logo image

Discrete Math for Shockers

John Hammond

Section 4.1 Sequences and Series

The next mathematical object we’ll explore is an ordered collection. Unlike a set which is a loose collection of objects, for a sequence, order matters. For this reason, we can view a sequence simply as a function whose domain is the counting numbers. But since we will spend a lot of time in our mathematical career working with them (in this class and calc 2 for a start), we give sequences their own special notation.

Subsection

Definition 4.1.1. Sequences.

A sequence is a function from a subset of the integers (usually \(\{0, 1,2,3 \dots\}\)) to a set \(S\text{.}\) We use the notation \(a_n\) to denote the image of the integer \(n\text{,}\) and we call \(a_n\) the \(n\)-th term of the sequence.
We will often write the shorthand \(\{a_n\}\) to denote the complete sequence where \(n\in \mathbb{N}\text{.}\)
It’s helpful to remember that \(a_n\) is just a new shorthand for a function. You can think of \(a_n\) as \(a(n)\text{,}\) with \(a\) is name of the function (sequence) and \(n\) is the input variable.

Example 4.1.2.

Find \(a_1, a_2, a_3, a_4\) for the sequences:
  1. \(\displaystyle a_n = \frac{1}{n^2}\)
  2. \(\displaystyle a_n = 3\cdot 2^n\)
  3. \(\displaystyle a_n = -5 + 3n\)
Video / Answer.
Although there are many different types of sequences, two common ones we’ll encounter regularly in this course are given below:

Definition 4.1.3. Arithmetic and Geometric Sequences.

A arithmetic progression is a sequence of the form:
\begin{equation*} a, a+d, a+2d, a+3d, \dots, a+nd, \dots \end{equation*}
with the initial term \(a\) and the common difference \(d\text{.}\)
A geometric progression is a sequence of the form:
\begin{equation*} a, ar, ar^2, ar^3, \dots, ar^n, \dots \end{equation*}
with the initial term \(a\) and the common ratio \(r\text{.}\)
Notice that the arithmetic sequence is of the form \(a_n = a+nd\text{.}\) Since \(n\) is the variable and \(a \and d\) are constants, this is the form of a “\(y=mx + b\)”, so arithmetic sequences are the linear functions of sequences. The geometric on the other hand, is an exponential function.
The next type of sequences we encounter isn’t one we’ve encountered in the calculus courses. These sequences are defined in terms of themselves. Each value that is computed depends on the value that comes before it.

Definition 4.1.4. Recurrence Relations / Recursive Sequences.

A recurrence relation for a sequence \(\{a_n\}\) is an equation that expressions \(a_n\) in terms of previous terms.
A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation.
We can always think of a sequence as a function, so the recurrence \(a_n = a_{n-1} + a_{n-2}\) is the function:
            def a(n):
                return a(n-1) + a(n-1)
with infinite recursion.

Example 4.1.5. The Fibonacci Sequence.

The Fibonacci sequence \(F_0, F_1, F_2, \dots\) is defined by the recurrence:
\begin{equation*} F_n = F_{n-1} + F_{n-2} \text{ For } n \ge 2, \text{ where } F_0 = 0, F_1 = 1 \end{equation*}
Note that the Fibonacci sequence has both the recursive definition and a definition for the first two terms of the sequence.
Video / Answer.

Example 4.1.6.

Consider the recurrence \(a_n = -3 a_{n-1} + 4 a_{n-2}\text{.}\) Are the following sequences solutions to the recurrence?
  1. \(\displaystyle a_n = 0\)
  2. \(\displaystyle a_n = 1\)
  3. \(\displaystyle a_n = 2^n\)
  4. \(\displaystyle a_n = (-4)^n\)

Note 4.1.7.

A recurrence has a unique solution if it has initial data.
This would be a function defined with finite recursion, so the recurrence \(F_n = F_{n-1} + F_{n-2}\) with \(F_0 = 0\) and \(F_1=1\text{,}\) the Fibonacci sequence, is the function:
          def F(n):
              if n == 0:
                  return 0
              elif n == 1:
                  return 1
              else:
                  return F(n-1) + F(n-1)

Example 4.1.8.

Find the unique solution to each recurrence:
  1. \(a_n = 2a_{n-1} - 3\) with \(a_0 = -1\)
  2. \(a_n = 2n a_{n-1}\) with \(a_0 = 3\)
Video / Answer.

Note 4.1.9.

When finding the general form of a sequence, creativity is required.
Look for patterns within the sequence
  • Look for a common difference (arithmetic)
  • Look for a common ratio (geometric)
  • Do later terms depend on previous terms in a recursive way?
  • Are there cycles among the terms?
  • ...

Example 4.1.10.

Find a simple formula or rule that generates the terms of the sequence, and give the next three terms of the sequence.
  1. \(\displaystyle 7, 11, 15, 19, 23, 27, 31, \dots\)
  2. \(\displaystyle 1, 10, 11, 100, 101, 110, 111, 1000, \dots\)
  3. \(\displaystyle 1, 3, 15, 105, 945, 10395, 135135, \dots\)
  4. \(\displaystyle 2,4,16,256,65536, 4294957296, \dots\)
Now given a sequence, what happens if you add these values together? The following notation will be familiar from calculus.

Definition 4.1.11. Series.

Let \(\{a_n\}\) be a sequence. We define a series of the sequence to be the summation of some subset of the terms of the sequence. We denote the sum by a capital sigma with sub- and superscript information in the following conventional way:
\begin{equation*} \sum_{\text{index variable, lower bound}}^{\text{upper bound}} \text{(sequence rule in terms of index variable)} \end{equation*}
For example, the summation of terms from 0 to \(n\) is expressed:
\begin{equation*} \sum_{i=0}^n a_i = a_0 + a_1 + a_2 + \dots + a_{n-1} + a_n \end{equation*}

Example 4.1.12.

Find the value of the sum:
  1. \(\displaystyle \displaystyle \sum_{j=0}^8 (1 + (-1)^j)\)
  2. \(\displaystyle \displaystyle \sum_{k \in \{1, 3, 5\}} (k^2 + 2)\)
  3. \(\displaystyle \displaystyle \sum_{j=1}^2 \sum_{k=1}^5 (j-k) \)
  4. \(\displaystyle \displaystyle \sum_{j=1}^2 \sum_{k=1}^5 (k-j) \)
Video / Answer.

Example 4.1.13.

Verify the following formula for the sum of a geometric sequence, if \(r \not= 1\text{,}\)
\begin{equation*} \sum_{k=0}^n ar^k = \frac{a-ar^{n+1}}{1-r}\text{.} \end{equation*}
Video / Answer.

Example 4.1.14.

Show that
\begin{equation*} \sum_{j=1}^n (a_j - a_{j-1}) = a_n - a_0 \end{equation*}
Video / Answer.

Example 4.1.15.

Find a formula for the following sums, using the telescoping example:
  1. Using the sequence \(a_n=n^2\text{,}\) find a formula for the sum \(\displaystyle \sum_{k=1}^n k\) by the finding the sum two ways.
Video / Answer.

Note 4.1.16. Some Sum Formulas.

Example 4.1.15 shows us the following formula for an arithmetic series:
\begin{equation*} \displaystyle \sum_{k=1}^n k = \dfrac{n(n+1)}{2} \end{equation*}
We will verify in Exercise 5 the sum formula for the series of squares:
\begin{equation*} \displaystyle \sum_{k=1}^n k^2 = \dfrac{n(2n+1)(n+1)}{6} \end{equation*}
and we saw above that if \(r \ne 1\text{,}\)
\begin{equation*} \sum_{k=0}^n ar^k = \frac{a-ar^{n+1}}{1-r}\text{.} \end{equation*}

Subsection Computer Corner

Recurrence relations are like recursive functions. For example, you can find the \(n\)th Fibonacci number, \(F_n\text{,}\) by evaluating fibonacci(n)
The initial conditions of a a recurrence guarantee that it has a unique solution. These initial conditions are the terminal/base conditions for the recursive functions. Because it’s theoretical, math can go on forever, computers enter infinite loops:
Eventually, we’ll get RecursionError: maximum recursion depth exceeded while calling a Python object

Exercises Exercises

1.

Find the first five terms of the sequence \(\{a_n\}\text{,}\) beginning with \(n=0\text{:}\)
  1. \(\displaystyle a_n = 2^n + 3\)
  2. \(\displaystyle a_n = n^{n+1}\)
  3. \(\displaystyle a_n = \lfloor n/2\rfloor + \lceil n/2 \rceil\)
  4. \(\displaystyle a_n = 6a_{n-1},\hspace{1em} a_0 = 2\)
  5. \(\displaystyle a_n = a_{n-1} + 3 a_{n-2},\hspace{1em} {a_0 = 1, a_1 = 2}\)
Solution.
  1. \(\displaystyle \{4, 5, 7, 11, 19\}\)
  2. \(\displaystyle \{ 0, 1, 8, 81, 1024 \}\)
  3. \(\displaystyle \{ 0, 1, 2, 3, 4\}\)
  4. \(\displaystyle \{2, 12, 72, 432, 2592 \}\)
  5. \(\displaystyle \{1, 2, 5, 11, 26\}\)

2.

Is the sequence \(\{a_n\}\) a solution of the recurrence relation \({a_n = 8a_{n-1}-16a_{n-2}}\) if
  1. \(\displaystyle a_n = 0\)
  2. \(\displaystyle a_n = 2n\)
  3. \(\displaystyle a_n = 2^n\)
  4. \(\displaystyle a_n = 4^n\)
Solution.
  1. Yes
  2. No
  3. No
  4. Yes

3.

Find a solution to the recurrence relation
  1. \(\displaystyle a_n = 3a_{n-1},\hspace{1em} a_0 = 2\)
  2. \(\displaystyle a_n = a_{n-1} + n,\hspace{1em} a_0 = 1\)
  3. \(\displaystyle a_n = na_{n-1},\hspace{1em} a_0 = 1\)
Solution.
  1. \(\displaystyle a_n = 2\cdot 3^n\)
  2. \(\displaystyle a_n = \dfrac{n^2 + n + 2}{2}\)
  3. \(\displaystyle a_n = n!\)

4.

Find the value of each of the following sums:
  1. \(\displaystyle \displaystyle \sum_{k=0}^8 3\cdot 2^k\)
  2. \(\displaystyle \displaystyle \sum_{k=1}^8 2^k \)
  3. \(\displaystyle \displaystyle \sum_{k=1}^8 (1 + (-1)^k) \)
  4. \(\displaystyle \displaystyle \sum_{k=1}^8 (2^{k+1} - 2^k) \)
  5. \(\displaystyle \displaystyle \sum_{k=50}^{100} k\)
Solution.
  1. 1533
  2. 510
  3. 8
  4. 510
  5. 3825

5.

Using the telescoping example with the sequence \(a_n=(n+1)^3\text{,}\) derive a formula for \(\displaystyle \sum_{k=1}^n k^2\)
Solution.
This one’s a lot of fun, so let’s do it in a lot of detail. This is approach Blaise Pascal used to discover the formula in his 1654 Traité du triangle arithmétique.
Let \(a_n = (n+1)^3\text{.}\) Then from Example 4.1.14, we have that:
\begin{align*} \sum_{j=1}^n (j+1)^3 - j^3 & = a_n - a_0\\ \sum_{j=1}^n (j+1)^3 - j^3 & = (n+1)^3 - (0+1)^3\\ \sum_{j=1}^n j^3 + 3j^2 + 3j + 1 - j^3 & = n^3 + 3n^2 + 3n + 1 - 1\\ \sum_{j=1}^n 3j^2 + 3j + 1 & = n^3 + 3n^2 + 3n \\ \sum_{j=1}^n 3j^2 + \sum_{j=1}^n 3j + \sum_{j=1}^n 1 & = n^3 + 3n^2 + 3n \\ 3 \sum_{j=1}^n j^2 + 3 \sum_{j=1}^n j + \sum_{j=1}^n 1 & = n^3 + 3n^2 + 3n \\ 3 \sum_{j=1}^n j^2 & = n^3 + 3n^2 + 3n - 3 \sum_{j=1}^n j - \sum_{j=1}^n 1 \end{align*}
We have from Example 4.1.15 that \(\displaystyle \sum_{j=1}^n j = \dfrac{n(n+1)}{2}\) and if we add \(1\) a total of \(n\) times, we have \(\displaystyle \sum_{j=1}^n 1 = n\text{.}\) Plugging these in, we find:
\begin{align*} 3 \sum_{j=1}^n j^2 & = n^3 + 3n^2 + 3n - 3 \sum_{j=1}^n j - \sum_{j=1}^n 1 \\ 3 \sum_{j=1}^n j^2 & = n^3 + 3n^2 + 3n - 3\left( \dfrac{n(n+1)}{2}\right) - n\\ 3 \sum_{j=1}^n j^2 & = n^3 + 3n^2 + 2n - 3\left(\dfrac{n^2 + n}{2}\right) \\ 3 \sum_{j=1}^n j^2 & = \frac{2n^3}{2} + \frac{6n^2}{2} + \frac{4n}{2} - \dfrac{3n^2}{2} - \frac{3n}{2}\\ 3 \sum_{j=1}^n j^2 & = \frac{2n^3 + 3n^2 + n}{2} \\ 3 \sum_{j=1}^n j^2 & = \frac{n(2n+1)(n+1)}{2} \\ \sum_{j=1}^n j^2 & = \frac{n(2n+1)(n+1)}{6} \end{align*}
which is exactly the formula you learned in calculus!

6.

Use the formula for geometric series to show that
\begin{equation*} 1 + 2 + 2^2 + 2^3 + \dots 2^n = 2^{n+1} - 1 \end{equation*}
Solution.
Noting that this is a geometric series with common ratio 2 and first term 1, let \(r=2, a=1\) in the geometric series formula:
\begin{align*} \sum_{k=0}^n 2^{k} \amp= \dfrac{1-2^{n+1}}{1-2}\\ \amp= 2^{n+1} - 1 \end{align*}
This is why a binary number which is all 1’s is always one less than the next power of 2, e.g. \(1111_{\text{two}} = 15_{\text{ten}}\)
<Prev^TopNext>