3.2. Sequences and Series#

Sequences are nothing more than ordered lists of elements. We can feel that they are strongly related to tuples. However, tuples are always finite. Sequences, on the other hand, may be infinite.

Sequences
- Progressions
- Strings as Sequences
Recurrence Relations
- Solving a recurrence relation
Series
- Closed-form formulas for Summations
Exercises

3.2.1. Sequences #

Informally and often in practice, a sequence is nothing more than a list of elements:

\[\begin{split} \begin{align} & 1, 2, 3, 4, 5, 6 \\[1em] & a, f, c, e, g, w, z, y \\[1em] & 1, 1, 2, 3, 5, 8, 13, \\[1em] & 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, \ldots \end{align} \end{split}\]

A sequence can be finite or finite. Elements of a sequence can be repeated.

Formally speaking, sequences are functions from a subset of the integers to another set $S$.

Definition (sequence)

A sequence is a function from the subset of the integers, typically $\mathbb{N}$, to a set $S$.

When referring to a sequence, we use the notation $a_n$ to refer to the image of $n$ under the sequence function. So, $f(n) = a_n$ for some sequence defined by $f$. When speaking of functions which encode sequences, a value of the function is instead called a term of the sequence.

This definition is very generic. It imposes no properties on the function. For example, the function does not need to be surjective nor injective. The domain and codomain of the function are also left quite generic. The only requirement is that the domain of a subset of the integers.

We may write sequences in many ways. There is a roster-like method where we simply write all the terms of the sequence. This leaves the domain of the function encoding the sequence implicit. Often that domain is either $\mathbb{N}$ or $\mathbb{N} \setminus \{0\}$, depending on the conventions and context. For example,

\[ 1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \ldots, \]

is the decreasing sequence of positive fractions with $1$ as the numerator. The “first” term is clearly $1$. If we label the first element as $a_1 = 1$, that makes the sequence defined formally as:

