TASK FIVE

Number 1

Show that if n is positive integer

P(n) : 1+2+………..+ n = [n (n+1)]/2

Basis step : let n = 1

1 = [1(1+1)]/2

1 = 1 (PROVE)!!!

Inductive step : let n=k; k= k+1

1 + 2 +…+ n = [n (n+1)]/2

1 + 2 +…+ k= [k (k+1)]/2

1 + 2 +…+ k + (k+1) = (k+1) [(k+1)+1]/2

[k(k+1)]/2 + (k+1) = [(k+1) (k+2)]/2

[k(k+1) +2k+2]/2 = [(k+1) (k+2)]/2

[k ² + k + 2k +2]/2 = [k² + 2k + k+ 2]/2

[k² + 3k+ 2] /2 = [k² + 3k + 2]/2 (PROVE)!!!

Number 2

Basis Step

if P(n) is true then can continue to the next step.

Inductive Step

If P then Q

P is the hyphothesis while Q is conclusion

Thus,

If P(n) is true, Then P(n+1) is true/false

Number 3

#Formulas:

Show that if n is a positive integer, then

1 + 2+…..+n =

Solution: Let P(n) be the proposition that the sum of the first n positive integers, 1+2+…+n=n(n+1)/2. We must do two things to prove that P(n) is true for n = 1, 2, 3, . . .

Namely, we must show that P(1) is true and that the conditional statement P(k) implies P(k + 1) is true for k = 1, 2, 3,…..

BASIS STEP: P(1) is true, because 1 =

(The left-hand side of this equation is 1 because 1 is the sum of the first positive integer. The right-hand side is found by substituting 1 for n in n(n + 1)/2.)

INDUCTIVE STEP: For the inductive hypothesis we assume that P(k) holds for an arbitrary positive integer k. That is, we assume that

1 + 2+· · ·+k =

Under this assumption, it must be shown that P(k + 1) is true, namely, that

1 + 2+· · ·+k + (k + 1) ==

is also true. When we add k + 1 to both sides of the equation in P(k), we obtain

1+2+....+k+(k + 1)=+(k+1)

=

=

This last equation shows that P(k + 1) is true under the assumption that P(k) is true. This completes the inductive step.

We have completed the basis step and the inductive step, so by mathematical induction we know that P(n) is true for all positive integers n. That is, we have proven that 1 + 2+· · ·+n =n(n + 1)/2 for all positive integers n.

#Divisibility properties

Proposition: For any integer n≥1, 7ⁿ - 2ⁿ is divisible by 5. (P(n))

Proof :

1) Basis step:

The statement is true for n=1: (P(1))

7¹ – 2¹ = 7 - 2 = 5 is divisible by 5.

2) Inductive step:

Assume the statement is true for some k≥1 (P(k))

(inductive hypothesis) ;

We are given that

P(k): 7^k - 2^k is divisible by 5. (1)

Then 7^k - 2^k = 5a for some aÎZ . (2)

We need to show:

P(k+1):7^k+1 - 2^k+1 is divisible by 5. (3)

7^k+1 - 2^k+1 = 7·7^k - 2·2^k = 5·7^k + 2·7^k - 2·2^k

= 5·7^k + 2·(7^k - 2^k) = 5·7^k + 2·5a (by (2))

= 5·(7^k + 2a) which is divisible by 5.

Show that it is true for k+1. (P(k+1))

Thus, P(n) is true by induction.

#Inequalities

Theorem: For all integers n≥5, n² < 2ⁿ. (P(n))

Proof (by induction):

1) Basis step:

The statement is true for n=5: (P(5))

5² =25 < 32 = 2⁵.

2)Inductive step:

Assume the statement is true for some k≥5 ; (P(k))

We are given that

P(k): k² < 2^k. (1)

We need to show:

P(k+1): (k+1)² < 2^k+1. (2)

(k+1)² = k²+2k+1 < k² +2^k (since k≥5)

< 2^k + 2^k (based on (1))

= 2·2^k = 2^k+1.

Show that it is true for k+1 . (P(k+1))

Thus, P(n) is true by induction.

