CS 201 - 9/25/14 Late Policy for Programming Projects 1 day 10% penalty 2 days 20% penalty 3 days 40% penalty 4 days 80% penalty 5 days 100+% penalty Inductive Proofs. Sum of i*(i+1) from i=1 to n-1 is n(n-1)(n+1) /3 for all n >= 2 Base Case: n = 2 Left Side Expression Sum of i*(i+1) from 1 to 1 1*(1+1) 1 * 2 2 Right Side Expression n(n-1)(n+1) / 3 replace 2 for n 2*(2-1)*(2+1) /3 (2* 1 * 3 ) / 3 6 / 3 2 Since LHS equal RHS for Base Case, Base Case is proven Inductive Case Assume true for M, Prove True for M+1 Show Sum of i*(i+1) from i=1 to n-1 is n(n-1)(n+1) /3 for all n = M+1 Left Hand Side Sum of i*(i+1) from i=1 to M+1-1 Right hand Side M+1(M+1-1)(M+1+1) /3 Work the LHS so it equals the RHS Sum of i*(i+1) from i=1 to M+1-1 Express this in terms of M and M+1 First expand into series form [1*(1+1) + 2*(2+1) + 3*(3+1) + ... + (M-1)*(M-1+1)] + (M)*(M+1) Then compress part of the series to express in terms of M [Sum of i*(i+1) from i=1 to M-1] + (M)*(M+1) Apply the inductive Statement on the M portion [M(M-1)(M+1) /3] + (M)*(M+1) (M^2-M)(M+1) / 3 + (M)(M+1) (M^3 + M^2 - M^2 - M)/3 + M^2 + M M^3/3 - M/3 + 3M^2/3 + 3M/3 (M^3 - M + 3M^2 + 3M) / 3 (M^3 + 3M^2 + 2M) / 3 M (M^2 + 3M + 2) / 3 M (M + 1)(M + 2) /3 (M + 1 )(M)(M + 2) /3 (M+1)(M+1-1)(M+1+1) /3 The above equal the Right hand Side of M+1(M+1-1)(M+1+1) /3 Since the LHS equals the RHS, we have proved the inductive case By proving both the Base Case and the Inductive Case and appling the Principle of Mathematical Induction we have proved the original claim. Strong Inductive Proofs have either(or both) multiple base cases or inductive steps not relying on the immediate previous value Consider the following sequence C0 = 2 C1 = 2 C2 = 6 CK = 3 * C(k-3) FOR ALL INT k >= 3 2 2 6 6 6 18 18 18 54 54 54 .... Prove that CN is even for all n > 1 We have 3 Base Case n = 2, 3, 4 C2 = 6 C3 = 6 C4 = 6 An integer is even if that integer can be expressed as 2k where K is also and integer The value of 6 can be expressed as 2*3. Since 3 is an integer, 6 is even. Induction Case Show that Ck is even when k > 4 show that Ck can be express as 2 * I where I is some integer