Sequences – Definition of Sequence

• Sequence is a list of number of objects in a special order.

•Example:

•3, 5, 7, 9, …… is a sequence starting at 3 and increasing by 2 each time.

• A sequence is a (finite or infinite) set of numbers.

Example problem involving Sequence

Problem Number One:

If the first three terms of an arithmetic sequence are 2, 6 and 10, find the 40th term.

To solve the problem we use this formula for finding the nth term of an arithmetic sequence.

An = A + (n - 1) d

Where, An = is the nth term, in the case of our problem it is the 40th term

A = the first term of the sequence, in our problem it is 2.

n = number of terms, in our problem it is 40.

d = the interval of the terms, or the difference of the next term from the previous term,

to get d; d = 6 - 2 = 4.

Now, it is time to substitute the values to the formula for solving nth term where the 40th term is to be solved.

An = 2 + (40 - 1) 4

An = 2 + (39) 4

An = 2 + 156

An = 158.

The 40th term of the arithmetic sequence is 158.

Problem Number Two:

If the first term of an arithmetic sequence is -3 and the eighth term is 11, find d and write the first 10 terms of the sequence.

In this problem,

A = -3 n = 8 A8 = 11

If these values are substituted in the formula for An, we have

11 = -3 + (8 - 1) d

11 = -3 + 7d

14 = 7d

d = 2

The first ten terms are -3, -1, 1, 3, 5, 7, 9, 11, 13, 15

Arithmetic Progression

• A sequence in which the difference between any two successive terms is constant is called an arithmetic sequence @ arithmetic progression.
• The constant difference is called the common difference.
• Denoted by d.

Geometric Progression

• A sequence in which the ratio of every pair of successive terms is constant is called a geomatric sequence @ geometric progression
• The constant ratio is called the common ratio.
• Denoted by r.

List down the principle of mathematical induction.

To prove that P(n) is true for all positive integers n, where P(n) is a propositional function

11)   verify that P(1) is true.

22)   Show that the conditional statement P(k) → P(k + 1) is true for all positive 

integers k. The technique that we’ve used in the above example to determine if all the values are true or not, is called mathematical induction. 

Template proof by mathematical induction

1.express to be proved in the form “for all n ≥ b, P(n) for integer b


2.write “Basic Step”. 


Show that P(b) is true,take the correct value of b used is used.


3.write word “Inductive Step”


4.state clearly the inductive hypothesis in the “ assume that p(k) is true for an arbitrary


fixed integer k ≥ b ”


5.proved under assumption that inductive is true


Write P(k + 1) says


6.prove P(k + 1),make assumption P(k)
,

Make sure proof is valid for all integer k with k ≥ b

,
taking care proof work for small value of k, including k = b


7.conclusion of the induction step, saying “ this complete the inductive step”


8.namely that by mathematical induction P(n) is true for all integer n ≥ b

Use of Sequence in Computer Programming

Example:

First of all, we need to write a  program. 

The output should looks like this.

The output of  product is presented in sequence form.

Use of Sequence in Computer Programming

Example:

First of all, we need to write a  program.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

The output should looks like this.

The output of  product is presented in sequence form.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Function

FUNCTION

Definition of function

function is a relationship between two quantities, one of which is completely determined by the value of the other. A function f from a set X to a set Y is a relation between the elements of X (called the inputs) and the elements of Y (called the outputs) with the property that each input is related to one and only one output. We use the notation

f : X → Y

Concept of Boolean Functions

An expression that is form with binary variables. It can be represented as an algebraic expression or in truth table.

      

       TYPES  OF FUNCTION

1.      INJECTIVE

o   one-to-one

o   f  is called injective when the a = b

o   can express in quantifier

2.      SURJECTIVE

o   onto

o   f  is called surjective when there is a function from element A to element B

3.      BIJECTIVE

o   one-to-one correspondence

o   f  becomes function when no value in  the domain are signed to the same function value

o   no repeatation of domain

Inverse function and composition of function

Inverse function

Definition :-

¨      Let f  be one-to-one correspondence from the set A to the set B

¨      f  is the function that assign to be an element b belonging to B the unique element a in A such that f (a) = b

