DOC PREVIEW
GSU CSC 2510 - ch02s2

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Proofs, Recursion and Analysis of AlgorithmsPrinciples of mathematical inductionExample: First Principle of InductionSlide 4Example: Second Principle of InductionProofs, Recursion and Analysis of AlgorithmsMathematical Structures for Computer ScienceChapter 2Copyright © 2006 W.H. Freeman & Co. MSCS Slides Proofs, Recursion and Analysis of AlgorithmsSection 2.2 Induction 2Principles of mathematical inductionFirst Principle: P(1) is true (k)P(k) true  P(k+1) true Second Principle: P(1) is true P(r) true for all r, 1rk  P(k+1) trueMajor difference is in the second statement. Use the second principle when assuming P(k) is not enough to prove P(k+1).Assuming P(r) for any r where 1 r  k gives more ammunition to prove the relation. Use second principle when the case k+1 depends on results further back than k.P(n) is true for all positive integers nP(n) is true for all positive integers nSection 2.2 Induction 3Example: First Principle of InductionProve that 1+2+22…+2n = 2n+1-1 for any n  1.P(1) is the equation 1+2 = 21+1+1 or 3 = 22+1, which is true. We take P(k) = 1+2+22…+2k = 2k+1-1 as the inductive hypothesis and try to establish P(k+1): 1+2+22…+2k+1 = 2k+1+1-1 Again, rewriting the sum on the left side of P(k+1) reveals how the inductive assumption can be used: 1+2+22…+2k+1 = 1+2+22…+ 2k + 2k+1= 2k+1-1 + 2k+1= 2(2k+1)-1 = 2k+1+1-1 Therefore, 1+2+22…+2k+1 = 2k+1+1-1 and verifies P(k+1) and completes the proof.?Section 2.2 Induction 4Example: First Principle of InductionProve that for any positive integer n, the number 22n-1 is divisible by 3. The basis step is to show P(1), that 22(1)-1 = 4-1 = 3 is divisible by 3. Clearly this is true. We assume that 22k+1 is divisible by 3,which means that 22k+1 = 3m for some integer m, or 22k = 3m+1. We want to show that 22(k+1) -1 is divisible by 3. 22(k+1) -1 = 22k+2 -1 = 22•22k-1 = 22(3m+1) -1 (by the inductive hypothesis) = 12m+4 -1 = 12m+3 = 3(4m+1) where 4m+1 is an integer Thus 22(k+1) -1 is divisible by 3.Section 2.2 Induction 5Example: Second Principle of InductionProve that the amount of postage greater than or equal to 8 cents can be built using only 3-cent and 5-cent stamps. Proof using the second principle of InductionHence, we have to prove that P(n) is true for n  8 where P(n) is the sum of 3 and 5 cent stamps used to make the n cents worth of postage. Base case: P(8) = 3 + 5 = 8 which is true.In this case we will have to establish additional cases to prove this. Hence, establish two cases P(9) and P(10) P(9) = 3 + 3 + 3 = 9 and P(10) = 5 + 5 Assume P(r) is true for any r, 8  r  k and consider P(k+1) We have proved P(r) is true for r = 8,9,10 So, lets assume k+1 is 11 If k+1  11 then (k+1)-3= k-2  8, hence, by inductive hypothesis, P(k-2) is true. Hence, k-2 can be written as a sum of 3s and 5s. Adding an additional 3 results in k+1 as a sum of 3s and 5s. This verifies P(k+1) is true and hence verifies the


View Full Document

GSU CSC 2510 - ch02s2

Documents in this Course
ch04s2

ch04s2

8 pages

ch01s6

ch01s6

10 pages

ch01s1

ch01s1

21 pages

ch02s4

ch02s4

10 pages

ch08s2

ch08s2

21 pages

ch08s3

ch08s3

15 pages

ch07s3

ch07s3

21 pages

ch04s3

ch04s3

23 pages

ch06s3

ch06s3

16 pages

ch01s3

ch01s3

15 pages

ch03s4

ch03s4

11 pages

ch03s6

ch03s6

6 pages

ch03s5

ch03s5

9 pages

ch06s2

ch06s2

9 pages

ch03s1

ch03s1

19 pages

ch07s1

ch07s1

11 pages

ch02s1

ch02s1

14 pages

ch08s1

ch08s1

15 pages

ch02s5

ch02s5

9 pages

ch01s4

ch01s4

13 pages

Load more
Download ch02s2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view ch02s2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view ch02s2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?