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