Functions

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen

Chapter 5 Ngoc Le

Functions
Discrete Structures for Computing
Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation

Recursion

Huynh Tuong Nguyen, Tran Tuan Anh, Nguyen Ngoc Le

Faculty of Computer Science and Engineering
University of Technology - VNUHCM
{htnguyen;trtanh}@[Link]
5.1
 Functions
Contents
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

1 Functions

Contents

Functions
2 One-to-one and Onto Functions One-to-one and Onto
Functions

Sequences and
Summation

3 Sequences and Summation Recursion

4 Recursion

5.2
 Functions
Course outcomes
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Course learning outcomes

L.O.1 Understanding of logic and discrete structures

L.O.1.1 – Describe definition of propositional and predicate logic
L.O.1.2 – Define basic discrete structures: set, mapping, graphs
Contents
L.O.2 Represent and model practical problems with discrete structures Functions
L.O.2.1 – Logically describe some problems arising in Computing One-to-one and Onto
L.O.2.2 – Use proving methods: direct, contrapositive, induction Functions

L.O.2.3 – Explain problem modeling using discrete structures Sequences and

Summation

L.O.3 Understanding of basic probability and random variables Recursion

L.O.3.1 – Define basic probability theory

L.O.3.2 – Explain discrete random variables

L.O.4 Compute quantities of discrete structures and probabilities

L.O.4.1 – Operate (compute/ optimize) on discrete structures
L.O.4.2 – Compute probabilities of various events, conditional
ones, Bayes theorem

5.3
 Functions
Introduction
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

• Each student is assigned a grade from set

Contents
{0, 0.1, 0.2, 0.3, . . . , 9.9, 10.0} at the end of semester Functions
• Function is extremely important in mathematics and One-to-one and Onto
computer science Functions

Sequences and
• linear, polynomial, exponential, logarithmic,... Summation

• Don’t worry! For discrete mathematics, we need to Recursion

understand functions at a basic set theoretic level

5.4
 Functions
Function
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Definition Ngoc Le

Let A and B be nonempty sets. A function f from A to B is an

assignment of exactly one element of B to each element of A.
• f :A→B
tu 1A -> duy nhat 1 B
• A: domain (miền xác định) of f
Contents
• B: codomain (miền giá trị) of f Functions
• For each a ∈ A, if f (a) = b One-to-one and Onto
• b is an image (ảnh) of a Functions

• a is pre-image (nghịch ảnh) of f (a) Sequences and

Summation
• Range of f is the set of all images of elements of A Recursion

• f maps (ánh xạ) A to B

f
a b = f (a)

A B
f
5.5
 Functions
Example
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Example:
• y is an image of d
• c is a pre-image of z Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation

Recursion

5.6
 Functions
Example
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Example
What are domain, codomain, and range of the function that
assigns grades to students includes: student A: 5, B: 3.5, C: 9, D:
5.2, E: 4.9? Contents

Functions

One-to-one and Onto

Example Functions

Let f : Z → Z assign the the square of an integer to this integer. Sequences and
Summation
What is f (x)? Domain, codomain, range of f ? Recursion

• f (x) = x2
• Domain: set of all integers
• Codomain: Set of all integers
• Range of f : {0, 1, 4, 9, . . .}

5.7
 Functions
Add and multiply real-valued functions
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Definition
Let f1 and f2 be functions from A to R. Then f1 + f2 and f1 f2
are also functions from A to R defined by
(f1 + f2 )(x) = f1 (x) + f2 (x) Contents

Functions
(f1 f2 )(x) = f1 (x)f2 (x) One-to-one and Onto
Functions

Sequences and
Summation
Example Recursion

Let f1 (x) = x2 and f2 (x) = x − x2 . What are the functions

f1 + f2 and f1 f2 ?
(f1 + f2 )(x) = f1 (x) + f2 (x) = x2 + x − x2 = x
(f1 f2 )(x) = f1 (x)f2 (x) = x2 (x − x2 ) = x3 − x4

