CS 201 - 9/29/14 Inductive Proofs Weak Inductive Proof Wording of Inductive Hypothosis: Assume the statement is true for a value of N, Prove for a value of N+1 Wording for Strong Inductive Proof (Epp Text): "Show that for all integers k>S if the property is true for all i with S <= i < k, then prove it is true for k." "Assume true for p < M, Prove true for M" ========================= Given the sequence, c: c[0] = 2 c[1] = 2 c[2] = 6 c[k] = 3 * c[k-3] for all integers k>=3 Prove c[n] is even for all integers n >= 0 Even integers can be represented as 2 * I for some integer I If an integer X that can be expressed as 2 * Y for some integer Y, then X is even. Base Cases: n = 0, n = 1, n = 2 c[0] = 2 = 2 * 1, since 1 is an integer C[0] is even c[1] = 2 = 2 * 1, since 1 is an integer C[1] is even c[2] = 6 = 2 * 3, since 3 is an integer C[2] is even Inductive Hypothosis: Assume true for all p < M, Prove true for M where p >= 0 and where M >= 3 C[M] = 3 * C[M-3] By applying then IH (Inductive Hypothesis), we can replace C[M-3] in the above expression This tells us the C[M-3] is even which can be express as 2 * I for some integer I C[M] = 3 * 2 * I C[m] = 2 * 3 * I by Communative Prop of * C[M] = 2 * J by the laws of Mulp on Integers J is an Integer Since C[M] is expressed a 2 * some Integer, c[M] is even. ==================================== 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 even