Chapter 2

With Question/Answer Animations

Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education.
Chapter Summary
 Sequences and Summations
 Types of Sequences
 Summation Formulae
 Set Cardinality
 Countable Sets
 Matrices
 Matrix Arithmetic
Section 2.4
Section Summary
 Sequences.
 Examples: Geometric Progression, Arithmetic
Progression
 Recurrence Relations
 Example: Fibonacci Sequence
 Summations
 Special Integer Sequences (optional)
Introduction
 Sequences are ordered lists of elements.
 1, 2, 3, 5, 8
 1, 3, 9, 27, 81, …….
 Sequences arise throughout mathematics, computer
science, and in many other disciplines.
 We will introduce the terminology to represent
sequences and sums of the terms in the sequences.
Sequences
Definition: A sequence is a function from a subset of
the integers (usually either the set {0, 1, 2, 3, 4, …..} or
{1, 2, 3, 4, ….} ) to a set S.
 The notation an is used to denote the image of the
integer n. We can think of an as the equivalent of f(n)
where f is a function from {0,1,2,…..} to S. We call an as
a term of the sequence.
Sequences
Example: Consider the sequence where
Geometric Progression
Definition: A geometric progression is a sequence of the
form: a, ar, ar2,…,arn,…
where the initial term a and the common ratio r are real
numbers.
Examples:
1. Let a = 1 and r = −1. Then:

2. Let a = 2 and r = 5. Then:

3. Let a = 6 and r = 1/3. Then:

Example: Calculating Simple
Geometric Progression
 Suppose you want to print the first n terms of a geometric progression
with a starting term a and common ratio r. You can use the following
code in Python (see simple_geometric_progression.py)

 The output is a sequence of 3, 6, 12, 24, 48

 See [Link]
geometric-progression/ for real life examples for GP
Example: Exponential Backoff
 In network programming, exponential backoff is often
used to handle retries after failures. The wait time between
retries increases geometrically to prevent overwhelming
the server. (see exponential_backoff.py)
Arithmetic Progression
Definition: A arithmetic progression is a sequence of the
form: a, a+d, a+2d, …, a+nd, … where the initial term a and
the common difference d are real numbers.
Examples:
1. Let a = −1 and d = 4:

2. Let a = 7 and d = −3:

3. Let a = 1 and d = 2:
Example: Simulating Temperature
Drop in a Cooling Experiment
 Let’s say we are studying the cooling rate of a heated metal object
exposed to a colder environment. We start with an initial temperature
of 100°C, and each minute, the temperature drops by a constant rate of
2°C. This cooling can be modeled as an arithmetic progression, where
the temperature decreases linearly over time.
 The temperature at each minute is given by the formula:
Tn​=T0​−(n×d)
where:
• T0 is the initial temperature,
• d is the cooling rate (temperature decrease per minute),
• n is the number of minutes elapsed.
 See simulating_temperature_drop.py for a Python implementation
 See [Link]
arithmetic-progression/ for real life examples for AP
Strings
 Definition: Given a set X, a string over X is a finite
sequences of elements of X.
 Example: If X is the set X = {a, b, c}, then the following are
examples of strings over X: aba, aaaa, bba, etc.
 Repetitions can be specified with a superscripts, for
instance: a2b3ac2a3 =aabbbaccaaa, (ab)3 = ababab, etc.
 The length of a string is its number of elements, e.g.,
|abaccbab| = 8.
 The string with no elements is called null string,
represented λ. Its length is, of course, zero: |λ| = 0.

Taken from the lecture notes on Discrete Mathematics by Miguel A. Lerma

Recurrence Relations
Definition: A recurrence relation for the sequence {an}
is an equation that expresses an in terms of one or
more of the previous terms of the sequence, namely,
a0, a1 , …, an-1, for all integers n with n ≥ n0, where n0 is a
nonnegative integer.
 A sequence is called a solution of a recurrence relation
