myLearning

Step 21: Proofs and discrete maths

Direct proof, contrapositive, and contradiction

Step 21 · Proofs and discrete maths topics

Prove if-then statements directly, through their contrapositive, or by contradiction, and write each proof in clear steps.

Direct proof

To prove 'if P then Q' directly, assume P, use definitions and known facts, and reason step by step until you reach Q. Definitions do the heavy lifting: an even integer is 2k and an odd integer is 2k + 1, for some integer k.

Example: Odd times odd

Prove: if m and n are odd, then mn is odd.

  1. Write m = 2a + 1 and n = 2b + 1.
  2. mn = 4ab + 2a + 2b + 1, which is 2(2ab + a + b) + 1.
  3. That is 2 times an integer, plus 1.

AnswerSo mn is odd

Example: Divisibility

Prove: if a divides b and b divides c, then a divides c.

  1. b = ak and c = bm for some integers k and m.
  2. So c = (ak)m = a(km).

Answera divides c, since km is an integer

Proof by contrapositive

'If P then Q' says the same as 'if not Q then not P'. When the hypothesis is awkward to use but the negated conclusion is easy, prove the contrapositive instead.

Example: Squares

Prove: if n² is even, then n is even.

  1. Contrapositive: if n is odd, then n² is odd.
  2. n = 2k + 1 gives n² = 4k² + 4k + 1, which is 2(2k² + 2k) + 1: odd.

AnswerSo if n² is even, n must be even

Example: Sums

Prove: if x + y ≥ 10, then x ≥ 5 or y ≥ 5.

  1. Contrapositive: if x < 5 and y < 5, then x + y < 10.
  2. Adding the two inequalities gives exactly that.

AnswerProved

Proof by contradiction

To prove a statement by contradiction, assume it is false and reason until you reach something impossible. The assumption must have been wrong, so the statement is true.

Example: √2 is irrational

Prove that √2 is not a fraction.

  1. Suppose √2 = a/b in lowest terms. Then a² = 2b², so a² is even, so a is even: a = 2c.
  2. Then 4c² = 2b², so b² = 2c² and b is even too.
  3. But a/b was in lowest terms, so a and b cannot both be even.

AnswerA contradiction, so √2 is irrational

Example: Infinitely many primes

Prove there are infinitely many primes.

  1. Suppose p₁, p₂, …, pₙ are all of them, and let N = p₁p₂⋯pₙ + 1.
  2. Dividing N by any of the pᵢ leaves remainder 1, so none of them divides N.
  3. But N > 1 has some prime factor, and it is not on the list.

AnswerA contradiction, so the primes never run out

Try it yourself

Work each one on paper first, then open the answer to check.

  1. Prove that the sum of two even integers is even.

    Show answer

    2a + 2b = 2(a + b), which is even

  2. To prove 'if n² is odd then n is odd' by contrapositive, what do you assume?

    Show answer

    That n is even

  3. To prove 'there is no largest integer' by contradiction, what do you assume?

    Show answer

    That there is a largest integer N

  4. Give a counterexample to 'every prime is odd'.

    Show answer

    2

  5. Prove that if n is odd, then n² − 1 is divisible by 4.

    Show answer

    (2k + 1)² − 1 = 4k² + 4k, which is 4(k² + k)

  6. Show that the product of two fractions a/b and c/d is a fraction.

    Show answer

    It is ac ÷ bd, and bd is not 0

What next?