Functions;

Sequences, Sums
Waris Ali
Function: Formal Definition
For any sets A, B, we say that a
function f from (or “mapping”) A to B
(f:AB) is a particular assignment of
exactly one element f(x)B to each
element xA.

2
Graphical Representations
Functions can be represented
graphically in several ways:
f A B
• •
f • •
• • • y
a b •
•
•
• x
A
B Plot
Like Venn diagrams

3
Some Function Terminology
If it is written that f:AB, and f(a)=b
(where aA & bB), then we say:
 A is the domain of f.
We also say
 B is the codomain of f. the signature
 b is the image of a under f. of f is A→B.
 a is a pre-image of b under f.
 In general, b may have more than 1 pre-image.
 The range RB of f is R={b | a f(a)=b }.

4
Range versus Codomain
The range of a function might not be its
whole codomain.
The codomain is the set that the
function is declared to map all domain
values into.
The range is the particular set of values
in the codomain that the function
actually maps elements of the domain
to. 5
Range vs. Codomain -
Example
Suppose I declare to you that: “f is a
function mapping students in this class
to the set of grades {A,B,C,D,E}.”
At this point, you know f’s codomain is:
__________, and its range is________.
{A,B,C,D,E} unknown!
Suppose the grades turn out all As and
Bs.
Then the range of f is {A,B}
_________, but
its codomain is __________________.
still {A,B,C,D,E}!
6
One-to-One, Onto, Bijection.
Intuitively.
Represent functions using “node and arrow” notation:
One-to-One means that no clashes occur.
 BAD: a clash occurred, not 1-to-1

 GOOD: no clashes, is 1-to-1

Onto means that every possible output is hit

 BAD: 3rd output missed, not onto

 GOOD: everything hit, onto

7
One-to-One, Onto, Bijection.
Intuitively.
Bijection means that when arrows reversed,
a function results. Equivalently, that both
one-to-one’ness and onto’ness occur.
 BAD: not 1-to-1. Reverse
over-determined:

 BAD: not onto. Reverse

under-determined:

 GOOD: Bijection. Reverse

is a function:
8
One-to-One, Onto, Bijection.
Formal Definition.
DEF: A function f : A B is:
one-to-one (or injective) if different elements of A
always result in different images in B.
onto (or surjective) if every element in B is hit by f.
I.e., f (A ) = B.
a one-to-one correspondence (or a bijection, or
invertible) if f is both one-to-one as well as onto.
If f is invertible, its inverse f -1 : B A is well
defined by taking the unique element in the pre-
image of b, for each b  B.

9
One-to-One, Onto, Bijection.
Examples.
Q: Which of the following are 1-to-1, onto, a
bijection? If f is invertible, what is its
inverse?
1. f : Z  R is given by f (x ) = x 2
2. f : Z  R is given by f (x ) = 2x
3. f : R  R is given by f (x ) = x 3
4. f : Z  N is given by f (x ) = |x |
5. f : {people}  {people} is given by
f (x ) = the father of x.

10
One-to-One, Onto, Bijection.
Examples.
1. f : Z  R, f (x ) = x 2: none
2. f : Z  Z, f (x ) = 2x : 1-1
3. f : R  R, f (x ) = x 3: 1-1, onto,
bijection, inverse is f (x ) = x (1/3)
4. f : Z  N, f (x ) = |x |: onto
5. f (x ) = the father of x : none

11
The Identity Function
For any domain A, the identity function
I:AA (variously written, IA, 1, 1A) is
the unique function such that aA:
I(a)=a.
Some identity functions you’ve seen:
 ing 0, ·ing by 1, ing with T, ing with F,
ing with , ing with U.
Note that the identity function is always
both one-to-one and onto (bijective).
12
 Composition
When a function f spits out elements of the
same kind that another function g eats, f and
g may be composed by letting g immediately
eat each output of f.
DEF: Suppose that g : A  B and f : B  C
are functions. Then the composite
f g : A  C is defined by setting
f g (a) = f ( g (a) )

13
 Composition. Examples.
Q: Compute g f where
1. f : Z  R, f (x ) = x 2
and g : R  R, g (x ) = x 3
2. f : Z  Z, f (x ) = x + 1
and g = f -1 so g (x ) = x – 1
3. f : {people}  {people},
f (x ) = the father of x, and g = f
14
 Composition. Examples.
1. f : Z  R, f (x ) = x 2
and g : R  R, g (x ) = x 3
f g : Z  R , f g (x ) = x 6
2. f : Z  Z, f (x ) = x + 1
and g = f -1
f g (x ) = x (true for any function
composed with its inverse)
3. f : {people}  {people},
f (x ) = g(x ) = the father of x
f g (x ) = grandfather of x from father’s side
15
 Repeated Composition
When the domain and codomain are equal, a
function may be self composed. The
composition may be repeated as much as
desired resulting in functional
exponentiation. The whole process is
denoted by 
 n
f n (x ) = f f f f  … f (x )
where f appears n –times on the right side.
Q1: Given f : Z  Z, f (x ) = x 2 find f 4
Q2: Given g : Z  Z, g (x ) = x + 1 find g n
Q3: Given h(x ) = the father of x, find hn
16
 Repeated Composition
A1: f : Z  Z, f (x ) = x 2.
f 4(x ) = x (2*2*2*2) = x 16
A2: g : Z  Z, g (x ) = x + 1
gn (x ) = x + n
A3: h (x ) = the father of x,
hn (x ) = x ’s n’th patrilineal ancestor

17
 Ceiling and Floor
This being a course on discrete math, it is often
useful to discretize numbers, sets and
functions. For this purpose the ceiling and
floor functions come in handy.
DEF: Given a real number x : The floor of x is
the biggest integer which is smaller or equal to
x The ceiling of x is the smallest integer
greater or equal to x.
NOTATION: floor(x) = x , ceiling(x) = x 
Q: Compute 1.7, -1.7, 1.7, -1.7.