if its terms satisfy the recurrence relation.
 The initial conditions for a sequence specify the terms
that precede the first term where the recurrence
relation takes effect.
Questions about Recurrence Relations
Example 1: Let {an} be a sequence that satisfies the
recurrence relation an = an-1 + 3 for n = 1,2,3,4,…. and
suppose that a0 = 2 (this is the initial condition).
What are a1 , a2 and a3?

Solution: We see from the recurrence relation that

a1 = a0 + 3 = 2 + 3 = 5
a2 = 5 + 3 = 8
a3 = 8 + 3 = 11
Questions about Recurrence Relations
Example 2: Let {an} be a sequence that satisfies the
recurrence relation an = an-1 – an-2 for n = 2,3,4,…. and
suppose that a0 = 3 and a1 = 5. What are a2 and a3?
[Here the initial conditions are a0 = 3 and a1 = 5. ]

Solution: We see from the recurrence relation that

a2 = a1 - a0 = 5 – 3 = 2
a3 = a2 – a1 = 2 – 5 = –3
Fibonacci Sequence
Definition: Define the Fibonacci sequence, f0 ,f1 ,f2,…, by:
 Initial Conditions: f0 = 0, f1 = 1
 Recurrence Relation: fn = fn-1 + fn-2

Example: Find f2 ,f3 ,f4 , f5 and f6.

Answer:
f2 = f1 + f0 = 1 + 0 = 1,
f3 = f2 + f1 = 1 + 1 = 2,
f4 = f3 + f2 = 2 + 1 = 3,
f5 = f4 + f3 = 3 + 2 = 5,
f6 = f5 + f4 = 5 + 3 = 8.
Solving Recurrence Relations
 Finding a formula for the nth term of the sequence
generated by a recurrence relation is called solving the
recurrence relation.
 Such a formula is called a closed formula.
 Various methods for solving recurrence relations will
be covered in Chapter 8 where recurrence relations
will be studied in greater depth.
 Here we illustrate by example the method of iteration
in which we need to guess the formula. The guess can
be proved correct by the method of induction
(Chapter 5).
Iterative Solution Example
Method 1: Working upward, forward substitution
Let {an} be a sequence that satisfies the recurrence relation
an = an-1 + 3 for n = 2, 3, 4, …. and suppose that a1 = 2.
a2 = 2 + 3
a3 = (2 + 3) + 3 = 2 + 3 ∙ 2
a4 = (2 + 2 ∙ 3) + 3 = 2 + 3 ∙ 3
.
.
.
an = an-1 + 3 = (2 + 3 ∙ (n – 2)) + 3 = 2 + 3(n – 1)
Iterative Solution Example
Method 2: Working downward, backward substitution
Let {an} be a sequence that satisfies the recurrence relation
an = an-1 + 3 for n = 2,3,4,…. and suppose that a1 = 2.

an = an-1 + 3
= (an-2 + 3) + 3 = an-2 + 3 ∙ 2
= (an-3 + 3 )+ 3 ∙ 2 = an-3 + 3 ∙ 3
.
.
.
= a2 + 3(n – 2) = (a1 + 3) + 3(n – 2) = 2 + 3(n – 1)
Financial Application
Example: Suppose that a person deposits $10,000.00 in
a savings account at a bank yielding 11% per year with
interest compounded annually. How much will be in
the account after 30 years?
Let Pn denote the amount in the account after 30
years. Pn satisfies the following recurrence relation:
Pn = Pn-1 + 0.11Pn-1 = (1.11) Pn-1
with the initial condition P0 = 10,000

Continued on next slide →

