Set Definition
• Set is a fundamental discrete structure on which all discrete
structures are built
• Sets are used to group objects, which often have the same
properties
Example
• Set of all the students who are currently taking Discrete
Mathematics 1 course.
• Set of all the subjects that K2011 students have to take in
the first semester.
• Set of natural numbers N

89 trang |

Chia sẻ: thuyduongbt11 | Ngày: 10/06/2022 | Lượt xem: 471 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu **Bài giảng Discrete structures for computer science - Chapter 3: Sets and Functions**, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên

Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.1
Chapter 4
Sets and Functions
Discrete Structures for Computer Science (CO1007) on Ngày
7 tháng 10 năm 2016
Nguyen An Khuong, Huynh Tuong Nguyen
Faculty of Computer Science and Engineering
University of Technology, VNU-HCM
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.2
Contents
1 Sets
2 Set Operation
3 Functions
4 One-to-one and Onto Functions
5 Sequences and Summation
6 Recursion
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.3
Set Definition
• Set is a fundamental discrete structure on which all discrete
structures are built
• Sets are used to group objects, which often have the same
properties
Example
• Set of all the students who are currently taking Discrete
Mathematics 1 course.
• Set of all the subjects that K2011 students have to take in
the first semester.
• Set of natural numbers N
Definition
A set is an unordered collection of objects.
The objects in a set are called the elements (phần tử ) of the set.
A set is said to contain (chứa) its elements.
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.4
Notations
Definition
• a ∈ A: a is an element of the set A
• a /∈ A: a is not an element of the set A
Definition (Set Description)
• The set V of all vowels in English alphabet, V = {a, e, i, o, u}
• Set of all real numbers greater than 1???
{x | x ∈ R, x > 1}
{x | x > 1}
{x : x > 1}
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.5
Equal Sets
Definition
Two sets are equal iff they have the same elements.
• (A = B)↔ ∀x(x ∈ A↔ x ∈ B)
Example
• {1, 3, 5} = {3, 5, 1}
• {1, 3, 5} = {1, 3, 3, 3, 5, 5, 5, 5}
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.6
Venn Diagram
• John Venn in 1881
• Universal set (tập vũ trụ) is
represented by a rectangle
• Circles and other
geometrical figures are used
to represent sets
• Points are used to represent
particular elements in set
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.7
Special Sets
• Empty set (tập rỗng) has no elements, denoted by ∅, or {}
• A set with one element is called a singleton set
• What is {∅}?
• Answer: singleton
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.8
Subset
Definition
The set A is called a subset (tập con) of B iff every element of A
is also an element of B, denoted by A ⊆ B.
If A 6= B, we write A ⊂ B and say A is a proper subset (tập con
thực sự) of B.
• ∀x(x ∈ A→ x ∈ B)
• For every set S,
(i) ∅ ⊆ S, (ii) S ⊆ S.
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.9
Cardinality
Definition
If S has exactly n distinct elements where n is non-negative
integers, S is finite set (tập hữu hạn), and n is cardinality (bản
số ) of S, denoted by |S|.
Example
• A is the set of odd positive integers less than 10. |A| = 5.
• S is the letters in Vietnamese alphabet, |S| = 29.
• Null set |∅| = 0.
Definition
A set that is infinite if it is not finite.
Example
• Set of positive integers is infinite
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.10
Power Set
Definition
Given a set S, the power set (tập lũy thừa) of S is the set of all
subsets of the set S, denoted by P (S).
Example
What is the power set of {0, 1, 2}?
P ({0, 1, 2}) = {∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}
Example
• What is the power set of the empty set?
• What is the power set of the set {∅}
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.11
Power Set
Theorem
If a set has n elements, then its power set has 2n elements.
Prove using induction!
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.12
Ordered n-tuples
Definition
The ordered n-tuple (dãy sắp thứ tự) (a1, a2, . . . , an) is the
ordered collection that has a1 as its first element, a2 as its second
element, . . ., and an as its nth element.
Definition
Two ordered n-tuples (a1, a2, . . . , an) = (b1, b2, . . . , bn) iff ai = bi,
for i = 1, 2, . . . , n.
Example
2-tuples, or ordered pairs (cặp), (a, b) and (c, d) are equal iff
a = c and b = d
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.13
Cartesian Product
• René Descartes (1596–1650)
Definition
Let A and B be sets. The Cartesian product (tích Đề-các) of A
and B, denoted by A×B, is the set of ordered pairs (a, b), where
a ∈ A and b ∈ B. Hence,
A×B = {(a, b) | a ∈ A ∧ b ∈ B}
Example
Cartesian product of A = {1, 2} and B = {a, b, c}. Then
A×B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}
Show that A×B 6= B ×A
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.14
Cartesian Product
Definition
A1×A2×· · ·×An = {(a1, a2, . . . , an) | ai ∈ Ai for i = 1, 2, . . . , n}
Example
A = {0, 1}, B = {1, 2}, C = {0, 1, 2}. What is A×B × C?
A×B × C = {(0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1),
(0, 2, 2), (1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 2, 0),
(1, 2, 1), (1, 2, 2)}
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.15
Union
Definition
The union (hợp) of A and B
A ∪ B = {x | x ∈ A ∨ x ∈ B}
A B
A ∪B
• Example:
• {1,2,3} ∪ {2,4} = {1,2,3,4}
• {1,2,3} ∪ ∅ = {1,2,3}
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.16
Intersection
Definition
The intersection (giao) of A and B
A ∩ B = {x | x ∈ A ∧ x ∈ B}
A B
A ∩B
Example:
• {1,2,3} ∩ {2,4} = {2}
• {1,2,3} ∩ N = {1,2,3}
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.17
Union/Intersection
n⋃
i=1
Ai = A1 ∪ A2 ∪ ... ∪ An = {x | x ∈ A1 ∨ x ∈ A2 ∨ ... ∨ x ∈ An}
n⋂
i=1
Ai = A1 ∩ A2 ∩ ... ∩ An = {x | x ∈ A1 ∧ x ∈ A2 ∧ ... ∧ x ∈ An}
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.18
Difference
Definition
The difference (hiệu) of A and B
A − B = {x | x ∈ A ∧ x /∈ B}
A B
A−B
Example:
• {1,2,3} - {2,4} = {1,3}
• {1,2,3} - N = ∅
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.19
Complement
Definition
The complement (phần bù) of A
A = {x | x /∈A}
Example:
• A = {1,2,3} then A = ???
• Note that A - B = A ∩ B
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.20
Set Identities
A ∪ ∅ = A Identity laws
A ∩ U = A Luật đồng nhất
A ∪ U = U Domination laws
A ∩ ∅ = ∅ Luật nuốt
A ∪A = A Idempotent laws
A ∩A = A Luật lũy đẳng
(A¯) = A Complementation law
Luật bù
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.21
Set Identities
A ∪B = B ∪A Commutative laws
A ∩B = B ∩A Luật giao hoán
A ∪ (B ∪ C) = (A ∪B) ∪ C Associative laws
A ∩ (B ∩ C) = (A ∩B) ∩ C Luật kết hợp
A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C) Distributive laws
A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C) Luật phân phối
A ∪ B = A ∩ B De Morgan’s laws
A ∩ B = A ∪ B Luật De Morgan
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.22
Method of Proofs of Set Equations
To prove A = B, we could use
• Venn diagrams
• Prove that A ⊆ B and B ⊆ A
• Use membership table
• Use set builder notation and logical equivalences
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.23
Example (1)
Example
Verify the distributive rule P ∪ (Q ∩R) = (P ∪Q) ∩ (P ∪R)
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.24
Example (2)
Example
Prove: A ∩B = A ∪B
(1) Show that A ∩B ⊆ A ∪B
Suppose that x ∈ A ∩B
By the definition of complement, x /∈ A ∩B
So, x /∈ A or x /∈ B
Hence, x ∈ A¯ or x ∈ B¯
We conclude, x ∈ A ∪B
Or, A ∩B ⊆ A ∪B
(2) Show that A ∪B ⊆ A ∩B
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.25
Example (3)
Prove: A ∩B = A ∪B
A B A ∩B A ∩B A¯ ∪ B¯
1 1 1 0 0
1 0 0 1 1
0 1 0 1 1
0 0 0 1 1
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.26
Example (4)
Prove: A ∩B = A ∪B
A ∩B = {x|x 6∈ A ∩B}
= {x|¬(x ∈ A ∩B)}
= {x|¬(x ∈ A ∧ x ∈ B)}
= {x|¬(x ∈ A) ∨ ¬(x ∈ B)}
= {x|x 6∈ A ∨ x 6∈ B}
= {x|x ∈ A ∨ x ∈ B}
= {x|x ∈ A ∪B}
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.27
Introduction
• Each student is assigned a grade from set
{0, 0.1, 0.2, 0.3, . . . , 9.9, 10.0} at the end of semester
• Function is extremely important in mathematics and
computer science
• linear, polynomial, exponential, logarithmic,...
• Don’t worry! For discrete mathematics, we need to
understand functions at a basic set theoretic level
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.28
Function
Definition
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
• A: domain (miền xác định) of f
• B: codomain (miền giá trị) of f
• For each a ∈ A, if f(a) = b
• b is an image (ảnh) of a
• a is pre-image (nghịch ảnh/tạo ảnh) of f(a)
• Range of f is the set of all images of elements of A
• f maps (ánh xạ) A to B
A B
a b = f(a)
f
f
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.29
Example
Example:
• y is an image of d
• c is a pre-image of z
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.30
Example
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?
Example
Let f : Z→ Z assign the the square of an integer to this integer.
What is f(x)? Domain, codomain, range of f?
• f(x) = x2
• Domain: set of all integers
• Codomain: Set of all integers
• Range of f : {0, 1, 4, 9, . . .}
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.31
Add and multiply real-valued functions
Definition
Let f1 and f2 be functions from A to R. Then f1 + f2 and f1f2
are also functions from A to R defined by
(f1 + f2)(x) = f1(x) + f2(x)
(f1f2)(x) = f1(x)f2(x)
Example
Let f1(x) = x
2 and f2(x) = x− x2. What are the functions
f1 + f2 and f1f2?
(f1 + f2)(x) = f1(x) + f2(x) = x
2 + x− x2 = x
(f1f2)(x) = f1(x)f2(x) = x
2(x− x2) = x3 − x4
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.32
Image of a subset
Definition
Let f : A→ B and S ⊆ A. The image of S:
f(S) = {f(s) | s ∈ S}
f({a, b, c, d}) = {x, y, z}
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.33
One-to-one
Definition
A function f is one-to-one or injective (đơn ánh) if and only if
∀a∀b (f(a) = f(b)→ a = b)
• Is f : Z→ Z, f(x) = x + 1
one-to-one?
• Is f : Z→ Z, f(x) = x2
one-to-one?
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.34
Onto
Definition
f : A→ B is onto or surjective (toàn ánh) if and only if
∀b ∈ B, ∃a ∈ A : f(a) = b
• Is f : Z→ Z, f(x) = x + 1
onto?
• Is f : Z→ Z, f(x) = x2
onto?
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.35
One-to-one and onto (bijection)
Definition
f : A→ B is bijective (one-to-one correspondence) (song ánh) if
and only if f is injective and surjective
• Let f be the function from
{a, b, c, d} to {1, 2, 3, 4}
with f(a) = 4, f(b) = 2,
f(c) = 1, f(d) = 3. Is f a
bijection?
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.36
Example
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.37
Inverse function (Hàm ngược)
Definition
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)
because we can define the inverse of this function.
A B
a = f−1(b) b = f(a)
f(a)
f−1(b)
f−1
f
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.38
Example
Example
A = {a, b, c} and B = {1, 2, 3} with
f(a) = 2 f(b) = 3 f(c) = 1
f is invertible and its inverse is
f−1(1) = c f−1(2) = a f−1(3) = b
Example
Let f : R→ R with f(x) = x2. If f invertible?
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.39
Example
f : R→ R
f(x) = 2x + 1
f−1 : R→ R
f−1(x) =
x− 1
2
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.40
Function Composition
Definition
Given a pair of functions g : A→ B and f : B → C. Then the
composition (hợp thành) of f and g, denoted f ◦ g is defined by
f ◦ g : A→ C
f ◦ g(a) = f(g(a))
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.41
Example
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.42
Graphs of Functions
Example
The graph of f(x) = x2 from Z to Z.
(−3, 9)
(−2, 4)
(−1, 1)
(0, 0)
(1, 1)
(2, 4)
(3, 9)
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}.
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.43
Important Functions
Definition
Floor function (hàm sàn) of x (bxc): the largest integer ≤ x
b 12c = 0, b3.1c = 3, b7c = 7
Ceiling function (hàm trần) of x (dxe): the smallest integer ≥ x
d 12e = 1, d3.1e = 4, d7e = 7
Bảng: Properties (n is an integer, x is a real number)
(1a) bxc = n iff n ≤ x < n + 1
(1b) dxe = n iff n− 1 < x ≤ n
(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
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.44
Sequences
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)
Example
1, 12 ,
1
4 ,
1
8 ,
1
16 , . . . an =
1
2n−1
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
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.45
Recurrence Relations
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
Definition (Fibonacci Sequence)
Initial condition: f0 = 0 and f1 = 1
fn = fn−1 + fn−2 for n = 2, 3, 4, . . .
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
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.46
Exercise (1)
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
{Pn} satisfies the recurrence relation
Pn = Pn−1 + 0.11Pn−1 = (1.11)Pn−1.
The initial condition is P0 = 10, 000
Step 1. Solve the recurrence relation (iteration technique)
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.
Step 2. Calculate
P30 = (1.11)
3010, 000 = $228, 922.97.
Sets and Functions
Nguyen An Khuong,
Huynh Tuong Nguyen
Contents
Sets
Set Operation
Functions
One-to-one and Onto
Functions
Sequences and
Summation
Recursion
4.47
Exercise (2)
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