# discrete structures chapter 2 part b mathematical induction

Post on 03-Jan-2016

28 views

Embed Size (px)

DESCRIPTION

Discrete Structures Chapter 2 Part B Mathematical Induction. Nurul Amelina Nasharuddin Multimedia Department. Mathematical Induction. Use to verify a property of a sequence Used to check the conclusions about the outcomes of processes that occur repeatedly and according to definite patterns. - PowerPoint PPT PresentationTRANSCRIPT

Discrete StructuresChapter 2 Part BMathematical InductionNurul Amelina NasharuddinMultimedia Department

Mathematical InductionUse to verify a property of a sequenceUsed to check the conclusions about the outcomes of processes that occur repeatedly and according to definite patterns*

Eg: Any whole number of cents of at least 8 cents can be obtained using 3 cents and 5 cents coinsFormally: For all integers n 8, P(n) is true where P(n) = n cents can be obtained using 3 cents and 5 cents coins(1) If k cents is obtained using at least one 5 cents coin, then replace the coin with two 3 cents coins = (k+1) cents(2) If k cents is obtained without using a 5 cents coin, then replace at least three 3 cents coins with two 5 cents coins = (k+1) centsTo show that P(n) is true for all integers n 8,(1) show P(8) is true(2) show that the truth of P(k+1) follows necessarily from the truth of P(k) for each k 8

Mathematical Induction*

Principle of Mathematical InductionLet P(n) be a predicate that is defined for integers n and let a be some integer. If the following two premises are true:P(a) is a truek a, P(k) P(k + 1)then the following conclusion is true as wellP(n) is true for all n a*

Method of Proof by Mathematical InductionConsider a statement of the form, For all integers n a, a property P(n) is trueTo prove such statement, perform these 2 steps:Step 1 (basis step): Show that when n = a, statement is trueStep 2 (inductive step): Show that for all integers k a, if the property is true for n = k then it is true for n = k+1. To perform this step,Suppose that the property is true for n = k, where k a [This supposition is called the induction hypothesis]ThenShow that the property is true for n = k+1*

Coins ProofingP(n): n cents can be obtained using 3c and 5c coins. P(n) is true for all integers n 8.Proof:Step 1: The property is true for n = 8 because 8c = 3c + 5c.Step 2: Suppose kc can be obtained using 3c and 5c for some integer k 8. [Induction hypothesis]. We must show that (k+1)c can be obtained using 3c and 5c.(1) In case there is a 5c coin among the kc, replace it by two 3c coins = (k+1) cents(2) In case there is no 5c coin, replace three 3c coins by two 5c coins = (k+1) centsThus in either case (k+1)c can be obtained using 3c and 5c coins (PROVED!!)

*

Applications of Mathematical InductionShow that 1 + 2 + + n = (n * (n + 1)) / 2Sum of geometric series: r0 + r1 + + rn = (rn+1 1) / (r 1)*

Sum of the First n IntegersShow that 1 + 2 + + n = (n * (n + 1)) / 2 for all integers n 1

P(n): 1 + 2 + + n = (n * (n + 1)) / 2Step 1: Show that the property is true for n=1(LHS) 1 = (1 * (1 + 1)) /2 = 1 (RHS)The property true for n=1

Step 2 : Show that for all integers k 1, if the property is true for n = k then it is true for n = k+1Suppose 1 + 2 + + k = (k * (k + 1)) / 2, for some integer k 1 (induction hypothesis)*

Sum of the First n Integers (2)We must show that 1 + 2 + + (k+1) = (k+1)((k + 1)+1) /2, or equivalently that 1 + 2 + + (k+1) = (k+1)(k + 2) /2(show that LHS equals the RHS)1 + 2 + + (k+1)= 1 + 2 + + k +(k+1)= (k * (k + 1)) / 2 + (k+1) (by substitution from the inductive hypothesis)= (k * (k + 1)) / 2 + 2(k + 1) / 2= [(k+1)(k+2)] / 2LHS = RHSConsequently, by the Principle of Mathematical Induction, P(n) is true for all n 1*

Sum of a Geometric SequenceFor any real number r except 1, and any integer n 0,

P(n):

Step 1: Show that the property is true for n=0:

(LHS)(RHS)

The property true for n=0*

Sum of a Geometric Sequence (2)Step 2 : Show that for all integers k 0, if the property is true for n = k then it is true for n = k+1Suppose , for k 0 (induction hypothesis)

We must show that the property is true for (show that LHS equals the RHS)

*LHS = RHSConsequently, the theorem is true

Proving the Divisibility PropertyFor all integers n 1, 22n 1 is divisible by 3

P(n): 22n 1 is divisible by 3Step 1: Show that the property is true for n=122(1) 1 = 22 1 = 3 is divisible by 3 The property true for n=1

Step 2 : Show that for all integers k 1, if the property is true for n = k then it is true for n = k+1Suppose 22k 1 is divisible by 3, for some integer k 1 (induction hypothesis)

*

Proving the Divisibility Property (2)By definition of divisibility, this means that 22k 1 = 3r, for some integer r. We must show that the 22(k+1) 1 is divisible by 3.

22(k+1) 1= 22k+2 1 = 22k . 22 1= 22k . 4 1= 22k . (3 + 1) 1= 22k . 3 + 22k 1= 22k . 3 + 3r = 3(22k + r)

