Recitation 8: Proof by Induction

Part 1: Practice with Induction

Prove the following statements using mathematical induction.

  1. Prove that 1+2+3+...+n=\frac{n(n+1)}{2} for every positive integer n.
  2. Prove that 1+3+5+...+(2n-1)=n^2 for every positive integer n.
  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. Prove that 1*2+2*3+3*4+...+n*(n+1)=\frac{(n)(n+1)(n+2)}{3} for every positive integer n.
  6. Find a formula for \frac{1}{2}+\frac{1}{4}+\frac{1}{8}+...+\frac{1}{2^n} and prove it.
  7. Consider the sequence: 1+2+4+8+16+... What is the sum of the first n elements? Prove this.

Proofs for the first five theorems (pdf format).

Proofs for the first five theorems (html format, harder to read).

Part 2: Extra Practice and Strong Induction

Prove that |\mathcal{P}(A)| = 2^{|A|} for any set A.

For which positive integers are the following propositional functions true?

  1. P(1) is true. For all positive integers n, P(n) \to P(n+1).

  2. P(1) is true. For all positive integers n, P(n) \to P(n+2).

  3. P(1) and P(2) are true. For all positive integers n, P(n) \to P(n+2).

  4. P(0) and P(1) are true. For all positive integers n, P(n) and P(n+1) imply P(n+2).

  5. P(0) is true. For all positive integers n, P(0) \land P(1) \land ... \land P(n-2) \land P(n - 1) \to P(n).

What is wrong with the following proof?

  Theorem: It is possible to form postage of three cents or more using just three cent and four cent stamps.

  Proof:

    Basis step: We can form postage of three cents with a single three cent stamp and postage of four cents using a single four cent stamp.

    Inductive step: Assume that we can form postage of j cents for all nonnegative integers j with j \leq k using just three cent and four cent stamps. We can then form postage of k + 1 cents by replacing one three cent stamp with a four cent stamp or by replacing two four cent stamps by three three cent stamps.

Prove the following using strong induction:

  1. Any amount of change over seven cents can be made out of three cent and four cent coins.

  2. Any positive integer n can be written as a sum of distinct powers of two. For example, 4 = 2^2 and 19 = 2^0 + 2^1 + 2^4.