Financial Application
Pn = Pn-1 + 0.11Pn-1 = (1.11) Pn-1
with the initial condition P0 = 10,000
Solution: Forward Substitution
P1 = (1.11)P0
P2 = (1.11)P1 = (1.11)2P0
P3 = (1.11)P2 = (1.11)3P0
:
Pn = (1.11)Pn-1 = (1.11)nP0 = (1.11)n 10,000
Pn = (1.11)n 10,000 (Can prove by induction, covered in Chapter 5)
P30 = (1.11)30 10,000 = $228,992.97
Special Integer Sequences (opt)
 Given a few terms of a sequence, try to identify the
sequence. Conjecture a formula, recurrence relation,
or some other rule.
 Some questions to ask?
 Are there repeated terms of the same value?
 Can you obtain a term from the previous term by adding
an amount or multiplying by an amount?
 Can you obtain a term by combining the previous terms
in some way?
 Are they cycles among the terms?
 Do the terms match those of a well-known sequence?
Questions on Special Integer
Sequences (opt)
Example 1: Find formulae for the sequences with the
following first five terms: 1, ½, ¼, 1/8, 1/16
Solution: Note that the denominators are powers of 2. The
sequence with an = 1/2n is a possible match. This is a
geometric progression with a = 1 and r = ½.
Example 2: Consider 1,3,5,7,9
Solution: Note that each term is obtained by adding 2 to
the previous term. A possible formula is an = 2n + 1. This
is an arithmetic progression with a =1 and d = 2.
Example 3: 1, -1, 1, -1,1
Solution: The terms alternate between 1 and -1. A possible
sequence is an = (−1)n . This is a geometric progression
with a = 1 and r = −1.
Useful Sequences
Guessing Sequences (optional)
Example: Conjecture a simple formula for an if the
first 10 terms of the sequence {an} are 1, 7, 25, 79, 241,
727, 2185, 6559, 19681, 59047.

Solution: Note the ratio of each term to the previous

approximates 3. So now compare with the sequence
3n . We notice that the nth term is 2 less than the
corresponding power of 3. So, a good conjecture is
that an = 3n − 2.
Integer Sequences (optional)
 Integer sequences appear in a wide range of contexts. Later we
will see:
 The sequence of prime numbers (Chapter 4)
 The number of ways to order n discrete objects (Chapter 6)
 The number of moves needed to solve the Tower of Hanoi puzzle
with n disks (Chapter 8)
 The number of rabbits on an island after n months (Chapter 8).
 Integer sequences are useful in many fields such as biology,
engineering, chemistry and physics.
 On-Line Encyclopedia of Integer Sequences (OESIS) contains
over 200,000 sequences. Began by Neil Stone in the 1960s
(printed form). Now found at [Link]
Summations
 Sum of the terms
from the sequence
 The notation:

represents

 The variable j is called the index of summation. It runs

through all the integers starting with its lower limit m and
ending with its upper limit n.
Summations
 More generally for a set S:

 Examples:
Product Notation (optional)
 Product of the terms
from the sequence

 The notation:

represents
Some Useful Summation Formulae
Geometric Series: We
just proved this.

Later we
will prove
some of
these by
induction.

Proof in text
(requires calculus)
Section 2.5
Section Summary
 Cardinality
 Countable Sets
 Computability
Cardinality
Definition: The cardinality of a set A is equal to the
cardinality of a set B, denoted
|A| = |B|,
if and only if there is a one-to-one correspondence from A
to B.
 If there is a one-to-one function from A to B, the
cardinality of A is less than or the same as the cardinality of
B and we write |A| ≤ |B|.
 When |A| ≤ |B| and A and B have different cardinality, we
say that the cardinality of A is less than the cardinality of B
and write |A| < |B|.
Cardinality
 Definition: A set that is either finite or has the same
cardinality as the set of positive integers (Z+) is called
countable. A set that is not countable is uncountable.
 The set of real numbers R is an uncountable set.
 When an infinite set is countable (countably infinite)
its cardinality is ℵ0 (where ℵ is aleph, the 1st letter of
the Hebrew alphabet). We write |S| = ℵ0 and say that S
has cardinality “aleph null.”
Showing that a Set is Countable
 An infinite set is countable if and only if it is possible