¨      Function of f is denoted by  f ˉ ¹ then  f ˉ ¹( b) = a when f (a) = b

       

        example

                           is the relation 

      

Composition function

¨       Let g be a function from the set A to the set B and let f be a function from the set B to the set C

¨      Function f and g, denoted for all a Î A by  f  ° g is defined by

      

           ( f  ° g )(a) = f( g(a) )

      

  example

                   f  ° g is defined  by   ( f  ° g )(a) = f  ( g(a)) = f (b) = 2

               ( f  ° g )(b) =  f ( g(b)) = f(c) =1 and ( f  ° g )(c) =  f ( g(c)) = f(a) =3

       Noted that:-

                f  ° g is not defined because the range of   f  is not a subset of domain of  g

   

                                                                           

Computer Representation of Sets

Computer Representation of Sets

    Method for storing elements using an arbitrary ordering of the elements of the universal
    set.Specify an arbitrary ordering of the elements of U, for instance a1, a2, . . . , an. Represent a 
    subset A of U with the bit string of length n, where the ith bit in this string is 1 if ai belongs to A
    and is 0 if ai does not belong to A.

Example1: Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.

i)What bit strings represent the subset of all odd integers in U?

  The bit string that represents the set of odd integers in U, {1, 3, 5, 7, 9}, has a one bit in the

  first, third, fifth, seventh, and ninth positions. It is 10 1010 1010.

ii)What bit strings represent the subset of all even integers in U?

   The bit string that  represent the subset of  even integers in U,{2, 4, 6, 8, 10}.

   It is 01 0101 0101.

iii)What bit strings represent the subset of integers not exceeding 5 in U? 

    The set of all integers in U that do not exceed 5, {1, 2, 3, 4, 5}, is represented by the

    string 11 1110 0000.

To find the bit string for the complement of a set from the bit string for that set, change each 1 to 0 and each 0 to 1.

Example 2:The bit string for the set {1, 3, 5, 7, 9} (with universal set {1, 2, 3, 4,

5, 6, 7, 8, 9, 10}) is 10 1010 1010.

What is the bit string for the complement of this set?

The bit string for the complement of this set is obtained by replacing 0s with 1s.

This yields the string 01 0101 0101,which corresponds to the set {2, 4, 6, 8, 10}.

To obtain the bit string for the union and intersection of two sets we perform bitwise Boolean

operations on the bit strings representing the two sets.

Example 3:The bit strings for the sets {1, 2, 3, 4, 5} and {1, 3, 5, 7, 9} are 11 1110 0000 and 10 1010 1010.

The bit string for the union of these sets is 11 1110 0000 ∨ 10 1010 1010 = 11 1110 1010,

which corresponds to the set {1, 2, 3, 4, 5, 7, 9}.

If either of the bits in the ith position in the two strings is 1 (or both are 1),the bit in the ith position of the bit string of the union is 1. When both bits are 0, is 0. Hence, the bit string for union is the bitwise OR of the bit strings for the two sets.

The bit string for the intersection of these sets is

11 1110 0000 ∧ 10 1010 1010 = 10 1010 0000, which corresponds to the set {1, 3, 5}.

When the bits in the corresponding position in the two strings are both 1,the bit in the ith position of the bit string of the intersection is 1. When either of the two bits is 0 (or both are 0) ,is 0. Hence, the bit string for the intersection is the bitwise AND of the bit strings for the two sets.

Properties of Relations

• Reflexive
• Irreflexive
• Symmetric
• Antisymmetric
• Transitive

[1] Reflexive

     A reflexive relation is a binary relation on a set for which every element is related to itself.

Example

A={1,2,3}

R={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}

R is reflexive because they contains all pairs of the form (a,a), namely (1,1),(2,2)&(3,3)

       

[2] Irreflexive

     A irreflexive relation is a binary relation on a set for which is false for every element.

" a Î A,(a,a) Ï R

Example

These 4 irreflexive relations are :

1. Empty
2. {(1,2)}
3. {(2,1)}
4. {(1,2),(2,1)}

[3] Symmetric

     A symmetric relation is a binary relation on a set  A if  (a,b) Î R = (b,a) Î R  

R={(1,1),(1,2),(2,1),(2,2)}

R is symmetric because both (1,2) and (2,1) are in the relation.