18
 Ceiling and Floor
A: 1.7 = 1, -1.7 = -2,
1.7 = 2, -1.7 = -1

Q: What’s the difference between the

floor function and the (int) casting
function in Java?

19
 Ceiling and Floor
A: Casting to int in Java always
truncates towards 0. Ceiling and floor
are not symmetric in this way.
EG: (int)(-1.7) == -1
-1.7 = -2

20
 Sequences
Sequences are a way of ordering lists of
objects. Arrays are a type of sequence of
finite size. Usually, mathematical sequences
are infinite.
To give an ordering to arbitrary elements, one
has to start with a basic model of order. The
basic model to start with is the set
N = {0, 1, 2, 3, …} of natural numbers.
For finite sets, the basic model of size n is:
n = {1, 2, 3, 4, …, n-1, n }
21
 Sequences
DEF: Given a set S, an (infinite) sequence in S is a
function N  S. A finite sequence in S is a
function
N  S.
Symbolically, a sequence is represented using the
subscript notation ai . This gives a way of specifying
formulaically
Note: The book often uses the positive numbers Z+ so
counting starts at 1 instead of 0. I’ll usually assume
the ordering model N.
Q: Give the first 5 terms of the sequence defined by
the formula
π
ai  cos( i )
2 22
 Sequence Examples
A: Plug in for i in sequence 0, 1, 2, 3, 4:
a 0  1, a1  0, a 2   1, a 3  0, a 4  1
Formulas for sequences often represent
patterns in the sequence.
Q: Provide a simple formula for each
sequence:
a) 3,6,11,18,27,38,51, …
b) 0,2,8,26,80,242,728,…
c) 1,1,2,3,5,8,13,21,34,…
23
 Sequence Examples
A: Try to find the patterns between numbers.
a) 3,6,11,18,27,38,51, …
a1=6=3+3, a2=11=6+5, a3=18=11+7, … and in
general ai +1 = ai +(2i +3). This is actually a good
enough formula. Later we’ll learn techniques that
show how to get the more explicit formula:
ai = 6 + 4(i –1) + (i –1)2
b) 0,2,8,26,80,242,728,…
If you add 1 you’ll see the pattern more clearly.
ai = 3i –1
c) 1,1,2,3,5,8,13,21,34,…
This is the famous Fibonacci sequence given by
ai +1 = ai + ai-1 24
 Finding General Pattern

Given a number sequence, can you find a general formula

for its terms?

a1, a2, a3, …, an, … General formula

1/4, 2/9, 3/16, 4/25, 5/36, … ai = i/(i+1)2

1/3, 2/9, 3/27, 4/81, 5/243,… ai = i/3i

0, 1, -2, 3, -4, 5, … ai = (i-1)·(-1)i

1, -1/4, 1/9, -1/16, 1/25, … ai = (-1)i+1 / i2

 Bit Strings
Bit strings are finite sequences of 0’s and 1’s.
Often there is enough pattern in the bit-string
to describe its bits by a formula.
EG: The bit-string 1111111 is described by the
formula ai =1, where we think of the string of
being represented by the finite sequence
a1a2a3a4a5a6a7
Q: What sequence is defined by
a1 =1, a2 =1 ai+2 = ai ai+1

26
 Bit Strings
A: a0 =1, a1 =1 ai+2 = ai ai+1:
1,1,0,1,1,0,1,1,0,1,…

27
 Summations
The symbol “S” takes a sequence of numbers
and turns it into a sum.
Symbolically: n

a
i 0
i  a0  a1  a2  ...  an
This is read as “the sum from i =0 to i =n of ai”
Note how “S” converts commas into plus signs.
One can also take sums over a set of numbers:
x
xS
2

28
 Summations
EG: Consider the identity sequence
ai = i
Or listing elements: 0, 1, 2, 3, 4, 5,…
The sum of the first n numbers is given
by: n

 ai  1  2  3  ...  n
i 1

(The first term 0 is dropped)

29
 Summation Formulas –
Arithmetic
There is an explicit formula for the previous:
n
n(n  1)

i 1
i
2
Intuitive reason: The smallest term is 1, the
biggest term is n so the avg. term is (n+1)/2.
There are n terms. To obtain the formula
simply multiply the average by the number of
terms.

30
Sum of a Sequence
 Summation Formulas –
Geometric
Geometric sequences are number
sequences with a fixed constant of
proportionality r between consecutive
terms. For example:
2, 6, 18, 54, 162, …
Q: What is r in this case?

32
 Summation Formulas
2, 6, 18, 54, 162, …
A: r = 3.
In general, the terms of a geometric sequence
have the form
ai = a r i
where a is the 1st term when i starts at 0.
A geometric sum is a sum of a portion of a
geometric sequence and has the following
explicit formula:
n 1
n
ar  a

i 0
ar  a  ar  ar  ...  ar 
i 2 n

r 1
33
 Summation Examples
If you are curious about how one could prove
such formulas, your curiosity will soon be
“satisfied” as you will become adept at
proving such formulas a few lectures from
now!
Q: Use the previous formulas to evaluate each
of the following
1.
103

 5(i  3)
i  20

13

2.  2 i

i 0 34
 Summation Examples
A:
1. Use the arithmetic sum formula and
additivity of summation:
103 103 103 103

 5(i  3)  5   (i  3)  5   i  5   3
i  20 i  20 i  20 i  20

(103  20)
 5  84   5  3  84  24570
2

35
 Summation Examples
A:
2. Apply the geometric sum formula
directly by setting a = 1 and r = 2:
13
214
 1 14

i 0
2 
i

2 1
 2  1  16383

36