Proof methods and counterexamples: VCE Specialist Mathematics Unit 3

What this dot point is asking

VCAA wants you to prove and disprove mathematical statements using the main methods: direct proof, proof by contrapositive, proof by contradiction, and disproof by a single counterexample. You also need the logical language of implication and quantifiers so you know exactly what a statement claims and what would establish or refute it.

Implication and quantifiers

Most statements to prove have the form "if $P$ then $Q$", written $P \Rightarrow Q$. The converse $Q \Rightarrow P$ and the contrapositive "not $Q \Rightarrow$ not $P$" are different statements: the contrapositive is logically equivalent to the original, but the converse is not.

A universal statement ("for all $x$, ...") claims something about every case. An existential statement ("there exists $x$ such that ...") claims at least one case works. The way you prove or disprove each depends on this structure.

Direct proof

Assume the hypothesis $P$ and deduce $Q$ by valid steps. For example, to prove "the sum of two even integers is even", write the integers as $2m$ and $2n$, add to get $2(m + n)$, and note this is even. Direct proof is the default when the path from $P$ to $Q$ is clear.

Proof by contrapositive

To prove $P \Rightarrow Q$, prove the equivalent "not $Q \Rightarrow$ not $P$". This helps when the negation of $Q$ is easier to work with. For instance, "if $n^2$ is even then $n$ is even" is awkward directly, but the contrapositive "if $n$ is odd then $n^2$ is odd" follows at once: $n = 2k + 1$ gives $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, which is odd.

Proof by contradiction

Assume the statement is false, then derive something impossible. The classic example is proving $\sqrt{2}$ is irrational: assume $\sqrt{2} = \frac{p}{q}$ in lowest terms, square to get $p^2 = 2q^2$, deduce $p$ is even, then $q$ is even, contradicting "lowest terms". Since the assumption leads to contradiction, the original statement holds.

Disproof by counterexample

A universal statement is false if even one case fails, so a single counterexample disproves it. To disprove "every prime is odd", give the example $2$, which is prime and even. You do not need to explain why other primes are odd; one exception is enough.

Examples in context

Example 1. To disprove "$n^2 + n + 41$ is prime for all positive integers $n$", use $n = 41$, which gives a multiple of $41$.

Example 2. "The product of two odd integers is odd" is a direct proof: $(2a+1)(2b+1) = 2(2ab + a + b) + 1$.

Try this

Q1. State the contrapositive of "if it rains then the ground is wet". [1 mark]

• Cue. If the ground is not wet then it did not rain.

Q2. Disprove "every multiple of $3$ is odd". [1 mark]

• Cue. $6$ is a multiple of $3$ and is even.

Q3. Outline a proof by contradiction that there is no largest integer. [2 marks]

• Cue. Assume $N$ is largest; then $N + 1$ is larger, a contradiction.