COMP 250 Lecture Notes - Lecture 9: Insertion Sort, Lecture Recording, Mathematical Induction
2 Dec 2016
School
Department
Course
Professor
Document Summary
Mathematical induction : a particular kind of proof technique. It"s not obvious when we look at it that it is a true statement. A proof is a very very convincing argument. + 1 + n = n(n (n. There are n pairs, and they each sum to n+1. Dividing by 2 gives the result n * ( + 1 n. It"s more subtle than above, and more general. With mathematical induction, there"s a certain statement we are trying to prove: Making a statement about all positive numbers greater than some constant. We want to make some statement which depends on n . P() is for predicate -- it can be true or false. For every n, it is either true or false. For any k>= n0, if p(k) is true , then p(k+1) is also true . Don"t prove p(k) is true -- prove that if it is true, then p(k+1) is true.