TASK 4

#Sequences

Definition of sequence

• Ordered list of objects (or events)
• Contains elements or terms

Example : {M,a,r,y} is a sequence of letter ‘M’ first and ‘Y’ last.

• Sequence can be finite or infinite

Types of sequence

1. Arithmetic sequence

• sequence of number with common difference, and the difference must be constant
• example : 2,4,6,8....
• common difference is 2
• so you have arithmetic sequence

2. geometric sequence

• sequence of number where each form in sequence is found by multiplying previous term with unchanging number called common ratio.
• Example: 2,6,18,54.
  
  
  With common ratio 3
  
  
  
  
  Example sequences use in computer programming.
  
  

  • Sequence of the form a_{1 ,} a_{2 ,….. ,}a_n are often use in computer science.
  • This finite sequence are also called strings .
  • The length of a string is the number of terms in the string.
  • The empty string,is the string that has no terms(has length zero).

  
  
  

  Example:

  The string abcd is a string of length four.

  
  
  #Mathematical Induction
  
  
  The Principle of Mathematical Induction
  
  
  • First Principle of Mathematical Induction.
  Let P(n) be a predicate with domain of discourse (over) the natural numbers N = {0,1,2,….}. If :
  
  
  1) P(0), and
  2) P(n) P(n + 1)
  
  
  Then, ∀nP(n)
  
  
  • The Second Principle of Mathematical Induction
  Let k be an integer, and let P(n) be a predicate whose universe of discourse is the set of integers {k,k+1,k+2,….}. Suppose :
  1) P(k), and
  2) P(j) for k ≤ j ≥ n implies P(n + 1).
  
  
  Then, ∀nP(n).
  
  
  In the induction step, the assumption that Pnholds is called the Induction Hypothesis
  (IH). In more formal notation, this proof technique can be stated as
  [P(0)∧∀(P(k)            P(k+1))]                 ∀P(n)
  
  
  Example 1 :
  
  
  E(n) is 1+2+3+4+5+...+ n = (1+n)n/2
  
  
  First step:
  We'll show the truth of E(1). We have to show: 1 = (1+1).1/2
  We see immediately that both sides are equal. So, E(1) is true.
  V contains '1'.
  
  
  Second step:
  Assume for a moment that E (k) is true.
  Given : 1+2+3+4+5+...+k = (1+k)k/2
  We'll show the truth of E(k+1).
  Proof:
  
  
  left side
  = (1+2+3+4+5+...+k)+ (k+1)
  = (1+k).k/2 + (k+1)
  = (k+1)(k+2)/2
  
  
  right side
  = (1+(k+1)).(k+1)/2
  = (2+k)(k+1)/2
  We see that the left side is equal to the right side.
  Thus if E (k) is true then E(k+1) is true.
  If k is in V, then k+1 is in V.
  But 1 is in V, so 2 is in V, so 3 is in V, etc..
  So, V = { 1,2,3,4,....}
  
  
  Conclusion: The property is proved for all natural numbers starting from 1
  
  
  Explain the method of Proof by mathematical Induction
  
  
  In general, mathematical induction can be used to prove statements that assert that P(n) is
  true for all positive integers n, where P(n) is a propositional function. A proof by mathematical induction has two parts, a basis step, where we show that P(1) is true, and an inductive step, where we show that for all positive integers k, if P(k) is true, then P(k+ 1) is true.
  
  
  PRINCIPLE OF MATHEMATICAL INDUCTION To prove that P(n) is true for all
  positive integers n, where P(n) is a propositional function, we complete two steps:
  
  
  BASIS STEP: We verify that P(1) is true.
  
  
  INDUCTIVE STEP: We show that the conditional statement P(k) ¡ú P(k+ 1) is true for
  all positive integers k.
  
  
  To complete the inductive step of a proof using the principle of mathematical induction, we assume that P(k)is true for an arbitrary positive integer k and show that under this assumption, P(k+ 1) must also be true. The assumption that P(k)is true is called the inductive hypothesis. Once we complete both steps in a proof by mathematical induction, we have shown that P(n) is true for all positive integers, that is, we have shown that ∀nP (n) is true where the quantification is over the set of positive integers. In the inductive step, we show that ∀k(P(k) ¡ú P(k+ 1)) is true, where again, the domain is the set of positive integers
  
  
  
  
  Rules of Mathematical Induction
  
  
  Show that the result holds for n = 1
  Step 1:Show that the result is true for n= 1.
  Step 2:Assume the validity of the result for ‘n’ equal to some arbitrary but fixed natural number, say ‘k’.
  Step 3:Show that the result is also true for n= k + 1.
  Step 4:Conclude that the result holds for all natural numbers.
  
  
  
  
  Example 1:
  
  
  Show that if n is a positive integer, then
  
  
  1 + 2+…..+n =
  
  
  Solution: Let P(n) be the proposition that the sum of the first n positive integers, 1+2+…+n=n(n+1)/2. We must do two things to prove that P(n) is true for n = 1, 2, 3, . . .
  Namely, we must show that P(1) is true and that the conditional statement P(k) implies P(k + 1) is true for k = 1, 2, 3,…..
  
  
  BASIS STEP: P(1) is true, because 1 =
  (The left-hand side of this equation is 1 because 1 is the sum of the first positive integer. The right-hand side is found by substituting 1 for n in n(n + 1)/2.)
  
  
  INDUCTIVE STEP: For the inductive hypothesis we assume that P(k) holds for an arbitrary positive integer k. That is, we assume that
  1 + 2+· · ·+k =
  Under this assumption, it must be shown that P(k + 1) is true, namely, that
  1 + 2+· · ·+k + (k + 1) ==
  is also true. When we add k + 1 to both sides of the equation in P(k), we obtain
  
  
  1+2+....+k+(k + 1)=+(k+1)
  =
  =
  
  
  This last equation shows that P(k + 1) is true under the assumption that P(k) is true. This completes the inductive step.
  We have completed the basis step and the inductive step, so by mathematical induction we know that P(n) is true for all positive integers n. That is, we have proven that 1 + 2+· · ·+n =n(n + 1)/2 for all positive integers n.
  
  
  
  
  Example 2:
  
  
  Prove by the principle of mathematical induction method
  4 + 8 + 12 + … + 4n = 2n(n + 1).
  Solution:
  P(n)= 4 + 8 + 12 + … + 4n = 2n(n + 1)
  Put n = 1
  P(1) is true
  Assume that statement be true for n = k
  Assume P(k) true.
  Assume 4 + 8 + 12 + … + 4k = 2k(k + 1) be true
  To prove P(k + 1) is true.
  4 + 8 + 12 + … + 4(k+1) = 2(k+1)(k+1 + 1)= 2(k+1)(k+2)
  P(k + 1) is true.
  If P(k) true, then P(k + 1) is also true.
  P(n) is true for all n ∈ N.
  
  
  

