Chap 3: Mathematical Induction (II)

STRONG MATHEMATICAL INDUCTION:

Almost similar to ordinary mathematical induction, however in strong mathematical induction, the basis step may contain proofs for several initial values, and in inductive step the truth of the predicate P(n) is assumed and not just for one value of n but for all from a through k and then the truth of P(k+1) is proved.

Principle of Strong Mathematical Induction:

Let P(n) be a property that is defined for integer n, and let a and b be fixed integer with a≤b.

Suppose the following 2 statements are true:

①    P(a), P(a+1), … and P(b) are all tue (BASIS)

②    For any integer k≥b, if P(i) is true for all int I from a through k, then P(k+1) is true. (INDUCTIVE STEP)

Then, the statement “for all integer n≥a, P(n) is true.”

(The supposition that P(i) is true for all integer i from a through k is called the inductive hypothesis.)

(Another way to state the inductive hypothesis is to say that P(a), P(a+1),…, P(k) are all true)

Note: Any statement that can be proved by ordinary mathematical induction can be proved by strong induction too.

Chap 3: Mathematical Induction (I)

PRINCIPLE OF MATHEMATICAL INDUCTION:

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

Basis      : We verify that P(1) is true @ show that an initial value is true for all Z⁺ of the propositional function.

Inductive  : We show that the conditional statement∀k (P(k) → P(k+1)) is true for all Z⁺ of k.

Similarly, we can say that mathematical induction is a method for proving a property defined that the property for integer n is true for all values of n that are greater than or equal to some initial interger.

                   P(1)^∀k(P(k) → P(k+1))) → ∀nP(n)

METHOD OF PROOF:

The proofs of the basis and inductive steps shown in the example illustrate 2 different ways to show an equation is true

p Transforming LHS and RHS independently until they seem to be equal.

p Transforming one side of equation until it is seen to be the same as the other side of the equation.

Chapter 3: Sequences and Mathematical Induction (I)

Presentation week. All notes are available in slides. You can download this slide at this link:
Chapter 3: Sequences and Mathematical Induction (I)

Chap 2: Set Theory (Part 6)

FUNCTIONS:

• A function f from a set X to a set Y is a relation from X to Y such that x Î X is related to one and only one y Î Y
• X is called the domain & Y is called the range. We say x is mapped into y.
• f = {(a, 3), (b, 3), (c, 5), (d, 1)}
• Functions are described as:
• Set of ordered pairs, example f as given before
• Using a formula such as f(x) = expression, example : f (x) = 2x + 2
• Illustration as in the example below

Chap 2: Set Theory (Part 5)

Relation between 2 sets:

™ A relation between two sets A and B is a subset of the Cartesian product AxB; A is called the source set and B is called the target set.

™ Often, we use notation aRb to denote that (a.b)єR and a~Rb to denote that (a,b)∉  ..

EXAMPLE:

Let U={0,1,2,3,4,5,6} represent set with bit strings

a) A= {2,4,5,6}

      bit string is 0010111

 b) B is the set of all odd integer, B Í U.

      B= {1,3,5} the bit string is 0101010

 c) C is a subset of U, containing all integers greater than 4.

      C={5,6} the bit string is 0000011

Chap 2: Set Theory (Part 4)

COMPUTER REPRESENTATION OF SETS:
 There are many ways to represent sets using a computer.
 One of the method is to store elements using an arbitrary ordering of elements of the universal set.
◦ Ordered set (less time-consuming)
◦ Unordered set (time consuming)
 An arbitrary ordering of the elements of U (universal set), for instance, a1, a2, …, an, then representing a subset of A of U with bit string of length n, where the ith bit in this string is 1 if a1 belongs to A and is 0 if a does not belong to A.

EXAMPLE:
Let U={0,1,2,3,4,5,6} represent set with bit strings (binary form)
a) A= {2,4,5,6}
      bit string is 0010111
 b) B is the set of all odd integer, BÍ U.
      B= {1,3,5} the bit string is 0101010
 c) C is a subset of U, containing all integers greater than 4.
      C={5,6} the bit string is 0000011