5.8
 Functions
Image of a subset
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Definition
Let f : A → B and S ⊆ A. The image of S:

f (S) = {f (s) | s ∈ S} Contents

Functions

One-to-one and Onto

Functions

f ({a, b, c, d}) = {x, y, z} Sequences and

Summation

Recursion

5.9
 Functions
One-to-one
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Definition
A function f is one-to-one or injective (đơn ánh) if and only if
Contents
∀a∀b (f (a) = f (b) → a = b) Functions

One-to-one and Onto

Functions

Sequences and
Summation

• Is f : Z → Z, f (x) = x + 1 Recursion

one-to-one?
• Is f : Z → Z, f (x) = x2
one-to-one?

5.10
 Functions
Onto
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Definition
f : A → B is onto or surjective (toàn ánh) if and only if
Contents
∀b ∈ B, ∃a ∈ A : f (a) = b Functions

One-to-one and Onto

Functions

Sequences and
Summation

• Is f : Z → Z, f (x) = x + 1 Recursion

onto?
• Is f : Z → Z, f (x) = x2
onto?

5.11
 Functions
One-to-one and onto (bijection)
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Definition
f : A → B is bijective (one-to-one correspondence) (song ánh) if
Contents
and only if f is injective and surjective
Functions

One-to-one and Onto

Functions

• Let f be the function from Sequences and

Summation
{a, bc, d} to {1, 2, 3, 4} with Recursion
f (a) = 4, f (b) = 2,
f (c) = 1, f (d) = 3. Is f a
bijection?

5.12
 Functions
Example
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation

Recursion

5.13
 Functions
Inverse function (Hàm ngược)
Huynh Tuong Nguyen,
Definition Tran Tuan Anh, Nguyen
Ngoc Le

Let f : A → B be a bijection then the inverse of f is the function

f − : B → A defined by

if f (a) = b then f − (b) = a

A one-to-one correspondence is call invertible (khả nghịch) Contents

because we can define the inverse of this function. Functions

One-to-one and Onto

Functions

Sequences and
f (a) Summation

Recursion

a = f −1 (b) f −1 (b) b = f (a)

A f B

f −1
5.14
 Functions
Example
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Example
A = {a, b, c} and B = {1, 2, 3} with
Contents
f (a) = 2 f (b) = 3 f (c) = 1 Functions

One-to-one and Onto

f is invertible and its inverse is Functions

Sequences and
Summation
−1 −1 −1
f (1) = c f (2) = a f (3) = b Recursion

Example
Let f : R → R with f (x) = x2 . If f invertible?

5.15
 Functions
Example
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

f :R→R
Contents

Functions
f (x) = 2x + 1 One-to-one and Onto
Functions

Sequences and
f −1 : R → R Summation

Recursion

x−1
f −1 (x) =
2

5.16
 Functions
Function Composition
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Definition
Given a pair of functions g : A → B and f : B → C. Then the Contents

Functions
composition (hợp thành) of f and g, denoted f ◦ g is defined by
One-to-one and Onto
Functions
f ◦g :A→C Sequences and
Summation

Recursion
f ◦ g(a) = f (g(a))

5.17
 Functions
Example
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation

Recursion

5.18
 Functions
Graphs of Functions
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Example
The graph of f (x) = x2 from Z to Z.

(−3, 9) (3, 9)
Contents

Functions

One-to-one and Onto

(−2, 4) (2, 4) Functions

Sequences and
Summation

(−1, 1) (1, 1) Recursion

(0, 0)

Definition
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}.

5.19
 Functions
Important Functions
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Definition Ngoc Le

Floor function (hàm sàn) of x (bxc): the largest integer ≤ x

b 12 c = 0, b3.1c = 3, b7c = 7
Ceiling function (hàm trần) of x (dxe): the smallest integer ≥ x
d 21 e = 1, d3.1e = 4, d7e = 7
Contents

Functions
Bảng: Properties (n is an integer, x is a real number) One-to-one and Onto
Functions