to list the elements of the set in a sequence (indexed
by the positive integers).
 The reason for this is that a one-to-one
correspondence (bijection) f from the set of positive
integers to a set S can be expressed in terms of a
sequence a1, a2, …, an , … where a1 = f(1), a2 = f(2),…, an =
f(n),…
Hilbert’s Grand Hotel David Hilbert

The Grand Hotel (example due to David Hilbert) has countably infinite number of
rooms, each occupied by a guest. We can always accommodate a new guest at this
hotel. How is this possible?

Explanation: Because the rooms of Grand

Hotel are countable, we can list them as Room
1, Room 2, Room 3, and so on. When a new
guest arrives, we move the guest in Room 1 to
Room 2, the guest in Room 2 to Room 3, and
in general the guest in Room n to Room n + 1,
for all positive integers n. This frees up Room
1, which we assign to the new guest, and all
the current guests still have rooms. The hotel can also accommodate a
countable number of new guests, all the
guests on a countable number of buses
where each bus contains a countable
number of guests (see exercises).
Showing that a Set is Countable
Example 1: Show that the set of positive even integers E is
countable set.
Solution: Let f(x) = 2x.
1 2 3 4 5 6 …..

2 4 6 8 10 12 ……
Then f is a bijection from N to E since f is both one-to-one
and onto. To show that it is one-to-one, suppose that
f(n) = f(m). Then 2n = 2m, and so n = m. To see that it is
onto, suppose that t is an even positive integer. Then
t = 2k for some positive integer k and f(k) = t.
Showing that a Set is Countable
Example 2: Show that the set of integers Z is
countable.
Solution: Can list in a sequence:
0, 1, − 1, 2, − 2, 3, − 3 ,………..
Or can define a bijection from N to Z:
 When n is even: f(n) = n/2
 When n is odd: f(n) = −(n−1)/2
The Positive Rational Numbers are
Countable
 Definition: A rational number can be expressed as the
ratio of two integers p and q such that q ≠ 0.
 ¾ is a rational number
 √2 is not a rational number.
Example 3: Show that the positive rational numbers
are countable.
Solution: The positive rational numbers are countable
since they can be arranged in a sequence:
r1 , r2 , r3 ,…
The next slide shows how this is done. →
 The Positive Rational Numbers are
Countable
First row q = 1.
Second row q = 2.
etc.

Constructing the list

First list p/q with p + q = 2.

Next list p/q with p + q = 3.
Next list p/q with p + q = 4.

And so on.
1, ½, 2, 3, 1/3,1/4, 2/3, ….

Because all positive rational numbers are

listed once, we have shown that the set of
positive rational numbers is countable.
Section 2.6
Section Summary
 Definition of a Matrix
 Matrix Arithmetic
 Transposes and Powers of Arithmetic
 Zero-One matrices
Matrices
 Matrices are useful discrete structures that can be used in many
ways. For example, they are used to:
 Describe certain types of functions known as linear
transformations.
 Express which vertices of a graph are connected by edges (see
Chapter 10).
 In later chapters, we will see matrices used to build models of:
 Transportation systems.
 Communication networks.
 Algorithms based on matrix models will be presented in later
chapters.
 Here we cover the aspect of matrix arithmetic that will be needed
later.
Matrix
Definition: A matrix is a rectangular array of
numbers. A matrix with m rows and n columns is
called an m×n matrix.
 The plural of matrix is matrices.
 A matrix with the same number of rows as columns is called square.
 Two matrices are equal if they have the same number of rows and
the same number of columns and the corresponding entries in
every position are equal.

3 × 2 matrix
Notation
 Let m and n be positive integers and let

 The ith row of A is the 1×n matrix [ai1, ai2,…,ain]. The

jth column of A is the m × 1 matrix:
 The (i,j)th element or entry of A is the element aij. We
