Prove the following statements using mathematical induction.


1. Consider the predicate P(n): 1 + 2 + 3 + ... + n = n(n+1)/2 is true for any positive integer n.

a) Show that P(1) is true, completing the base of the induction.

b) What do you need to prove in the inductive step?

c) Complete the inductive step



2. Consider the predicate P(n): 1 + 3 + 5 + ... + (2n-1) = n^2 is true for any positive integer n.

a) Show that P(1) is true, completing the base of the induction.

b) What do you need to prove in the inductive step?

c) Complete the inductive step


3.  Prove that 2^n > n^2 for every positive n that is greater than 4.


4.  Prove that n^5 - n is divisible by 5 for every positive integer n.


5.  Determine which amounts of postage can be formed using only 4 cent and 11 cent stamps.  Prove your answer using mathematical induction.


6. Prove that 1*2 + 2*3 + 3*4 + ... + n*(n+1) = (n)(n+1)(n+2)/3 for every positive integer n.


7. a) Find a formula for 1/2 + 1/4 + 1/8 + ... + 1/(2^n)

   b) Prove the formula you conjectured in part (a).


8.  Consider the sequence:  1 + 2 + 4 + 8 + 16 + ...
    What is the sum of the first n elements?  Prove your answer using mathematical induction.