CS 201 - 9/11/14 inductive proof Sum i from 1 to n = n (n+1) / 2 Proved Base Case Last Time: Now we need to solve the inductive case: Assume the formula is true for M Show the formula is true for M+1 Sum of i from 1 to M+1 = (M+1) * ((M+1) + 1) / 2 1 + 2 + 3 + ... + M-1 + M + M+1 = (1 + 2 + 3 + ... + M-1 + M) + M+1 = (Sum of i from 1 to M) + M+1 = Now we apply the Inductive Hypothosis (M * (M + 1) / 2) + M+1 = (M^2 + M) / 2 + M+1 = M^2/2 + M/2 + 2M/2 + 2/2 = (M^2 + 3M + 2) / 2 = (M + 1)(M + 2) / 2 = (M+1) * ((M+1) + 1) / 2 = Since the LHS equals the RHS the inductive case has been proven. By combine the base case and the inductive case, using the Principles of Mathematical Induction we have shown that Sum of i from 1 to n = n * (n+1) / 2 is true for all values of i greater than or equal to 1 When solving an Inductive Proof, Step 1. Understand the general formula being proved Step 2. Understand and solve the base case Step 3. The Inductive Case 3a. State the Inductive Hypothesis "Assume true for M" "Show True for M+1" Use a different variable for the terms than used in the original formula 3b. State the formula for the Value M+1 3c. Manipulate one side of the formula from 3b the express a sub-portion of the that side in terms of M and some other stuff. 3d. Apply the Inductive Hypothesis on the portion of the side contain M 3e. Reduce/Maniplution the side of the formula so that it (hopefully) match the other side 4. Insert verbiage of "The principle of Mathematical Induction" to finalize the proof. The above idea is called Simple Induction - where the step N relies on step N-1 - there is only one base case Complete Induction is when the Induction Proof has at least one of - multiple base cases - step N relies on some step between step N-1 and step 0 - step N relies on multiple steps between ste N-1 and step 0 Comon case requiring Complete Induction: - formula using either even or odd values - the Fibonacci sequence step 0 = x (First base case) step 1 = y (Second Base Case) step N = (step N-1) + (step N-2) When dealing with Complete Inductive Proofs, we must - solve each base case seperately - solve each inductive step seperately