[4] Antisymmetric

     A binary relation a on a set A is antisymmetric whenever (a, b) Î R and (b, a) Î R , then a=b

Example

R={(2, 1), (3, 1), (4, 1), (3, 2), (4, 2), (4, 3)}

R is antisymmetric because there is no pair of element a and b.

a ≠ b (a,b) & (b,a).

[5] Transitive

A binary relation a on a set A is transitive (a,b) Î R and (b,c) Î R = (a,c) Î R     

Example

A={1,2,3,4}

answer:

R={(1,1),(1,2),(2,2),(2,3),(1,3),(3,3)}

     

       

Generalised Union and Intersection


Generalised Union

• The union of a collection of set is a 
• set that contains those elements that are members of at 
• least one set in the collection
  
  
•      A ∪ (B ∪ C) = (A ∪ B) ∪ C

• 
  A = {0,2,4,6}, B = {0,1,3,5,7}, C = {0,1,2,3}
• 
  
  A ∪ B ∪ C = {0,1,2,3,4,5,6,7}

• 
  

Generalised Intersection

• The intersection of a collection of sets is a set that 
• contains those elements that are members all the sets in 
• the collection
• 
  

•     A ∩ (B ∩ C) = (A ∩ B) ∩ C

• A = {0,2,4,6}, B = {0,1,3,5,7}, C = {0,1,2,3}
• 
  
  A ∩ B ∩ C = {0}

Cartesian Product

 The direct product of two sets

Specifically, the Cartesian product of two sets X and Y denoted  X × Y, is the set of all possible ordered pairs whose first component is a member of X and whose second component is a member of Y

Example

A={abu,dol}

B={cow,goat,camel}

What is the cartesian product of A x B ?

  

       A x B ={(abu,cow),(abu,goat),(abu,camel),(dol,cow),(dol,goat),(dol,camel)}

Take note !!

      A x B  B x A

POWER SET

The power set of a set A is the set of all its subsets (including, of course, itself and the empty set). It is denoted by P(A).

Using set comprehension notation, P(A) can be defined as

P(A) = { Q | Q⊆A }

Example 4

Write down the power sets of A if:

(a) A = {1, 2, 3}

(b) A = {1, 2}

(c) A = {1}

(d) A = ø

Solution

(a) P(A) = { {1, 2, 3}, {2, 3}, {1, 3}, {1, 2}, {1}, {2}, {3}, ø }

(b) P(A) = { {1, 2}, {1}, {2}, ø }

(c) P(A) = { {1}, ø }

(d) P(A) = { ø }

SET OPERATION

·         Union

Definition (Union): The union of sets A and B, denoted by AB , is the set defined as :-
             AB = { x | xAxB }

Example 1: If A = {1, 2, 3} and B = {4, 5} ,  then AB = {1, 2, 3, 4, 5} .

Example 2: If A = {1, 2, 3} and B = {1, 2, 4, 5} ,  then AB = {1, 2, 3, 4, 5} .

Note that elements are not repeated in a set.

·         Intersection

Definition (Intersection): The intersection of sets A and B, denoted by AB , is the set defined as :-
             AB = { x | xAxB }

Example 3: If A = {1, 2, 3} and B = {1, 2, 4, 5} ,  then AB = {1, 2} .

Example 4: If A = {1, 2, 3} and B = {4, 5} ,  then AB = .

·         Disjoin Set  (Non-Overlapping Sets )

Two or more sets which have no elements in common. For example, the sets A = {a,b,c} and B = {d,e,f} are disjoint.

·         Set Difference

Definition (Difference): The difference of sets A from B , denoted by A- B , is the set defined as

             A- B = { x | xAxB }

Example 5: If A = {1, 2, 3} and B = {1, 2, 4, 5} ,  then A- B = {3} .
Example 6: If A = {1, 2, 3} and B = {4, 5} ,  then A- B = {1, 2, 3} .

Note that in general A- BB–A

·         Set Complimentary

The set of elements that are not in a set A is called the complement of A. It is written A′ (or sometimes A^C, or ).

Clearly, this is the set of elements that answer 'No' to the question Are you in A?.

For example, if U = N and A = {odd numbers}, then A′ = {even numbers}.

·         Characteristic of Set