Lesson 6 of 8 · 18 min

Proof by cases and by contrapositive

Prove results for every integer by splitting into cases such as odd and even, and prove an implication by proving its contrapositive instead.

What you will be able to do

  • Prove a result for all n∈Zn \in \mathbb{Z} by considering nn even and nn odd, or n=3kn = 3k, 3k+13k + 1, 3k+23k + 2.
  • Prove 5n2+3n+65n^2 + 3n + 6 is even for all n∈Zn \in \mathbb{Z}.
  • Prove P⇒QP \Rightarrow Q by proving ¬Q⇒¬P\neg Q \Rightarrow \neg P, for example "if n2n^2 is even then nn is even".

Try 5n2+3n+65n^2 + 3n + 6 for a few integers: n=0n = 0 gives 6, n=1n = 1 gives 14, n=2n = 2 gives 32, n=−3n = -3 gives 42. Always even. But writing nn as one general expression does not help here, because an even nn and an odd nn make the expression even for different reasons. So split the integers into cases and prove each one.

Key idea

Proof by cases

If every possibility falls into one of a few cases, prove the result in each case separately. The cases must cover every possibility.

  • Every integer is even or odd: n=2kn = 2k or n=2k+1n = 2k + 1, k∈Zk \in \mathbb{Z}.
  • Every integer leaves remainder 0, 1 or 2 on division by 3: n=3kn = 3k, 3k+13k + 1 or 3k+23k + 2.

Worked example

5n2+3n+65n^2 + 3n + 6 is always even

  • Complex familiar
  • Technology free

Prove that 5n2+3n+65n^2 + 3n + 6 is even for all n∈Zn \in \mathbb{Z}.

4 steps

Try it yourself first, then check the working one step at a time.

Method

  1. State the cases and why they cover every integer.

  2. Substitute and simplify in each case.

  3. Factor out 2 and say the bracket is an integer.

  4. Conclude for all integers.

Watch out for

  • Expanding (2k+1)2(2k + 1)^2 as 4k2+14k^2 + 1.

  • Proving only one case.

By cases

Substitute n=2kn = 2k and n=2k+1n = 2k + 1 and show each result has a factor of 2. Reliable and systematic, but more algebra.

By factorising

5n2+3n+6=n(5n+3)+65n^2 + 3n + 6 = n(5n + 3) + 6. If nn is even, nn is even; if nn is odd, 5n+35n + 3 is odd + odd, which is even. Either way n(5n+3)n(5n + 3) is even, and even + 6 is even. Shorter, but it still uses the two cases.

For n∈Zn \in \mathbb{Z}, which statement about n2+n+1n^2 + n + 1 is true?

Choose one answer

Every integer is exactly one of 3k3k, 3k+13k + 1 or 3k+23k + 2. These three cases cover all of Z\mathbb{Z}, so they can be used for a proof by cases.

Let n=3k+2n = 3k + 2, where k∈Zk \in \mathbb{Z}. Then n2=3m+rn^2 = 3m + r for some m∈Zm \in \mathbb{Z} and r∈{0,1,2}r \in \{0, 1, 2\}. Find rr.

Proof using the contrapositive. Try to prove "if n2n^2 is even, then nn is even" directly. You would start with n2=2kn^2 = 2k and get stuck: n=2kn = \sqrt{2k} tells you nothing useful. But an implication and its contrapositive are equivalent, and the contrapositive, "if nn is odd, then n2n^2 is odd", is easy to prove.

Worked example

If n2n^2 is even, then nn is even

  • Complex familiar
  • Technology free

Prove that for all n∈Zn \in \mathbb{Z}, if n2n^2 is even then nn is even.

4 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Write the contrapositive ¬Q⇒¬P\neg Q \Rightarrow \neg P and say you are proving it.

  2. Prove it directly.

  3. Bring the conclusion back to the original statement.

Watch out for

  • Proving "if nn is even then n2n^2 is even", which is the converse.

Common mistake

Don't prove the converse by accident

To prove "if n2n^2 is even then nn is even", showing that "if nn is even then n2n^2 is even" proves the converse, a different statement. The contrapositive negates and swaps: start from "nn is odd" and finish at "n2n^2 is odd".

To prove "for n∈Zn \in \mathbb{Z}, if 3n+13n + 1 is even then nn is odd" using the contrapositive, which statement should you prove?

Choose one answer

Exam tip

Name the method

Start a contrapositive proof by saying so: "We prove the contrapositive: if nn is odd then n2n^2 is odd." Start a proof by cases by listing the cases and why they cover everything: "Every integer is even or odd." Finish by bringing the cases or the contrapositive back to the original statement.

Summary

  • Proof by cases: split into cases that cover every possibility (even/odd, or 3k3k, 3k+13k + 1, 3k+23k + 2) and prove each one.

  • 5n2+3n+6=n(5n+3)+65n^2 + 3n + 6 = n(5n + 3) + 6 is even for every integer nn, because n(5n+3)n(5n + 3) is always even.

  • A perfect square leaves remainder 0 or 1 on division by 3.

  • To prove P⇒QP \Rightarrow Q, you may prove the equivalent contrapositive ¬Q⇒¬P\neg Q \Rightarrow \neg P instead.

  • "If n2n^2 is even then nn is even" is proved through its contrapositive, and it is the key step in proving 2\sqrt{2} is irrational.

Finished the lesson?

Try the 3 quick checks above and the lesson completes itself, or mark it complete now.

Lesson 6 of 80% read

Save your progress with a free account