CSCB36H3 Lecture Notes - Structural Induction, Horse Length

216 views5 pages
1 Nov 2012
School
Course
Professor

Document Summary

P(n): n = k * 4 + l * 7 for some k, l n. Prove p(n) holds for all n 18. For n = 18, let k = 1, l = 2, then 4k + 7l = 18. For n = 19, let k = 3, l = 1, , = 19. For n = 20, let k = 5 l = 0, , = 20. Suppose p(g) holds whenever 18 g < n [ih] Since n 22, 18 n - 4 < n. By i. h p(n-4) holds i. e n - 4 = 4k + 7l for some k, l n. Let k" = k + 1, l" = l. Then k", l" n, and 4k" + 7l" = 4(k+1) +7l. Chapter 3: use of induction to define functions: 0 if n = 0 f(n) = { 1 if n - 1 f(n -1) + f(n-2) , if n > 1.

Get access

Grade+
$40 USD/m
Billed monthly
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
10 Verified Answers
Class+
$30 USD/m
Billed monthly
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
7 Verified Answers

Related Documents

Related Questions