CPSC 121 Lecture Notes - Lecture 35: Mathematical Induction

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

Document Summary

Cpsc 121 lecture #34 more on induction. We can prove x z, q(x) q(x+1): for this version, the base case is q(1). Then we"d obtain q(1) q(2), therefore q(2) all the way to q(x-1) q(x), therefore q(x): this is the same as saying q(1) q(2), therefore q(2). Q(3) all the way to q(1) ^ q(2) ^ q(3) ^ q(x-1) q(x) therefore q(x): we prove the term that for an arbitrary x, q(x) is going to work from on the previous values of x. So proving x z, (q(1) ^ q(2) ^ q(x)) q(x+1) also works. If we go from x-4 to x, then we can buy exactly 4 eggs. If you can buy x 4 eggs, you can buy x eggs by buying a pack of 3. Induction , slide 54: base cases: (belleville, lecture 34, since we are asked to start at g(1), we need n=1 as a base case.