Class Notes (835,007)
CSCB36H3 (2)
Lecture

# Day 2

5 Pages
129 Views

Department
Computer Science
Course
CSCB36H3
Professor
Nick Cheng
Semester
Fall

Description
Stamps Revisited: P(n): n = K * 4 + L * 7 for some K, L ϵ N 18, 22, 26, 30, 19, 23, 27, 31, 20, 24, 28, 32, 21, 25, 29, 33, Prove P(n) holds for all n ≥ 18 Base Case: 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 Induction Step: Let n ≥ 22 Suppose P(g) holds whenever 18 ≤ g < n [IH] WTP: P(n) 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 = 4K + 7L + 4 = (n-4) + 4 = n Chapter 3: Use of Induction to define functions: 0 if n = 0 f(n) = { 1 if n - 1 Fibonacci f(n -1) + f(n-2) , if n > 1 f(n) = ∅ - ∅’ / sqrt(5), when ∅ = (1 + sqrt(5))/ 2, ∅’ = (1 - sqrt(5))/2 Section 3.3: Pretend Induction. f(n) = { n if n 2; 2 f([n/2]) + [] if n > 2 it can be shown / P(n) Ind. Step: Let n > 2
More Less

Related notes for CSCB36H3
Me

OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.