Sequences and
(1a) bxc = n iff n≤x<n+1 Summation

(1b) dxe = n iff n−1<x≤n Recursion

(1c) bxc = n iff x−1<n≤x

(1d) dxe = n iff x≤n<x+1
(2) x − 1 < bxc ≤ dxe < x + 1
(3a) b−xc = −dxe
(3b) d−xe = −bxc
(4a) bx + nc = bxc + n
(4b) dx + ne = dxe + n
5.20
 Functions
Sequences
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

What are the rule of these sequences (dãy )?

Example
1, 3, 5, 7, 9, . . . an = 2n − 1
Arithmetic sequence (cấp số cộng ) Contents

Functions

One-to-one and Onto

Functions
Example
Sequences and

1, 12 , 14 , 81 , 16
1 1 Summation
,... an = 2n−1
Recursion
Geometric sequence (cấp số nhân)

Example
{an } 5, 11, 17, 23, 29, 35, 41, 47, . . . an = 6n − 1
{bn } 1, 7, 25, 79, 241, 727, 2185, . . . bn = 3n − 2

5.21
 Functions
Recurrence Relations
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le
Example
{an } 5, 11, 17, 23, 29, 35, 41, 47, . . .
an = an−1 + 6 for n = 2, 3, 4, . . . and a1 = 5
Recurrence relations: công thức truy hồi

Contents

Functions
Definition (Fibonacci Sequence)
One-to-one and Onto
Functions
Initial condition: f0 = 0 and f1 = 1
Sequences and
fn = fn−1 + fn−2 for n = 2, 3, 4, . . . Summation

Recursion

Example
Find the Fibonacci numbers f2 , f3 , f4 , f5 and f6
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
5.22
 Functions

Exercise (1) Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
Ngoc Le
Initial deposit: $10,000
Interest: 11%/year, compounded annually (lãi suất kép)
After 30 years, how much do you have in your account?
Solution:
Let Pn be the amount in the account after n years. The sequence Contents

{Pn } satisfies the recurrence relation Functions

Pn = Pn−1 + 0.11Pn−1 = (1.11)Pn−1 . One-to-one and Onto

Functions
The initial condition is P0 = 10, 000 Sequences and
Summation
Step 1. Solve the recurrence relation (iteration technique) Recursion
P1 = (1.11)P0
P2 = (1.11)P1 = (1.11)2 P0
P3 = (1.11)P2 = (1.11)3 P0
..
.
Pn = (1.11)Pn−1 = (1.11)n P0 .
Step 2. Calculate
P30 = (1.11)30 10, 000 = $228, 922.97.
5.23
 Functions

Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
Exercise (2) Ngoc Le

What is the 2012th number in the sequence {xn }: 1, 2, 2, 3, 3, 3,

4, 4, 4, 4, 5, 5, 5, 5, 5, 6,. . .
Solution:
In this sequence, integer 1 appears once, the integer 2 appears
twice, the integer 3 appears three times, and so on. Therefore Contents

Functions
integer n appears n times in the sequence.
One-to-one and Onto
Functions
We can prove that (try it!)
n Sequences and
X n(n + 1) Summation
i = 1 + 2 + 3 + ... + n = Recursion
i=1
2
and can easily calculate that
X62
i = 1953
i=1
so the next 63 numbers (until 2016) is 63.
Therefore, 2012th number in the sequence is 63.

5.24
 Functions

Theorem Huynh Tuong Nguyen,

Tran Tuan Anh, Nguyen
If a and r are real numbers and r 6= 0, then Ngoc Le

n  ar n+1 −a
X if r 6= 1
arj = r−1
j=0
(n + 1)a if r = 1.

Contents

Chứng minh. Functions

Pn j One-to-one and Onto
Let Sn = j=0 ar . Functions

Sequences and
Pn Summation
rSn = r j=0 arj Recursion
Pn
= j=0 arj+1
Pn+1
=  k=1 ark 
Pn k
= k=0 ar + (arn+1 − a)
= Sn + (arn+1 − a)

