Section 2.

3
Section Summary
 Definition of a Function.
 Domain, Codomain
 Image, Preimage
 Injection, Surjection, Bijection
 Inverse Function
 Function Composition
 Graphing Functions
 Floor, Ceiling, Factorial
Functions
Definition: Let A and B be nonempty sets. A function f
from A to B, denoted f : A → B is an assignment of
each element of A to exactly one element of B. We
write f(a) = b if b is the unique element of B assigned
by the function f to the element a of A. Students Grades
 Functions are sometimes A
Carlota Rodriguez
called mappings or B
transformations. Sandeep Patel C
Jalen Williams D

F
Kathy Scott
Functions
 A function f: A → B can also be defined as a subset of
A×B (a relation). This subset is restricted to be a
relation where no two elements of the relation have
the same first element.
 Specifically, a function f from A to B contains one, and
only one ordered pair (a, b) for every element a∈ A.

and
Functions f(a)
Given a function f: A → B:
 We say f maps A to B or
f is a mapping from A to B.
 A is called the domain of f. f : A B
 B is called the codomain of f.
 If f(a) = b,
 then b is called the image of a under f.
 a is called the preimage of b.
 The range of f is the set of all images of points in A under f.
We denote it by f (A). The range is a subset of codomain B.
 Two functions are equal when they have the same domain, the
same codomain and map each element of the domain to the
same element of the codomain.
Representing Functions
 Functions may be specified in different ways:
 An explicit statement of the assignment.
Students and grades example.
 A formula.
f(x) = x + 1
 A computer program.
 When given an integer n, a program (e.g. in Java) can produce
the n-th Fibonacci Number (covered in the next section and also in Chapter 5).
 Questions
f(a) = ? z A B
a
The image of d is ? z x
b
The domain of f is ? A y
c
The codomain of f is ? B
d z
The preimage of y is ? b
f(A) = ? {y, z}
The preimage(s) of z is (are) ? {a,c,d}
Question on Functions and Sets
 If and S is a subset of A, then

A B
a
f {a,b,c,} is ? {y,z}
x
b
f {c,d} is ? {z} y
c

d z
 “many-to-one”
NOTE: in general, a function can map many
elements in the domain on the same element in
the range (many-to-one mapping)
A B
e.g. each of elements a,c,d is mapped to z
a
x
b
y
c

d z
Injections (i.e. one-to-one)
Definition: A function f is said to be one-to-one, or
injective, if and only if f(a) = f(b) implies that a = b for
all a and b in the domain of f. A function is said to be
an injection if it is one-to-one.
A B
a x

v
b
y
c
z
d

w
Surjections (i.e. onto)
Definition: A function f from A to B is called onto or
surjective, if and only if for every element
there is an element with . A
function f is called a surjection if it is onto.

A B
NOTE: as in the example of the right, a x
function could be surjective (onto)
but not injective (one to one). Why it is not? b
y
Vice versa, the example on the previous slide c
shows that a function could be injective (one- z
to-one) but not surjective (onto). Why? d
Bijections
Definition: A function f is a one-to-one correspondence,
or a bijection, if it is both one-to-one and onto
(surjective and injective).

A B
a x

b
y
c

d z

w
Showing that f is one-to-one or onto
 Showing that f is one-to-one or onto
Example 1: Let f be the function from {a,b,c,d} to {1,2,3}
defined by f(a) = 3, f(b) = 2, f(c) = 1, and f(d) = 3. Is f an
onto function?
Solution: Yes, f is onto since all three elements of the codomain are images of elements
in the domain. If the codomain were changed to {1,2,3,4}, f would not be onto.

Example 2: Consider function f: Z Z defined for any xZ

by equation f(x) = x2. Is this function onto Z (surjective)?
Solution: No, f is not onto because there is no integer x with x2 = −1, for example.
Showing that f is one-to-one or onto
Example 3: Consider function/mapping f: Z Z+ defined
by equation f(x) = x2. Is this function onto?

Solution: No. There is no integer such that x2 = 2, for example

Example 4: Consider function/mapping f: R R+ defined

by equation f(x) = x2. Is this function a onto?
Solution: yes.

Is it a bijection?
Solution: No. It is onto but not one-to-one
Showing that f is one-to-one or onto
Example 5: Consider function/mapping f: R+ R+ defined
by equation f(x) = x2. Is this function a bijection?

Solution: Yes, Why?

NOTE: properties like injection (one-to-one),

