CPSC 121 Lecture Notes - Lecture 37: Mathematical Induction

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

Document Summary

Cpsc 121 lecture #37 induction and models of computation. Topics included: a final proof involving mathematical induction, the beginnings of computation and programming. 2cn + s(floor(3n/4)) works only when n is at least 4. We can get s(4) using the formula 2cn + s(floor(3n/4)) so we don"t need it as a base case: base case tests, s(1) = 4c <= 8c(1) = 8c. Therefore this holds: s(2) = 12c <= 8c(2) = 16c. Therefore this holds: s(3) = 20c <= 8c(3) = 24c. Induction step: we can assume theorem is true for 1, 2, 3 n-1 and then prove n, or we can assume the theorem is true from 1 to n and then prove n+1. 3 n-1 and prove n: consider an arbitrary integer n >= 4. Induction hypothesis: assume s(k) <= 8ck for every k in the range.