ar n+1 −a
Solving for Sn shows that if r 6= 1, then Sn = r−1
Pn
If r = 1, then Sn = j=0 a = (n + 1)a

5.25
 Functions
Recursion
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Definition (Recurrence Relation) Ngoc Le

An equation that recursively defines a sequence.

Definition (Recursion (đệ quy))

The act of defining an object (usually a function) in terms of that Contents

object itself. Functions

One-to-one and Onto

Functions

Sequences and
Summation

Recursion

5.26
 Functions
Recursive Algorithms
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Definition
An algorithm is called recursive if it solves a problem by reducing
it to an instance of the same problem with smaller input.

Contents

Example Functions

One-to-one and Onto

Give a recursive algorithm for computing n!, where n is a Functions

nonnegative integer. Sequences and

Summation

Recursion
Solution. We base on the recursive definition of n!:
n! = n · (n − 1)! and 0! = 1.
procedure factorial (n: nonnegative integer)
if n = 0 then return 1
else return n· factorial (n - 1)
{output is n!}

5.27
 Functions
Algorithms for Fibonacci Numbers
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Recursive Algorithm Ngoc Le

procedure fibonacci(n: nonnegative integer)

if n = 0 then return 0
else if n = 1 then return 1
else return fibonacci(n-1) + fibonacci(n-2)
{output is fibonacci(n)} Contents

Functions

Iterative Algorithm One-to-one and Onto

Functions

procedure iterative fibonacci(n: nonnegative integer) Sequences and

Summation
if n = 0 then return 0 Recursion
else
x := 0
y := 1
for i := 1 to n − 1
z := x + y
x := y
y := z
return y
{output is the nth Fibonacci number}
5.28
 Functions
Tower of Hanoi
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

There is a tower in Hanoi that has three pegs mounted on a board

together with 64 gold disks of different sizes.
Initially, these disks are placed on the first peg in order of size,
Contents
with the largest on the borrom. Functions

The rules: One-to-one and Onto

Functions

1 Move one at a time from one peg to another Sequences and

Summation

2 A disk is never placed on top of a smaller disk Recursion

Goals: all the disks on the third peg in order of size.

The myth says that the world will end when they finish the
puzzle.

5.29
 Functions
Tower of Hanoi – 64 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

1
2
3
4
? Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation
5 Recursion

5.30
 Functions
Tower of Hanoi – 1 Disc
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation

Recursion

5.31
 Functions
Tower of Hanoi – 1 Disc
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation

Recursion

Moved disc from peg 1 to peg 3.

5.32
 Functions
Tower of Hanoi – 1 Disc
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

OK Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation

Recursion

5.33
 Functions
Tower of Hanoi – 2 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation
1 Recursion

5.34
 Functions
Tower of Hanoi – 2 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation

Recursion

2 1

Moved disc from peg 1 to peg 2.

5.35
 Functions
Tower of Hanoi – 2 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation

Recursion

1 2

Moved disc from peg 1 to peg 3.

5.36
 Functions
Tower of Hanoi – 2 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation
1 Recursion

Moved disc from peg 2 to peg 3.

5.37
 Functions
Tower of Hanoi – 2 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

OK Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation
1 Recursion

5.38
 Functions
Tower of Hanoi – 3 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions
1 Sequences and
Summation
2 Recursion

5.39
 Functions
Tower of Hanoi – 3 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation
2 Recursion

3 1

Moved disc from peg 1 to peg 3.

5.40
 Functions
Tower of Hanoi – 3 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation

Recursion

3 2 1

Moved disc from peg 1 to peg 2.

5.41
 Functions
Tower of Hanoi – 3 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation
1 Recursion

3 2

Moved disc from peg 3 to peg 2.

5.42
 Functions
Tower of Hanoi – 3 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation
1 Recursion

2 3

Moved disc from peg 1 to peg 3.

5.43
 Functions
Tower of Hanoi – 3 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation

Recursion