surjection (onto), or bijection (one-to-one correspondence)
depend on the definition of the function’s domain and codomain.
Inverse Functions
Definition: Let f be a bijection from A to B. Then the
inverse of f, denoted , is the function from B to A
defined as
No inverse exists unless f is a bijection. Why?
Inverse Functions
A f
B A B
a V V
a

b b
W W
c c

d X X
d

Y Y
Questions
Example 1: Let f be the function from {a,b,c} to {1,2,3}
such that f(a) = 2, f(b) = 3, and f(c) = 1. Is f invertible
and if so what is its inverse?
Questions
Example 1: Let f be the function from {a,b,c} to {1,2,3}
such that f(a) = 2, f(b) = 3, and f(c) = 1.
Is f invertible and if so what is its inverse?

Solution: The function f is invertible because it is a one-to-one correspondence.

The inverse function f-1 is f-1 (1) = c, f-1 (2) = a, and f-1 (3) = b.
Questions
Example 2: Let f: Z  Z be such that f(x) = x + 1.
Is f invertible, and if so, what is its inverse?
Questions
Example 2: Let f: Z  Z be such that f(x) = x + 1.
Is f invertible, and if so, what is its inverse?

Solution: The function f is invertible because it is a one-to-one correspondence.

The inverse function f-1 reverses the correspondence so f-1 (y) = y – 1.
Questions
Example 3: Let f: R → R be such that .
Is f invertible, and if so, what is its inverse?
Questions
Example 3: Let f: R → R be such that .
Is f invertible, and if so, what is its inverse?

Solution: The function f is not invertible.

It is not a bijection (neither injective nor surjective, why?)

R
0
Questions
Example 4: Let f: R → R+ be such that .
Is f invertible, and if so, what is its inverse?

Solution: The function f is not invertible.

It is not a bijection (surjective, but not injective, why?)

R+

R
0
Questions
Example 5: Let f: R+ → R + be such that .
Is f invertible, and if so, what is its inverse?

Solution: Yes, the inverse is .

R+ R+

R+ R+
0 0
Composition
 Definition: Let f: B → C, g: A → B. The composition of
f with g, denoted is the function from A to C
defined by
Composition
g f
A B C A C
V a
a h h
b i b
W i
c
c
X j
d
d j
Y
Composition
Example 1: If and , then

and
Composition Questions
Example 2: Let g be the function from the set {a,b,c}
to itself such that g(a) = b, g(b) = c, and g(c) = a. Let f
be the function from the set {a,b,c} to the set {1,2,3}
such that f(a) = 3, f(b) = 2, and f(c) = 1.
What is the composition of f and g ?
Solution: The composition f∘g is defined by
f∘g (a)= f(g(a)) = f(b) = 2.
f∘g (b)= f(g(b)) = f(c) = 1.
f∘g (c)= f(g(c)) = f(a) = 3.

Note that the composition g∘f is not defined, because the range of f is not
a subset of the domain of g.
Composition Questions
Example 2: Let f and g be functions from the set of
integers to the set of integers defined by f(x) = 2x + 3
and g(x) = 3x + 2.
What is the composition of f and g, and also the
composition of g and f ?
Composition Questions
Example 2: Let f and g be functions from the set of
integers to the set of integers defined by f(x) = 2x + 3
and g(x) = 3x + 2.
What is the composition of f and g, and also the
composition of g and f ?
Solution:
f∘g (x)= f(g(x)) = f(3x + 2) = 2(3x + 2) + 3 = 6x + 7
g∘f (x)= g(f(x)) = g(2x + 3) = 3(2x + 3) + 2 = 6x + 11
Graphs of Functions
 Let f be a function from the set A to the set B. The
graph of the function f is the set of ordered pairs
{(a,b) | a ∈A and f(a) = b}.

Graph of f(n) = 2n + 1 Graph of f(x) = x2

from Z to Z from Z to Z
Some Important Functions
 The floor function, denoted

is the largest integer less than or equal to x.

 The ceiling function, denoted

is the smallest integer greater than or equal to x

Example:
Floor and Ceiling Functions

Graph of (a) Floor and (b) Ceiling Functions

