CPSC 170 Postlab 7

Use the First Principle of Mathematical Induction to prove the following:
1. n² >= 2n+3   for   n>=3

   
   Base case: n=3  32 ?>= 2*3+3
                   9 >= 9
   
   Inductive step: If k2 >= 2k+3 then (k+1)2 >= 2(k+1)+3,
   or k2+2k+1 >= 2k+5.
   
   
   Proof: By the inductive hypothesis, k2 >= 2k+3.
   Adding 2k+1 to both sides gives
   
           k2+2k+1 >= 2k+3 + 2k+1
   
      =>   k2+2k+1 >= 4k+4
   
   But we're trying to show that  k2+2k+1 >= 2k+5.  This will be true
   by the transitive property of >= if
   
           4k+4 >= 2k+5
   
       =>  2k >= 1, or k >= 1/2.  We are concerned only with k>=3, so the property holds.        
   
   

   Use the Second Principle of Mathematical Induction to prove the following:
2. Any amount of postage greater than or equal to 12 cents can be built using only 4-cent and 5-cent stamps.

   Base cases: 
                     n=12: 12=4+4+4
                     n=13: 13=4+4+5
                     n=14: 14=4+5+5
                     n=15: 15=5+5+5
   
   Inductive step: If any amount of postage r, 12<=r<=k, can be built
   using only 4-cent and 5-cent stamps, then postage k+1 can be built using only
   4-cent and 5-cent stamps.
   
   Proof: Cases k=12, k=13, k=14, and k=15 were proved in the base case, 
   so here we can assume that k+1 >= 16.  By the inductive hypothesis, we know 
   that the postage for k-3 can be formed using 4-cent and 5-cent stamps since
   (k+1)>=16 => (k-3)>=12.  Now take the postage for k-3 and add a 4-cent stamp;
   this gives the postage for k+1.