CPSC170
Solutions to Induction Review Exercises

1. Sum(i=0,n) 2i = 2n+1-1       n>0
   
   Base case: n=1  
   Left side: Sum(i=0,1) 2i = 20 + 21 = 1 + 2 = 3. 
   Right side: 21+1-1 = 4-1 = 3..
   
   Inductive step: 
   If Sum(i=0,k) 2i = 2k+1-1 then Sum(i=0,k+1) 2i = 2k+2-1
   
   Proof: By the inductive hypothesis, Sum(i=0,k) 2i = 2k+1-1.  
   Adding 2k+1 to both sides gives
   
   Sum(i=0,k+1) 2i =  2k+1-1 + 2k+1
                  = 2k+2-1.
   

   
   

2. Sum(i=1,n) i+2 = n(n+5)/2     n>0
   
   Base case: n=1  
   Left side:  Sum(i=1,n) i+2 = 1+2 = 3.
   Right side: 1(1+5)/2 = 3.
   
   Inductive step: 
   If Sum(i=1,k) i+2 = k(k+5)/2 then Sum(i=1,k+1) i+2 = (k+1)((k+1)+5)/2 
                                  = (k+1)(k+6)/2 = (k2+7k+6)/2
   
   Proof: By the inductive hypothesis, Sum(i=1,k) i+2 = k(k+5)/2.
   Adding (k+1)+2 to both sides gives
   
   Sum(i=1,k+1) i+2 = k(k+5)/2 + k+3
                 = (k2+5k)/2 + (2k+6)/2
                 = (k2+5k+2k+6)/2 
                 = (k2+7k+6)/2.
   

   
   

3. Any postage greater than or equal to 14 cents can be made with only 3 cent
   and 8 cent stamps.
   
   Base case: Need three base cases:
   n=14: 3+3+8
   n=15: 3+3+3+3+3
   n=16: 8+8
   
   Inductive step: If any postage r, 14<=r<=k, can be made using only 3 
   cent and 8 cent stamps, then postage k+1 can be made using only 3 cent
   and 8 cent stamps.
   
   Proof: We have shown 14, 15, and 16 as base cases, so we can assume
   that k+1>=17.  This means that k+1-3>=14, so by the inductive hypothesis
   we can make postage for k+1-3 using only 3 cent and 8 cent stamps.  To make
   postage for k+1, simply add a 3 cent stamp.