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