Floor and Ceiling Functions
Proving Properties of Functions
Example: Prove that x is a real number, then
⌊2x⌋= ⌊x⌋ + ⌊x + ½⌋
Solution: Let x = n + ε, where n is an integer and 0 ≤ ε< 1.
Case 1: ε < ½
 2x = 2n + 2ε and ⌊2x⌋ = 2n, since 0 ≤ 2ε< 1.
 ⌊x + 1/2⌋ = n, since x + ½ = n + (1/2 + ε ) and 0 ≤ ½ +ε < 1.
 Hence, ⌊2x⌋ = 2n and ⌊x⌋ + ⌊x + 1/2⌋ = n + n = 2n.
Case 2: ε ≥ ½
 2x = 2n + 2ε = (2n + 1) +(2ε − 1) and ⌊2x⌋ =2n + 1,
since 0 ≤ 2 ε - 1< 1.
 ⌊x + 1/2⌋ = ⌊ n + (1/2 + ε)⌋ = ⌊ n + 1 + (ε – 1/2)⌋ = n + 1 since
0 ≤ ε – 1/2< 1.
 Hence, ⌊2x⌋ = 2n + 1 and ⌊x⌋ + ⌊x + 1/2⌋ = n + (n + 1) = 2n + 1.
Example: Factorial Function
Definition: f: N → Z+ , denoted by f(n) = n! is the
product of the first n positive integers when n is a
nonnegative integer.
f(n) = 1 ∙ 2 ∙∙∙ (n – 1) ∙ n, f(0) = 0! = 1

Examples: Stirling’s Formula:

f(1) = 1! = 1
f(2) = 2! = 1 ∙ 2 = 2

f(6) = 6! = 1 ∙ 2 ∙ 3∙ 4∙ 5 ∙ 6 = 720

f(20) = 2,432,902,008,176,640,000.
Section 2.4
Section Summary
 Sequences.
 Examples: Geometric Progression, Arithmetic
Progression
 Recurrence Relations
 Example: Fibonacci Sequence
 Summations
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, ranging from
botany to music.
 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, that is, f : N → 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 f : N → S. We call an a term
of the sequence.

an = f(n)
Sequences
Example: Consider the sequence where
 Geometric Progression
Definition: A geometric progression is a sequence of the form:

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:

 Arithmetic Progression
Definition: A arithmetic progression is a sequence of the form:

where initial term a and 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:
Strings
Definition: A string is a finite sequence of characters
from a finite set (an alphabet).
 Sequences of characters or bits are important in
computer science.
 The empty string is represented by λ.
 The string abcde has length 5.
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. What are a1 , a2 and a3?
[Here a0 = 2 is the initial condition.]

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:
f0 = 0
f1 = 1
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
.
observed pattern (guess) am = 2 + 3(m – 1)
.
.
an = an-1 + 3 = (2 + 3 ∙ (n – 2)) + 3 = 2 + 3(n – 1) (confirmed)
(prove by induction, covered in Chapter 5)
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
.
. pattern an = an-m + 3 ∙ m
.

= 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 n 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
observed pattern (guess) Pm = (1.11)m P0
:
Pn = (1.11)Pn-1 = (1.11) (1.11)n-1 P0 = (1.11)n P0 (confirmed)
(prove by induction, covered in Chapter 5)

Pn = (1.11)n 10,000
P30 = (1.11)30 10,000 = $228,992.97
Useful Sequences
 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
 Product of the terms
from the sequence

 The notation:

represents
Geometric Series
Sums of terms of geometric progressions

Continued on next slide 

Geometric Series
Sums of terms of geometric progressions

To compute Sn , first multiply both sides of the

Proof: Let equality by r and then manipulate the resulting sum
as follows:

Continued on next slide 

Geometric Series
From previous slide.

Shifting the index of summation with k = j + 1.

Removing k = n + 1 term and

adding k = 0 term.

Substituting S for summation formula

∴
if r ≠1

if r = 1
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.6
Section Summary
 Definition of a Matrix
 Matrix Arithmetic
 Transposes and Powers of Arithmetic
 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).
 represent systems of linear equations and their solutions
 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 i-th row of A is the 1 n matrix [ai1, ai2,…,ain].

The j-th 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
Definition: 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, if A + B = [cij] then cij = aij + bij .
Example:

Note that matrices of different sizes can not be added.

Matrix Multiplication
Definition: Let A be an n  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 i-th row of A and the j-th
column of B. In other words, if AB = [cij] then
cij = ai1b1j + ai2b2j + … + akjbkj.
Example: c12 = a21b11 + a22b21 + a23b31

Matrices of size : 43 3 2 4 2

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.

Transposes of 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) symmetric matrices do not change when

their rows and columns are interchanged.