\[\begin{split} f: \left\{ \begin{array}{c} \mathbb{N} \setminus \{0\} \rightarrow \mathbb{Q} \\ n \mapsto \frac{1}{n} \end{array} \right. \end{split}\]

If we instead label the first element as $a_0$, that makes the sequence defined formally as:

\[\begin{split} f: \left\{ \begin{array}{c} \mathbb{N} \rightarrow \mathbb{Q} \\ n \mapsto \frac{1}{n+1} \end{array} \right. \end{split}\]

We can also describe the sequence using a formula and some way to indicate the domain. One way is to write out the elements using a roster-like method, but instead of writing the actual terms, we write $a_1, a_2$, etc next to the formula.

\[ a_n = \frac{1}{n+1} \qquad\qquad (a_n) = (a_0, a_1, a_2, a_3, \ldots). \]

Notice that we typically use parenthesis to denote sequences, much like tuples. Indeed, a tuple is just a finite sequence. Another way to define a sequence is to define the “index range” of the sequence, Not to be confused with the range of a function, the index range is the range of values that the index $i$ may take for the terms $a_i$.

\[ (a_n) = \frac{1}{n+1} \ \ \text{ for } i \geq 0 \]

or simply

\[ (\frac{1}{n+1}) \ \ \text{ for } i \geq 0. \]

An even further shorthand would be $(\frac{1}{n+1})_{n \in \mathbb{N}}$

Tip

Notice that we can also define empty sequences very easily. If we let the domain of the function describing the sequence be $\varnothing$, then the sequence is immediately empty.

Progressions #

There are kinds of sequences to which we give special names. We will look at two: arithmetic progressions and geometric progressions.

Arithemtic Progression.

An arithmetic progression is a sequence with a common difference between each term. Given an initial term $a$ and a common difference $d$, an arithmetic progressions is a sequence of the form:

\[ (a, a+d, a+2d, a+3d, a+4d, \ldots) \]

Therefore, $a_n = a + nd$ for $n \in \mathbb{N}$.

In an arithmetic progression, the key trait is that $a_{i+1} - a_{i} = d$ The starting term and the difference can be any (typically real) number.

Arithmetic progressions

Let $a = 2$ and $d = 5$:

\[ (a_n) = (2, 7, 12, 17, 22, 27, 32, \ldots) \]

Let $a = 10$, and $d = -10$:

\[ (b_n) = (10, 0, -10, -20, -30, -40, \ldots) \]

Let $a = 0$ and $d = 1.1$:

\[ (c_n) = (0, 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, \ldots) \]

Notice that an arithmetic progression can either be increasing or decreasing, depending on if $d$ is positive or negative.

Geometric Progression.

Geometric progressions are sequences with a common ratio between each term. Given an initial term $a$ and a common ratio $r$, an arithmetic progression is a sequence of the form:

\[ (a, ar, ar^2, ar^3, ar^4, \ldots) \]

Therefore, $a_n = ar^n$ for $n \in \mathbb{N}$.

In a geometric progression, the key trait is that $a_{i+1} / a_i = r$ The starting term and ratio can be any (typically real) number.

Geometric progressions

Let $a = 1$ and $r = 2$:

\[ (a_n) = (1, 2, 4, 8, 16, 32, 64, 128, 256, \ldots) \]

Let $a = 18$ and $r = \frac{1}{3}$:

\[ (b_n) = (18, 6, 2, \frac{2}{3}, \frac{2}{9}, \frac{2}{27}, \frac{2}{81}, \ldots) \]

Let $a = 1$, and $r = -1$:

\[ (c_n) = (1, -1, 1, -1, 1, -1, 1, -1, \ldots) \]

A geometric progression may encode exponential growth or exponential decay depending on $r$. If $r > 1$, then it is exponential growth. If $0 < r < 1$, then it is exponential decay. Another fun property of geometric progressions are that if $r$ is negative, then the sequences goes back and forth between positive and negative numbers.

Checkpoint

Constant progression

Given any constant number $c$, the sequence

\[ (c, c, c, c, c, c, c, \ldots) \]

is both an arithmetic progression and a geometric progression.

Find the starting terms, difference, and ratio, to describe this sequence as an arithmetic progression and as a geometric progression.

Solution

Constant progression

Arithmetic: $a = c, d = 0$.

Geometric: $a = c, r = 1$.

Strings as Sequences #

It may have been apparently already from the discussion of tuples in the previous chapter, but strings are nothing more than tuples of characters. Formally, we can define strings to be a finite sequence of characters.

Definition (string)

A string is a finite sequence of symbols from a finite set of symbols.

Thinking again of sequences as functions, the codomain of a string is called the alphabet and is denoted by $\Sigma$. We denote the empty string as $\lambda$.

In computer science $\Sigma$ is often $\{0, 1\}$, thus forming binary strings. The alphabet may also be characters, for example, $\Sigma = \{a, b, c, \ldots, A, B, C, \ldots, !, @, \#, \ldots\}$, or some other character encoding like UTF-8 or ASCII.

You will study strings much more formally in a future course the Foundations of Computer Science.

3.2.2. Recurrence Relations #

Recurrence relations are descriptions for special kinds of sequences where the definition of one term relies on the previous term(s).

Definition (recurrence relation)

A recurrence relation for a sequence $(a_n)$ is an equation definition $a_n$ in terms of one of more of the previous terms in the sequence.

A recurrence relation should be paired with initial conditions which state the initial terms of the sequence from which the recurrence relation can then build further terms.

A sequence which satisfies the formula of a recurrence relation is called a solution of the recurrence.

Arithmetic progressions and geometric progressions can easily be defined using recurrence relations.

Progressions as recurrences

Let $(a_n) = (0, 4, 8, 12, 16, 20, 24, \ldots)$ be an arithmetic progression. A recurrence relation for this sequence is:

\[ a_n = a_{n-1} + 4, \quad a_0 = 0. \]

Here, $a_0$ is the initial condition.

Let $(b_n) = (1, 1.5, 2.25, 3.375, 5.0625, \ldots)$ be a geometric progression. We have:

\[ b_n = \frac{3}{2} b_{n-1}, \quad b_0 = 1 \]

Of course, a recurrence relation may rely on more than just a single previous term. It may also require more than one initial condition. Consider the recurrence $a_n = 2a_{n-2}$. To find a solution to this recurrence relation, we require two initial conditions, namely $a_0$ and $a_1$.

The most famous example of a recurrence relation relying on more than one previous term is the Fibonacci sequence. It is given by:

\[ a_n = a_{n-1} + a_{n-2}, \quad a_0 = a_1 = 1 \]

Recurrence relations naturally give rise to recursive algorithms. Below is a simple recursive algorithm to compute the Fibonacci number of index $n$.

def fib(n) :
    if (n <= 1) : return 1;
    return fib(n-1) + fib(n-2)

print([fib(i) for i in range(0,10)]);

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

The Fibonacci Spiral

Let $(F_n)$ be the Fibonacci sequence. If we organize a collection of squares whose successive side lengths are equal to $F_1$, $F_2$, $F_3$, etc., then these squares perfectly fill a rectangle. This is called a Fibonacci tiling.

If we then draw arcs to connect the opposite corners of each square, the result is the Fibonacci spiral.

../_images/2DFibb.svg — Fig. 3.19 The Fibonacci spiral and tiling for $F_1, F_2, \ldots F_8$.#

You may recognize the Fibonacci spiral from the logo of this book.

The Fibonacci numbers, and the Fibonacci spiral, have a strong relationship with the golden ratio. The golden ratio, denoted $\phi$, has been known since at least 500 BCE. Its presence in math, geometry, and nature has inspired many works of art as being very aesthetically pleasing. Indeed, we have:

\[ \lim_{n\rightarrow \infty} \frac{F_{n+1}}{F_n} = \phi = \frac{1 + \sqrt{5}}{2}. \]

This is a peculiar relation between a seemingly discrete sequence of natural numbers to the irrational value of $\phi$. Research continues to this day studying the golden ratio and the Fibonacci numbers.

Solving a recurrence relation #

Recall that a solution to a recurrence relation is a sequence of terms satisfying the relation. In order to solve a recurrence relation we must determine a closed-form formula for $a_n$ which depends on $n$ and does not depend on any previous terms.

Solving recurrence relations is a crucial part of computer science. Indeed, the efficiency of an algorithm to compute an element of a sequence is (most often) greatly improved by a closed-form formula rather than a recursive algorithm.

There are several strategies to try and solve recurrence relations. Two common strategies are forward substitution and backward substitution. Both attempt to discern a closed-form formula by comparing adjacent terms and manipulating expressions.

Take the recurrence relation $a_n = a_{n-1} + 3$ with $a_0 = 2$.

Forward substitution starts at the initial condition and applies the recurrence relation over and over.

\[\begin{split} \begin{align} a_0 &= 2 \\[1em] a_1 &= 2 + 3 \\[1em] a_2 &= (2+3) + 3 = 2 + 2\cdot 3 \\[1em] a_3 &= (2 + 2\cdot 3) + 3) = 2 + 3\cdot 3 \\[1em] \vdots & \\[1em] a_n &= a_{n-1} + 3 = (2 + (n-1)3) + 3 = 2 + 3n \end{align} \end{split}\]

Backward substitution starts at the recurrence relation and attempts to backtrack to the initial condition.

\[\begin{split} \begin{align} a_n &= a_{n-1} + 3 \\[1em] &= (a_{n-2} + 3) + 3 = a_{n-2} + 2\cdot 3 \\[1em] &= (a_{n-3} + 3) + 2\cdot 3 = a_{n-3} + 3\cdot 3 \\[1em] &= \vdots \\[1em] &= (a_1 + 3) + (n-2)3 = a_1 + (n-1)3 \\[1em] &= (a_0 + 3) + (n-1)3 = a_0 + 3n = 2 + 3n \end{align} \end{split}\]

Solving recurrence relations is typically a very challenging process. Many recurrence relations simply cannot be solved.

A classic example of recurrence relations is based on compounding interest.

Compounding interest

Consider a savings account which has an annual interest rate of 3%, compounding annually. If an investor makes an initial deposit of $1000.00, how much money will be in the account after 25 years?

This compound interest can be defined as the recurrence relation $S_n = S_{n-1}(1 + 0.03)$, where $0.03$ is the 3% interest rate and $n$ is measured in years.

Using forward substitution we can solve this recurrence.

\[\begin{split} \begin{align} S_1 &= 1.03S_0 \\[1em] S_2 &= 1.03S_1 = 1.03(1.03S_0) = 1.03^2S_0 \\[1em] S_3 &= 1.03S_2 = 1.03(1.03^2S_0) = 1.03^3S_0 \\[1em] \vdots & \\[1em] S_n &= 1.03^nS_0 \end{align} \end{split}\]

Since the initial deposit was $S_0 = 1000$, we have $S_{25} = 1.03^{25}(1000) = 2093.78$. Not a very good return on investment!

3.2.3. Series #

Before we look at the more general object of a series, consider first a summation.

A summation is simply a sum of a collection of numbers. Because addition is commutative, the order in which numbers of the collection are added does not matter. However, for ease of description and notation, we define a summation as a the addition of all the terms in a finite sequence. The resulting value is the sum.

A first summation

Let $(a_n) = 2n$ for $ 1 \leq n \leq 10$. The summation of this sequence is

$2 + 4 + 6 + 8 + 10 + 12 + 14 + 16 + 18 + 20 = 110$.

More generally, for a sequence $a_i$ for $c \leq i \leq n$, we write its summation using summation notation:

\[\begin{split} \begin{align} \sum_{i=c}^n a_i &= a_c + a_{c+1} + a_{c+2} + \cdots + a_n, \quad \text{or} \\[1em] \sum_{c \leq i \leq n} &= a_c + a_{c+1} + a_{c+2} + \cdots + a_n. \end{align} \end{split}\]

In these examples, we call $i$ the index of summation with $c$ being called the lower limit and $n$ being called the upper limit.

Since sequences can map from any subset of the integers, we may have a sequence like $(a_3, a_5, a_{11}, a_{24})$. How would we write the summation of this sequence?

Rather than relying on a sequential range of values for the index of summation (i.e. $0, 1, 2, 3$, etc.), we can specify a set for the index of summation. If we let $S = \{3, 5, 11, 24\}$, then the previous summation is given as:

\[ \sum_{i \in S} a_i = a_3 + a_5 + a_{11} + a_{24}. \]

The ideas of summation notation extend to product notation as well. We simply replace $\Sigma$ with $\Pi$ to represent multiplication of terms in a sequence instead of addition.

Checkpoint

Product notation

Determine the following products.

$\prod\limits_{i=1}^5 i$
$\prod\limits_{i=0}^6 (a_i)$, where $(a_i) = 2^i$

Solution

Product notation

$\prod\limits_{i=1}^5 i = 1 \times 2 \times 3 \times 4 \times 5 = 5! = 120$
$\prod\limits_{i=0}^6 (a_i) = 2^0 \times 2^1 \times 2^2 \times 2^3 \times 2^4 \times 2^5 \times 2^6 = 2^{21} = 2097152$

The more general series describes a summation with a possibly infinite number of terms. Some authors use series and summation interchangeably in the finite case and instead say infinite series to emphasize that the series in question has infinitely many terms.

Some special infinite series are said to be convergent if their sum approaches a fixed value in its limit. Otherwise, the series is said to be divergent.

For an infinite series $\sum_{i=0}^\infty a_i$, its $n$-th partial sum is $\sum_{i=0}^n a_i$ One way to determine if a series is convergent is to find a closed-form solution to the sequence of partial sums and then get the limit of that sequence for large $n$. We are probably already familiar with the notion of convergent series from calculus, but let us take a simple example.

Converging series

The series $\sum_{i=0}^\infty \frac{1}{2^n}$ is:

\[ \sum_{i=0}^\infty \frac{1}{2^n} = 1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots \]

The partial sums of this series are defined as $\sum_{i=0}^n = 1 + \frac{2^n - 1}{2^n}$.

Clearly, taking $\lim\limits_{n \rightarrow \infty}$, we have

\[ \sum_{i=0}^\infty \frac{1}{2^n} = \lim_{n \rightarrow \infty} 1 + \frac{2^n - 1}{2^n} = 2 \]

Closed-form formulas for Summations #

Finding the closed-from of a summation entails finding a function $f$ such that $f(n) = \sum_{i=0}^n a_i$, assuming the sequence $(a_i)$ is defined for $i \in \mathbb{N}$.

The easiest closed form solution comes directly from the definition of multiplication. Indeed, multiplication is just repeated addition. For any constant number $c$, we have the following summation formula.

\[ \sum_{i=1}^n c = nc. \]

\[ \sum_{i=0}^n c = (n+1)c. \]

Tip

Be careful with the index of summation! There are actually (n+1) terms in the range $a_0, a_1, a_2, \ldots, a_n$.

One fundamental closed-form sum is:

\[ \sum_{i=0}^n i = \frac{n(n+1)}{2}. \]

A fun exercise is proving this formula holds true.

Similarly, there are closed forms for $\sum_{i=0}^n i^2$ and $\sum_{i=0}^n i^3$.

\[\begin{split} \begin{align} \sum_{i=0}^n i^2 &= \frac{n^3}{3} + \frac{n^2}{2} + \frac{n}{6} \\[1em] &= \frac{(n)(n+1)(2n +1)}{6} \\[1em] \end{align} \end{split}\]

\[\begin{split} \begin{align} \sum_{i=0}^n i^3 &= \frac{n^4}{4} + \frac{n^3}{2} + \frac{n^2}{4} \\[1em] &= \frac{n^2(n+1)^2}{4} \\[1em] \end{align} \end{split}\]

Arithmetic and geometric progressions, when summed, yield closed-form solutions.

An arithmetic series, the summation of an arithmetic progression $(a_n)$ has the closed-form formula:

\[ \sum_{i=1}^{n-1} (a_i) = n\frac{(a_0 + a_n)}{2} \]

The summation is simply $n$ times the average of the first and last elements in the arithmetic progression. As a fun anecdote, this formulas was used by Gauss as a child.

For geometric series, summations of geometric progressions, there is a little more work involved. In particular, we must consider what happens for different values of $r$, the ratio.

\[\begin{split} \sum_{i=0}^n ar^i = \left\{ \begin{array}{ll} \frac{ar^{n-1} - a}{r-1}, &\ r \neq 1\\ (n+1)a, &\ r = 1 \end{array}\right. \end{split}\]

Checkpoint

Summations

Determine the sum of the following summation

\[ \sum_{i=0}^{15} i^2 + 3i \]

Solution

Summations

\[\begin{split} \sum_{i=0}^{15} i^2 + 3i &= \sum_{i=0}^{15} i^2 + 3\sum_{i=0}^{15} i \\[1em] &= \frac{(15)(16)(31)}{6} + \frac{3}{2}(15)(16) \\[1em] &= 1600 \end{split}\]

3.2.4. Exercises #

Exercise 3.19

Find a recurrence relation and its initial conditions to describe the sequence of numbers produced by the factorial function.

Solution to Exercise 3.19

$f_n = n \cdot f_{n-1}$, $f_0 = 1$.

Exercise 3.20

Write a recursive Python function which encodes the factorial function. This function should use your recurrence relation determined in the previous exercise.

Solution to Exercise 3.20

def fact(n) :
    if (n == 0) :
        return 1;
    return n * fact(n-1);

print(fact(1), fact(2), fact(3), fact(4), fact(5))

1 2 6 24 120

Exercise 3.21

Give a recurrence relation and initial condition(s) for:

The arithmetic progression $(c, c+s, c+2s, c+3s, \ldots)$.
The geometric progression $(bn, bn^2, bn^3, bn^4, \ldots)$.

Solution to Exercise 3.21

$a_n = a_{n-1}+s, a_0 = c$
$a_k = a_{k-1}n, a_0 = bn$

Exercise 3.22

Consider the recurrence relation $a_n = 8a_{n-1} - 16a_{n-2}$. Are the following valid solutions to this recurrence relation? If so, compute $a_0, a_1, \ldots, a_4$ using the formula.

$(a_n) = 0$
$(a_n) = n4^n$
$(a_n) = n^24^n$
$(a_n) = (2 + 3n)(4^n)$

Solution to Exercise 3.22

Yes. $(a_n) = (0, 0, 0, 0, 0, 0, \ldots)$
Yes. $(a_n) = (0, 4, 32, 192, 1024, \ldots)$
No.
Yes. $(a_n) = (2, 20, 128, 704, 3584, \ldots)$

Exercise 3.23

Consider the recurrence relation $a_n = 4a_{n-1} - 4a_{n-2}$ with initial conditions $a_0 = 1$ and $a_1 = 4$. What are the first 7 terms of this sequence? Can you find a closed-form formula for $a_n$?

Solution to Exercise 3.23

$a_0 = 1, a_1 = 4, a_2 = 12, a_3 = 32, a_4 = 80, a_5 = 192, a_6 = 448$.

$a_n = (n+1)2^n$

Exercise 3.24

Determine the sum of the following summations.

$\sum\limits_{i=0}^{10} i + 3$
$\sum\limits_{i=0}^{20} 2i + 5$
$\sum\limits_{i=0}^{20} (a_i)$ where $a_i = a_{i-1} + 10$ and $a_0 = 0$

Solution to Exercise 3.24

\[\begin{split} \sum\limits_{i=0}^{10} i + 3 &= \sum\limits_{i=0}^{10} i + \sum\limits_{i=0}^{10} 3\\ &= (10)(11)(\frac{1}{2}) + 3(11) \\ &= 55 + 33\\ &= 88 \end{split}\]
\[\begin{split} \sum\limits_{i=0}^{20} 2i + 5 &= 2\sum\limits_{i=0}^{20} i + \sum\limits_{i=0}^{20} 5\\ &= 2(20)(21)(\frac{1}{2}) + 5(21) \\ &= 420 + 105\\ &= 525 \end{split}\]
Notice that the recurrence relation can be solved as $a_{i} = 10i$. Then:

\[\begin{split} \sum\limits_{i=0}^{20} a_i &= \frac{21}{2}(a_0 + a_{20})\\ &= \frac{21}{2}(200)\\ &= 2100 \end{split}\]

Exercise 3.25

Determine the sum of the following summations.

$\sum\limits_{k=0}^{3} 3^{k}$
$\sum\limits_{t=1}^{1} cos(\pi t)$
$\sum\limits_{\ell=0}^{10} 6^2$
$\sum\limits_{i=-2}^{2} 2i + 4$

Solution to Exercise 3.25

$1 + 3 + 9 + 27 = 40$
$-1$
$11\cdot 6^2 = 396$
$(-4 + 4) + (-2 + 4) + (0 + 4) + (2 + 4) + (4 + 4) = 20$

Sequences and Series

Contents

3.2. Sequences and Series#