Proof, exhaustion and counterexamples

What you’ll learn

• Build a complete logical argument from stated assumptions.
• Use exhaustion for finite cases and a counterexample to disprove a claim.

Understand the idea

A proof must cover every permitted case. Algebra often does this by expressing an arbitrary integer as $n$, an even integer as $2k$, or an odd integer as $2k+1$. Explain why the final expression has the claimed property, rather than stopping at an unexplained formula.

Proof by exhaustion checks every member of a finite set or every possible type of case. A universal statement is disproved by one admissible counterexample. Several successful examples cannot prove a statement about all integers, but one failing example can disprove it.

Key formulae

$$n\text{ even}\iff n=2k\text{ for some }k\in\mathbb Z$$

$$n\text{ odd}\iff n=2k+1\text{ for some }k\in\mathbb Z$$

$$n(n+1)\text{ is divisible by }2\quad(n\in\mathbb Z)$$

Worked example

Prove that the square of any odd integer is odd.

1. Write the arbitrary odd integer as $n=2k+1$, where $k$ is an integer.
2. Square: $n^2=4k^2+4k+1=2(2k^2+2k)+1$.
3. The quantity $2k^2+2k$ is an integer, so the square has the form twice an integer plus one.

Answer: Therefore every odd integer has an odd square.