CISC 121 Lecture : 6.1.pdf

• School: Queen's University
• Department: Computing
• Course: CISC 121
• Professor: Robin W Dawes

Document Summary

Suppose we want to prove something is true about all the objects in a set. Statement: every citrus fruit has a certain amount of vitamin c in the juice. You can prove this by evaluating every fruit and showing that it is true for each. If the set is infinite however, you can"t do that. Proof by induction is useful for proving statements about all members of infinite sets. Prove the statement is true for the first member of the set. Prove that if it is true for some member, it is also true for the next member of the set. Statement: e(n) = 1 + 2 + 3 + 4 + n = (n(n+1))/2. Assume e(n) is true for some n in set. 1+2+ . n+n+1 = (n+1)(n+1+1)/2 n(n+1)/2 + (n+1) = (n+1)(n+1+1)/2. We do not use concrete time to measure the time it takes a program to run, due to software differences and other programs running, etc.