CS 201 - 9/30/14 Why are we studying Inductive proofs? What is the big picture?? Most Programs require an inductive proof to be shown to be correct. Most programs require an inductive proof to prove/show/determine run time of the program. Formal proofs of the above type are not part of CS 201 ================================== From Last Time Given the sequence b b[1] = 4 b[2] = 12 b[k] = b[k-2] + b[k-1] for all integers k >= 3 Prove that b[N] is divisible by 4 for all integers N >= 1 A number that is divisible by 4 can be expressed as 4 * I for some integer value I Base Cases: n = 1, n = 2 b[1] = 4 (by definition of the sequence, i.e it was given) = 4 * 1 since 1 is an integer, b[1] is divisibly by 4 b[2] = 12 (given by def. of the sequence) = 4 * 3 since 3 is an integer, b[2] is divisible by 4 Inductive Case: Inductive Hypothesis: Show the for all integers k >= 3 if the property is true ( b[k] is divisible by 4 ) for all i with 1 <= i < k, then the property is true for all k. "Assume true for p < k, Prove true for k." Write out the equation for k b[k] = b[k-2] + b[k-1] Show b[k] is divisible by 4, we can use that b[l] is known to be divisible by for all 1 <= l < k b[k] = 4 * X + 4 * Y (substitute for b[k-2] and b[k-1]) where X and Y are some integer values = 4 * (X + Y) by distributive law = 4 * Z , where Z is some integer since Integer + Integer equals another integer By being able to express b[k] in terms of 4 times some integer, we prove the b[k] is divisible by 4. Thus, Proving the inductive case. By the property of String mathematical Induction we have proved that all values in the sequence are divisible by 4. When dealing C pointers, invalid address references is a HUGE issue and can be extremely time consuming. node* head; Head is storing an address head->elem = 5; The above statement causes a "run-time violation" if the address in head is not 100% correct. Understanding a few simple debugging tips can greatly help reduce development time. One debugging tool is called gdb