can use A = [aij ] to denote the matrix with its (i,j)th
element equal to aij.
Matrix Arithmetic: Addition
Defintion: Let A = [aij] and B = [bij] be m×n matrices.
The sum of A and B, denoted by A + B, is the m×n
matrix that has aij + bij as its (i,j)th element. In other
words, A + B = [aij + bij].
Example:

Note that matrices of different sizes can not be added.

Matrix Multiplication
Definition: Let A be an m×k matrix and B be a k×n matrix. The
product of A and B, denoted by AB, is the m×n matrix that has
its (i,j)th element equal to the sum of the products of the
corresponding elements from the ith row of A and the jth column
of B. In other words, if AB = [cij] then cij = ai1b1j + ai2b2j + … +
akjb2j.
Example:

The product of two matrices is undefined when the number of

columns in the first matrix is not the same as the number of rows
in the second.
Illustration of Matrix Multiplication
 The Product of A = [aij] and B = [bij]
Matrix Multiplication is not
Commutative
Example: Let

Does AB = BA?
Solution:

AB ≠ BA
Identity Matrix and Powers of Matrices
Definition: The identity matrix of order n is the m×n
matrix In = [ij], where ij = 1 if i = j and ij = 0 if i≠j.

AIn = ImA = A
when A is an m n matrix

Powers of square matrices can be defined. When A is an

n  n matrix, we have:
A0 = In Ar = AAA∙∙∙A
r times
Transposes of Matrices
Definition: Let A = [aij] be an m×n matrix. The
transpose of A, denoted by At ,is the n×m matrix
obtained by interchanging the rows and columns of A.

If At = [bij], then bij = aji for i =1,2,…,n

and j = 1,2, ...,m.
Symmetric Matrices
Definition: A square matrix A is called symmetric if
A = At. Thus A = [aij] is symmetric if aij = aji for i and j
with 1≤ i≤ n and 1≤ j≤ n.

Square matrices do not change when their rows and

columns are interchanged.
Zero-One Matrices
Definition: A matrix all of whose entries are either 0
or 1 is called a zero-one matrix. (These will be used in
Chapters 9 and 10.)
Algorithms operating on discrete structures
represented by zero-one matrices are based on
Boolean arithmetic defined by the following Boolean
operations:
Zero-One Matrices
Definition: Let A = [aij] and B = [bij] be an m  n
zero-one matrices.
 The join of A and B is the zero-one matrix with (i,j)th
entry aij ∨ bij. The join of A and B is denoted by A ∨ B.
 The meet of of A and B is the zero-one matrix with
(i,j)th entry aij ∧ bij. The meet of A and B is denoted
by A ∧ B.
Joins and Meets of Zero-One Matrices
Example: Find the join and meet of the zero-one
matrices

Solution: The join of A and B is

The meet of A and B is

Boolean Product of Zero-One Matrices
Definition: Let A = [aij] be an m k zero-one
matrix and B = [bij] be a k n zero-one matrix. The
Boolean product of A and B, denoted by A ⊙ B, is the
m n zero-one matrix with(i,j)th entry
cij = (ai1 ∧ b1j)∨ (ai2 ∧ b2j) ∨ … ∨ (aik ∧ bkj).
Example: Find the Boolean product of A and B, where

Continued on next slide →

Boolean Product of Zero-One Matrices
Solution: The Boolean product A ⊙ B is given by
Boolean Powers of Zero-One Matrices
Definition: Let A be a square zero-one matrix and
let r be a positive integer. The rth Boolean power of
A is the Boolean product of r factors of A, denoted
by A[r] . Hence,

(The Boolean product is well defined because the

Boolean product of matrices is associative.)
Boolean Powers of Zero-One Matrices
Example: Let

Find An for all positive integers n.

Solution:
Example: Social Networks
 See [Link]
textbook/[Link]
Questions?