TASK THREE

#Computer representation of Sets

1. Unordered fashion
2. Arbitrary ordery

Example:

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

A = {1, 3, 5, 7, 9} – Odd

A1	A2	A3	A4	A5	A6	A7	A8	A9	A10
1	2	3	4	5	6	7	8	9	10
0	0	0	0	0	0	0	0	0	0
1	0	1	0	1	0	1	0	1	0

A1 is element of A

Then, A1 will have value of 1.

Union (OR)

1 1 1 1 1 0 0 0 0 0

                 1 0 1 0 1 0 1 0 1 0

                 1 1 1 1 1 0 1 0 1 0

So the answer is 1 2 3 4 5 7 9

Intersect (AND)

1 1 1 1 1 0 0 0 0 0

                  1 0 1 0 1 0 1 0 1 0

                        1 0 1 0 1 0 0 0 0 0

So the answer is 1 3 5

#Relation

Relation

If we want to describe a relationship between elements of two sets A and B, we can use ordered pairs with their first element taken from A and their second element taken from B.

Since this is a relation between two sets, it is called a binary relation.

Definition: Let A and B be sets. A binary relation from A to B is a subset of A´B.

In other words, for a binary relation R we have R Í A´B.

We use the notation aRb to denote that (a, b)ÎR and aRb to denote that (a, b)ÏR.