1 2 3

Moved disc from peg 2 to peg 1.

5.44
 Functions
Tower of Hanoi – 3 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation
2 Recursion

1 3

Moved disc from peg 2 to peg 3.

5.45
 Functions
Tower of Hanoi – 3 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions
1 Sequences and
Summation
2 Recursion

Moved disc from peg 1 to peg 3.

5.46
 Functions
Tower of Hanoi – 3 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

OK 1
Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation
2 Recursion

5.47
 Functions
Tower of Hanoi – 4 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

1 One-to-one and Onto

Functions
2 Sequences and
Summation
3 Recursion

5.48
 Functions
Tower of Hanoi – 4 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions
2 Sequences and
Summation
3 Recursion

4 1

Moved disc from peg 1 to peg 2.

5.49
 Functions
Tower of Hanoi – 4 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation
3 Recursion

4 1 2

Moved disc from peg 1 to peg 3.

5.50
 Functions
Tower of Hanoi – 4 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation
3 1 Recursion

4 2

Moved disc from peg 2 to peg 3.

5.51
 Functions
Tower of Hanoi – 4 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation
1 Recursion

4 3 2

Moved disc from peg 1 to peg 2.

5.52
 Functions
Tower of Hanoi – 4 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation
1 Recursion

4 3 2

Moved disc from peg 3 to peg 1.

5.53
 Functions
Tower of Hanoi – 4 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation
1 2 Recursion

4 3

Moved disc from peg 3 to peg 2.

5.54
 Functions
Tower of Hanoi – 4 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions
1 Sequences and
Summation
2 Recursion

4 3

Moved disc from peg 1 to peg 2.

5.55
 Functions
Tower of Hanoi – 4 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions
1 Sequences and
Summation
2 Recursion

3 4

Moved disc from peg 1 to peg 3.

5.56
 Functions
Tower of Hanoi – 4 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation
2 1 Recursion

3 4

Moved disc from peg 2 to peg 3.

5.57
 Functions
Tower of Hanoi – 4 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation
1 Recursion

2 3 4

Moved disc from peg 2 to peg 1.

5.58
 Functions
Tower of Hanoi – 4 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation
1 Recursion

2 3 4

Moved disc from peg 3 to peg 1.

5.59
 Functions
Tower of Hanoi – 4 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation
1 3 Recursion

2 4

Moved disc from peg 2 to peg 3.

5.60
 Functions
Tower of Hanoi – 4 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation
3 Recursion

2 1 4

Moved disc from peg 1 to peg 2.

5.61
 Functions
Tower of Hanoi – 4 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

One-to-one and Onto

Functions
2 Sequences and
Summation
3 Recursion

1 4

Moved disc from peg 1 to peg 3.

5.62
 Functions
Tower of Hanoi – 4 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

Contents

Functions

1 One-to-one and Onto

Functions
2 Sequences and
Summation
3 Recursion

Moved disc from peg 2 to peg 3.

5.63
 Functions
Tower of Hanoi – 4 Discs
Huynh Tuong Nguyen,
Tran Tuan Anh, Nguyen
Ngoc Le

OK 1
2
Contents

Functions

One-to-one and Onto

Functions

Sequences and
Summation
3 Recursion

5.64
 Functions
Tower of Hanoi
Huynh Tuong Nguyen,
Algorithm Tran Tuan Anh, Nguyen
Ngoc Le

procedure hanoi(n, A, B, C)
if n = 1 then move the disk from A to C
else
call hanoi(n − 1, A, C, B)
move disk n from A to C Contents
call hanoi(n − 1, B, A, C) Functions

One-to-one and Onto

Functions
Recurrence Relation Sequences and
Summation

1 if n = 1 Recursion
H(n) =
2H(n − 1) + 1 if n > 1.

Recurrence Solving
H(n) = 2n − 1
If one move takes 1 second, for n = 64

264 − 1 ≈ 2 × 1019 sec

≈ 500 billion years!.
5.65