CPSC 170 Lab 7: Mathematical Induction

Use mathematical induction to prove each of the following. Be sure to identify the base case, the inductive step, and the proof, and be clear about where you use the inductive hypothesis.
  1. 1 + 5 + ... + 4n-3 = n(2n-1)    n>0

  2. 2 + 6 + 10 + ... + (4n-2) = 2n2    n>0

  3. 2n > n2    n>4

  4. Any amount of postage greater than or equal to 12 cents can be built using only 4 and 5 cent stamps.

  5. For every n>1, n is either a prime number or a product of prime numbers.

  6. What is wrong with the following inductive proof?

    Any n horses, n>=1, are all the same color.

    Base case (n=1): Any horse is the same color as itself.

    Inductive step: If any r horses, 1<=r<=k, are all the same color, then any k+1 horses are all the same color.

    Proof: Divide your k+1 horses into two non-empty groups. One group will have x horses, and the other group will have (k+1)-x horses. Both x and (k+1)-x are less than k+1, so by the inductive hypothesis each group of horses is all the same color. Now choose one horse from the first group and one horse from the second group. Again, by the inductive hypothesis these two horses must be the same color, so all of the horses must be the same color.