CSCI 1112 Lecture Notes - Lecture 3: Greatest Common Divisor, Artery Recordings
Document Summary
Divide it into one or more smaller sub-problems. Recursion and induction: proof by induction. Prove the theorem for the base case(s): n=0, or n=1, or n=c. If the theorem is assumed true for n, then it is also true for n+1. Theorem is true for all n >= c: example. Prove that the sum of the first n odd numbers is equal to n^2. Base case: n = 1, the first odd number is 1 and 1 = 1^2. General case: assume the sum of the first n odd numbers is n^2. Let us prove that if we add the (n+1)-th odd number we get (n+1)^2. Assume one disk can be moved in 1 second. I can do it with n>3 disks and it took me: Twice the number of moves that it takes to move n -2 disks + 1. N = 4, 2*7 +1 = 15 moves. In general it takes 2^n 1 moves.
