CS 201 - 10/6/14 Thursday 10/9/14 Quiz on inductive proof(s) - solve an simple inductive proof (maybe solve two) - question or two on when a strong inductive proof might be needed. - when more than 1 base case is needed we must do a strong inductive proof - when the inductive case only relies on the previous value in the sequeunce (given M is true, prove M+1), we can use the simple inductive proof. Otherwise, we must use the strong inductive proof. Prove the following using Strong Mathematical Induction: Suppose that a sequence is defined as: g[0] = 12 g[1] = 29 g[k] = 5*g[k-1] - 6*g[k-2] for all integers k>=2 Prove that g[n] = 5*(3^n) + 7*(2^n) for all integers n>= 0 First part prove the 2 base cases (when n = 0, n = 1): Base Case: n = 1 g[0] = 5*3^n + 7*2^n = 5*3^0 + 7*2^0 .... finish rest for base cases on your own Inductive Case: Inductive Hypothesis: { Assume true for values of n >= 0 and n < k, Show true for k. } Show that g[k] = 5*3^k + 7*2^k By the sequence definition 5*g[k-1] - 6*g[k-2] = 5*3^k + 7*2^k Apply the Inductive Hypothesis 5*(5*3^(k-1) + 7*2^(k-1)) - 6(5*3^(k-2) + 7*2^(k-2)) = ... work the equation until we get .... 5*3^k + 7*2^k =