When (a, b) belongs to R, a is said to be related to b by R.

Example: Let P be a set of people, C be a set of cars, and D be the relation describing which person drives which car(s).

P = {Carl, Suzanne, Peter, Carla}

C = {Mercedes, BMW, tricycle}

D = {(Carl, Mercedes), (Suzanne, Mercedes), (Suzanne, BMW), (Peter, tricycle)}

This means that Carl drives a Mercedes, Suzanne drives a Mercedes and a BMW, Peter drives a tricycle, and Carla does not drive any of these vehicles.

Functions as Relations

You might remember that a function f from a set A to a set B assigns a unique element of B to each element of A.

The graph of f is the set of ordered pairs (a, b) such that b = f(a).

Since the graph of f is a subset of A´B, it is a relation from A to B.

Moreover, for each element of A, there is exactly one ordered pair in the graph that has a as its first element.

Conversely, if R is a relation from A to B such that every element in A is the first element of exactly one ordered pair of R, then a function can be defined with R as its graph.

This is done by assigning to an element aÎA the unique element bÎB such that (a, b)ÎR.

Relations on a Set

Definition: A relation on the set A is a relation from A to A.

In other words, a relation on the set A is a subset of A´A.

Example: Let A = {1, 2, 3, 4}. Which ordered pairs are in the relation R = {(a, b) | a < b} ?

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

Properties of Relation

(1)Reflexive

A relation R on a set A is called reflexive if (a, a)ÎR for every element aÎA.

Example:

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

Answer: R is reflexive because they both contain all pairs of the form (a, a),namely, (1, 1), (2, 2), (3, 3), and (4, 4).

(2)Irreflexive

A relation on a set A is called irreflexive if (a, a)ÏR for every element aÎA.

Example:

These 4 irreflexive relations are :

1. Empty

2. {(1,2)}

3. {(2,1)}

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

(3)Symmetric

A relation R on a set A is called symmetric if (b, a)ÎR whenever (a, b)ÎR for all a, bÎA.

Example:

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

Answer: R is symmetric.Both (2, 1) and (1, 2) are in the relation so R is symmetric.

(4) Antisymmetric

A relation R on a set A is called antisymmetric if a = b whenever (a, b)ÎR and (b, a)ÎR.

Example:

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

Answer:R is antisymmetric.There is no pair of elements a and b with a ≠ b such that both (a, b) and (b, a) belong to the relation.

(5)Transitive

A relation R on a set A is called transitive if whenever (a, b)ÎR and (b, c)ÎR, then (a, c)ÎR for a, b, cÎA.

Example: Are the following relations on {1, 2, 3, 4} transitive?

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

#Functions

Boolean Function

A Boolean function describes how to determine a Boolean value output based on some logical calculation from Boolean inputs.Boolean functions are often represented by sentences in propositional logic.

A function consists of:

• a domain (the set being mapped from),
• a codomain (the set being mapped to),
• a mapping from the domain to the codomain.

Usually, for each element in the domain, the mapping assigns one element of the codomain. If this happens, the function is said to be total.

Sometimes, there are some elements in a domain that are not assigned at all. Thus, the mapping for these elements are unknown. Such functions are said to be partial because not every element in the domain is mapped.

For finite domains and codomains, we can draw pictures.

Types of function :

         1) injective function(one-to-one)

• If and only if f(x)=f(y) implies x=y for all x,y in the domain of f.
  
  
  2) Surjective function (onto)

• If and only if for every bB there is an element aA such that f(a)=b
• Alternative way to understand: all codomains elements are covered

         3) Bijective (both one-to-one[injection] and onto[surjection])

Inverse function:

Let f be a bijection from set A to set B. The inverse function of f is the function that assigns to an element b from B the unique element a in A such that f(a)=b. The inverse function of f is denoted by f-1 (f inverse). Hence, f-1 (b)=a, when f(a)=b . If inverse function of f exists, f is called invertible.

SLIDE FOR THIS TASK
http://www.scribd.com/doc/131035898/3