22k + r is an integer because it is a sum of products of integers. Consequently, the theorem is true

*

Proving an InequalityFor all integers n 3, 2n + 1 2n

P(n): 2n + 1 2nStep 1: Show that the property is true for n=3 2n + 1 = 2(3) + 1 = 7 2n = 23 = 8 The property true for n=3

Step 2 : Show that for all integers k 3, if the property is true for n = k then it is true for n = k+1Suppose 2k + 1 2k, for some integer k 3 (induction hypothesis)

*

Proving an Inequality (2)We must show that 2(k+1) + 1 2(k+1) or equivalently, 2k+3 2k+1

2k+3 = (2k+1) +2 2k + 22k+3 = (2k+1) +2 2k + 2k 2 2k for all integers k2k + 3 2(2k) = 2k+1

Consequently, the 2n + 1 2n for all integers n 3

*

Proving a Property of A SequenceDefine a sequence a1, a2, a3, , as followsa1 = 2ak = 5ak-1 Write the first four sequence a1 = 2 a2 = 5a1 = 5.2 = 10 a3 = 5a2 = 5.10 = 50 a4 = 5a3 = 5.50 = 250

Proof an = 2 . 5n-1 for all integers n 1Step 1: Show that the property is true for n=1 2 . 51-1 = 2 . 1 = 2 = a1The property true for n=1

*

Proving a Property of A Sequence (2)Step 2 : Show that for all integers k 1, if the property is true for n = k then it is true for n = k+1Suppose ak = 2 . 5k-1 for all integers k 1(induction hypothesis)We must show that ak+1 = 2 . 5(k+1)-1 = 2 . 5k

ak+1= 5a(k+1)-1 = 5ak= 5 . (2 . 5k-1)= 2 . (5 . 5k-1)= 2 . 5k

Consequently, the an = 2 . 5n-1 for all integers n 1

*

ExercisesShow that 22n 1 is divisible by 3Show that for n > 2: 2n + 1 < 2nShow that xn yn is divisible by x yShow that n3 n is divisible by 6 On the outside rim of a circular disk the integers from 1 to 30 are painted in random. Show that there must be three successive integers whose sum is at least 45*

Principle of Strong Mathematical InductionBasis step may contains proofs for several initial valuesIn inductive step the truth of the predicate P(n) is assumed for all values through k-1, then the truth of P(k) is proved.

Let P(n) be a predicate that is defined for integers n and let a and b be fixed integers with a b. Suppose the following two premises are true:P(a), P(a+1), P(a+2), , and P(b) are true (basis step)For any integer k b, if P(i) is true for all integers i with a i k, then P(k) is true (inductive step)then the following conclusion is true as wellP(n) is true for all n a

*

Applying Strong Mathematical InductionProve that any integer greater than 1 is divisible by a prime number

P(n): n is divisible by a prime number where n 2Step 1: Show that the property is true for n=2The property is true for n=2 because 2 is a prime number and 2 is divisible by 2

Step 2: Show that for all integers k 2, if the property true for all i with 2 i k, then it is true for kFor all integers i with 2 i k, i is divisible by a prime number. (induction hypothesis)

*

Applying Strong Mathematical Induction (2)Either k is a prime or not.If k is a prime, k is divisible by a prime number, namely itself.If k is not a prime, then k = ab, where a and b are integers with 2 a k and 2 b k.By inductive hypothesis, a is divisible by a prime number p, and so by transitivity of divisibility (pg151), k is also divisible by p. Hence regardless of whether k is a prime or not, k is divisible by a prime number

*

Divisibility (pg 148)Integer n is divisible by an integer d, when k Z, n = d * k, for some integer kNotation: d | nSynonymous statements:n is a multiple of dd is a factor of nd is a divisor of nd divides nEg: If a and b are integers, is 3a + 3b divisible by 3?Yes. By distributive law, 3a + 3b = 3(a+b) and a+b is an integer because it is a sum of 2 integers*

Divisibility (pg 148)Divisibility is transitive: for all integers a, b, c, if a divides b and b divides c, then a divides cWe need to show a | c or in other words c = a*k (k is some integer) a | b or b = a*r; and b | c or c = b*s (r and s are some integers)

c= b*s=(a*r)*s=a(rs)

Let k = rs, therefore a divides c by definition of divisibility*

ExercisesProve or provide counterexample:For integers a, b, c: (a | b) (a | bc)For integers a, b, c: (a | (b + c)) (a | b a | c)If 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * m = 151 * 150 * 149 * 148 * 147 * 146 * 145 * 144 * 143, does 151 | m?Show that an integer is divisible by 9 iff the sum of its digits is divisible by 9. Prove the same for divisibility by 3.Show that an integer is divisible by 11 iff the alternate sum of its digits is divisible by 11

Fundamental Theorem of Arithmetic (pg 153)Given any integer n 1, the standard factored form of n, is an expression of the form

where k is a positive integer; p1, p2, , pk are prime numbers; e1, e2, , ek are positive integers; and p1 p2 pk Eg: Write 3300 in standard factored form3300= 2(1650)=22(825)=2231(275)= 223152(11) = 223152111

*

Fundamental Theorem of Arithmetic (pg 153)Number of positive divisors of n are(e1 + 1)(e2 + 1)(ek + 1)

Eg: 29, 338, 848,000 = 28 35 53 73 11. 29,338,848,000 has (8 + 1)(5 + 1)(3