VCE Specialist Mathematics (Year 11) · Algebra and Structure · 20m read

Logic, Proof and Mathematical Reasoning

Ever wondered why mathematicians won't accept "it works for these numbers" as proof? In this topic, you'll learn to build bulletproof arguments using three powerful techniques: direct proof (showing something's true step-by-step), proof by contradiction (assuming it's false and finding the absurdity), and mathematical induction (proving something works for all numbers by showing it works for one, then the next, then all). These skills are essential for VCE Specialist Maths and show examiners you genuinely understand why mathematics works, not just that it does.

Learning objective: Use propositional logic, construct proofs by direct and indirect methods, and apply mathematical induction.

By the end of this lesson you can:

I identify the hypothesis and conclusion of a conditional statement.
I write the converse, inverse and contrapositive of a given statement.
I construct a proof by contradiction and a proof by mathematical induction.
I use counterexamples to disprove universal statements.

A proof is a chain of logic. Each link must follow from the last. One weak link and the whole chain breaks.

Propositions, conditionals and their forms

A proposition is a statement that is definitively true or false. "All prime numbers are odd" is a proposition (it's false because 2 is prime and even).

### Conditional statements

A conditional statement has the form "If $P$, then $Q$":

$$P \Rightarrow Q \qquad \text{("$P$ implies $Q$")}$$

$P$ is the hypothesis (premise/antecedent)
$Q$ is the conclusion (consequent)

### Related forms

Given $P \Rightarrow Q$:

| Name | Form | Example |
|------|------|---------|
| Original | $P \Rightarrow Q$ | If $x > 2$, then $x^2 > 4$ |
| Converse | $Q \Rightarrow P$ | If $x^2 > 4$, then $x > 2$ |
| Inverse | $\neg P \Rightarrow \neg Q$ | If $x \leq 2$, then $x^2 \leq 4$ |
| Contrapositive | $\neg Q \Rightarrow \neg P$ | If $x^2 \leq 4$, then $x \leq 2$ |

Critical fact: The contrapositive is logically equivalent to the original. The converse and inverse are equivalent to each other but NOT to the original.

### Biconditional

$P \iff Q$ means "$P$ if and only if $Q$" — both $P \Rightarrow Q$ AND $Q \Rightarrow P$ hold simultaneously. This is the standard definition of mathematical "equivalence."

### Universal quantifier

"For all $x$, $P(x)$" — written $\forall x, P(x)$. To prove this, you must cover all cases. To disprove it, one counterexample suffices.

"There exists $x$ such that $P(x)$" — written $\exists x, P(x)$. To prove this, one example suffices.

Methods of proof

### Direct proof

Assume the hypothesis $P$ is true and use logical steps to conclude $Q$.

Structure: "Assume $P$. Then [steps]. Therefore $Q$. QED."

Example: Prove that the sum of two odd integers is even.

*Proof:* Let $m, n$ be odd. Then $m = 2j+1$ and $n = 2k+1$ for integers $j, k$.
$$m + n = (2j+1) + (2k+1) = 2(j+k+1)$$
Since $j+k+1$ is an integer, $m+n$ is even. $\square$

---

### Proof by contradiction (reductio ad absurdum)

Assume the negation $\neg Q$ (or $\neg P$) and show this leads to a contradiction.

Structure: "Assume for contradiction that $\neg Q$. Then [steps lead to something impossible]. This is a contradiction, so $Q$ must be true. QED."

Classic example: Prove that $\sqrt{2}$ is irrational.

*Proof:* Assume $\sqrt{2} = \frac{p}{q}$ in lowest terms (i.e., $\gcd(p,q) = 1$).
Then $2 = \frac{p^2}{q^2} \implies p^2 = 2q^2$, so $p^2$ is even, so $p$ is even.
Write $p = 2k$: $(2k)^2 = 2q^2 \implies 4k^2 = 2q^2 \implies q^2 = 2k^2$, so $q$ is even.
But then $p$ and $q$ are both even, contradicting $\gcd(p,q) = 1$. $\square$

---

### Proof by contrapositive

Instead of proving $P \Rightarrow Q$, prove the equivalent $\neg Q \Rightarrow \neg P$.

Sometimes easier when the negation is simpler to work with.

---

### Mathematical induction

Used to prove statements $P(n)$ for all positive integers $n$.

Two steps:
1. Base case: Show $P(1)$ is true.
2. Inductive step: Assume $P(k)$ is true (inductive hypothesis). Show $P(k+1)$ follows.

By these two steps, $P(n)$ is true for all $n \geq 1$.

> Why it works: Like an infinite row of dominoes. Showing the first falls (base case) and each falling knocks the next (inductive step) means all fall.

Proof checklist

State your assumptions: Every proof begins: "Let..." or "Assume..." — be explicit.
Use general representatives: Prove for arbitrary $n$, $m$, $x$ — not specific values.
Conclude clearly: End with the exact conclusion the question asked for. State "Therefore..."
Mark the end: Use $\square$ or QED to signal the proof is complete.
Induction: write IH explicitly: State "Assume $P(k)$ is true for some $k \geq 1$" before the inductive step.
Counterexample: one suffices: To disprove "for all", one example where it fails is enough.

Worked example (Easy)

Prove that if $n$ is odd, then $n^2$ is odd.

Represent odd $n$. Let $n$ be an odd integer. By definition, $n = 2k + 1$ for some integer $k$.
Square $n$. n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1
Conclude. Since $2k^2 + 2k$ is an integer, $n^2 = 2m + 1$ where $m = 2k^2 + 2k$. Hence $n^2$ is odd.

Answer: Direct proof: $n = 2k+1 \Rightarrow n^2 = 2(2k^2+2k)+1$, which has the form $2m+1$ (odd). $\square$

Worked example (Medium)

Prove by mathematical induction that $\displaystyle\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ for all positive integers $n$.

Base case: $n = 1$. LHS = $\sum_{k=1}^{1} k = 1$. RHS = $\frac{1 \cdot 2}{2} = 1$. LHS = RHS ✓
Inductive hypothesis. Assume the statement is true for $n = k$, i.e., $\sum_{j=1}^{k} j = \frac{k(k+1)}{2}$.
Inductive step: prove for $n = k+1$. Add the $(k+1)$-th term to both sides of the IH: \sum_{j=1}^{k+1} j = \frac{k(k+1)}{2} + (k+1)
Factor out $(k+1)$. = (k+1)\left(\frac{k}{2} + 1\right) = (k+1) \cdot \frac{k+2}{2} = \frac{(k+1)(k+2)}{2}
This is the formula for $n = k+1$. The RHS equals $\frac{(k+1)((k+1)+1)}{2}$ ✓.

Answer: By induction, $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ for all positive integers $n$. $\square$

Worked example (Hard)

Prove that there are infinitely many prime numbers. (Euclid's proof)

Assume for contradiction. Suppose there are only finitely many primes: $p_1, p_2, \ldots, p_n$.
Construct a number. Let $N = p_1 \cdot p_2 \cdots p_n + 1$ (the product of all primes, plus 1).
Analyse divisibility. For any prime $p_i$ in our list: dividing $N$ by $p_i$ leaves remainder 1 (not 0). So no $p_i$ divides $N$.
Reach the contradiction. But every integer $> 1$ has a prime factor. So $N$ has a prime factor $p$ not in our list — contradicting the assumption that the list was complete.

Answer: The assumption leads to a contradiction; hence there are infinitely many primes. $\square$

Common mistakes

Verifying a specific case instead of proving for all cases "I checked $n = 1, 2, 3$ and it works" is NOT a proof. A theorem must hold for all values in the domain, not just a few. Fix: Use general variables ($n$, $x$, $a$) that represent any element of the domain, not specific numbers.
In induction, using $P(k+1)$ to prove $P(k+1)$ The inductive step must derive $P(k+1)$ FROM $P(k)$ — not assume the conclusion in the proof. Fix: Start from $P(k)$ (the inductive hypothesis) and transform it algebraically to reach the $n = k+1$ formula.
Confusing converse with contrapositive The converse of $P \Rightarrow Q$ is $Q \Rightarrow P$ — NOT logically equivalent. The contrapositive $\neg Q \Rightarrow \neg P$ IS equivalent. Fix: Memorise: Contrapositive = equivalent (negate and switch). Converse = not equivalent (just switch).

Why proof matters — the foundation of mathematical certainty

Mathematics is unique among the sciences: it achieves absolute certainty through proof. In physics or biology, a theory is supported by evidence but could be overturned by new observations. In mathematics, a proven theorem is true forever — Euclid's proofs from 300 BCE are as valid today as when they were written.

The three proof techniques you learn in Specialist Maths have distinct logical structures. Direct proof builds a chain of logical implications: $P \Rightarrow Q_1 \Rightarrow Q_2 \Rightarrow \cdots \Rightarrow R$. Proof by contradiction assumes $\neg R$ and derives a logical impossibility, concluding $R$ must be true. Mathematical induction proves infinitely many statements at once by showing: (1) the first case is true, and (2) each case implies the next — like an infinite line of dominoes.

Induction is particularly powerful because it proves statements about ALL positive integers, despite there being infinitely many. The base case establishes $n = 1$; the inductive step shows that truth at $n = k$ guarantees truth at $n = k + 1$. Together, they cover $n = 1, 2, 3, \ldots$ — every positive integer. This is the principle of mathematical induction, and it is one of the axioms that defines the natural numbers themselves (Peano axioms).

Practice questions

The contrapositive of "If $x$ is prime, then $x > 1$" is:
1. If $x > 1$, then $x$ is prime
2. If $x \leq 1$, then $x$ is not prime
3. If $x$ is not prime, then $x \leq 1$
4. If $x \leq 1$, then $x$ is prime
(1 marks)
Provide a counterexample to disprove: "For all integers $n$, $n^2 + n + 41$ is prime."
(2 marks)
Prove by induction that $\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$ for all positive integers $n$.
(4 marks)

Summary

Contrapositive of $P \Rightarrow Q$ is $\neg Q \Rightarrow \neg P$ — logically equivalent.
Converse ($Q \Rightarrow P$) is NOT equivalent to the original.
Direct proof: assume hypothesis, derive conclusion algebraically.
Contradiction: assume negation, derive impossibility.
Induction: base case + inductive step (start from $P(k)$, reach $P(k+1)$).
Disprove a universal claim: one counterexample is sufficient.