CPSC 220
Fall 2007
HW 3: Review of Proof by Induction

1. Use mathematical induction to show that Sum(i=3,n)2i = (n+3)(n-2)    n>=3.

   Base case: n=____.  Left side:________________  Right side:__________________
   
   Inductive step: 
   
   If _____________________________________  then ____________________________________.
            (property for k)                         (property for k+1)
   
   
                                              => ____________________________________
                                                     (simplify property for k+1)
   
   Proof:
   By the inductive hypothesis, ________________________________________________.
   
   To make the left side of this look like what we are trying to show, add
   
    ___________ to both sides.
   
   
   This gives ___________________________________________________________________.
   
   
   Simplifying, we get __________________________________________________________
   
   
   ______________________________________________________________________________.
   

   ---

2. Use mathematical induction to show that Sum(i=0,n)2ⁱ = 2ⁿ⁺¹-1    n>=1

   Base case:
   
   
   Inductive step:
   
   
   
   
   Proof:
   By the inductive hypothesis, _________________________________________________.
   
   (... You finish!)