Recitation 4: Practice with Proofs

Part One

Your TA will guide you through the following proofs using different techniques.

Direct Proof

Show that the sum of two odd integers is even.

Proof by Contrapositive

If x and y are integers and x - y is odd, then x is odd or y is odd.

Proof by Contradiction

Among any group of 25 people, there must be at least three who are all born in the same month.

Proof by Cases

If x is an integer, then x^2 + 5x - 1 is odd.

Part Two

Now work in small groups to prove the following propositions:

  1. Show that the sum of two even integers is even.
  2. If an integer n is not divisible by 2, then it is not divisible by 4.
  3. The square of any integer is either a multiple of 4 or a multiple of 4 plus 1.
  4. If x and y are real numbers, then \max(x, y) + \min(x, y) = x + y.
  5. There is no smallest integer.
  6. \sqrt{2} is irrational (not representable by a fraction).