CPSC 121 Lecture Notes - Lecture 33: Mathematical Induction, Natural Number

• School: UBC
• Department: Computer Science
• Course: CPSC 121
• Professor: BELLEVILLE, PATRICE

Document Summary

Cpsc 121 lecture #32 mathematical induction practice. Induction intro (part 2: mathematical induction doesn"t come up with the formula; you have to find that separately and then use induction on the formula that was created separately, ex. 1: the following is from belleville, lecture 32 mathematical induction , slide 34. For every value of a 0, 1. = [(at+1 1) / (a-1)] + [(at+1)(a-1) / (a-1)] = [(at+1 1 + (at+1)(a-1)) / (a-1)] = [(at+1 1 + at+2 - at+1) / (a-1): (expanded (at+1)(a-1)) = [(at+2 + 1) / (a-1): ex. Slide 34: base case: 24 < 4! (belleville, lecture 32 mathematical induction , Is true because 2 2 2 2 = 16, which is bigger than 1 2 3 4 = 16: the base case has n = 4 because that"s the smallest natural number that works for the formula 2n < n! Induction step: consider an arbitrary n. assume 2n < n!.