Statements, implication and converse
A statement (proposition) is a sentence that is either true or false, such as '7 is prime'.
- P ⇒ Q ('if P then Q', 'P implies Q'): whenever P is true, Q is true.
- The converse is Q ⇒ P. It may be false: 'if n > 2 then n > 1' is true, but 'if n > 1 then n > 2' fails for n = 1.5.
- P ⇔ Q ('if and only if'): both P ⇒ Q and Q ⇒ P are true.
- The contrapositive of P ⇒ Q is 'not Q ⇒ not P'. It is always true when P ⇒ Q is true.
A proof uses definitions, axioms (facts we accept) and already proved theorems, joined by correct reasoning.
Direct proof (deduction)
Start from the facts you are given and reach the result step by step. Algebra helps us talk about every number at once:
- even number: 2n; odd number: 2n + 1; consecutive numbers: n, n + 1; a multiple of 3: 3n.
Example: prove the sum of two odd numbers is even. Let them be 2a + 1 and 2b + 1. Sum = 2a + 2b + 2 = 2(a + b + 1), which is 2 × a whole number, so it is even. ∎
Finish a proof with a clear sentence or the symbol ∎ (QED).
Proof by exhaustion and disproof by counterexample
Exhaustion: split the problem into a finite set of cases that covers every possibility, then prove each case. Example: every whole number is 3k, 3k + 1 or 3k + 2. Squaring gives 9k², 9k² + 6k + 1 and 9k² + 12k + 4 = 3(3k² + 4k + 1) + 1. So a square number leaves remainder 0 or 1 on division by 3, never 2.
Counterexample: to show a claim is false, find just one case where it fails. 'n² + n + 41 is always prime' works for n = 0 to 39 but fails at n = 40 (40² + 40 + 41 = 41²). Many examples never prove a general claim; one counterexample always disproves it.
Proof by contradiction
Assume the statement is false. Reason correctly until you reach something impossible (a contradiction). So the assumption was wrong, and the statement is true.
√2 is irrational. Suppose √2 = p/q with whole numbers p, q having no common factor. Then p² = 2q², so p² is even, so p is even: p = 2k. Then 4k² = 2q², so q² = 2k², so q is even too. Both even means they share a factor 2: contradiction. ∎
There are infinitely many primes. Suppose the primes are only p₁, p₂, …, pₙ. Let N = p₁p₂…pₙ + 1. N leaves remainder 1 when divided by each listed prime, so N is prime or has a prime factor not on the list. Either way the list was not complete: contradiction. ∎
Proving geometric theorems
Write a geometric proof as numbered statements, each with a reason (given, definition, or a known theorem). Common reasons: vertically opposite angles are equal; with parallel lines, alternate angles are equal and corresponding angles are equal; angles on a straight line add to 180°; congruence tests SSS, SAS, ASA, RHS; similarity tests AA, SAS, SSS.
Angle sum of a triangle. Draw a line through the top vertex parallel to the base. The two angles beside the top angle equal the two base angles (alternate angles). The three angles now sit on a straight line, so they add to 180°. ∎
Synthetic proofs use pure geometry like this. Analytic proofs place the figure on coordinates and use algebra: for example, to show the diagonals of a parallelogram bisect each other, put the vertices at (0, 0), (a, 0), (b, c), (a + b, c) and show both diagonals have the same midpoint ((a + b)/2, c/2).
Key formulas and definitions
- Even: 2n · Odd: 2n + 1 · Consecutive: n, n + 1
- P ⇒ Q: if P then Q · converse: Q ⇒ P
- Contrapositive: not Q ⇒ not P (same truth as P ⇒ Q)
- P ⇔ Q: P ⇒ Q and Q ⇒ P
- Prove = all cases · Disprove = one counterexample
- Contradiction: assume not-P → impossible → P is true
- Triangle angle sum = 180° (parallel line + alternate angles)
Worked examples
1. Prove that the product of two odd numbers is odd.
(2a + 1)(2b + 1) = 4ab + 2a + 2b + 1 = 2(2ab + a + b) + 1, which is of the form 2n + 1, so it is odd. ∎
2. Prove that the sum of three consecutive whole numbers is a multiple of 3.
n + (n + 1) + (n + 2) = 3n + 3 = 3(n + 1), a multiple of 3. ∎
3. Disprove: 'If n is prime, then 2n + 1 is prime.'
Try n = 7: 2(7) + 1 = 15 = 3 × 5, not prime. One counterexample is enough. ∎
4. Prove by exhaustion that n³ − n is even for n = 1, 2, 3, 4, 5.
0, 6, 24, 60, 120: all even. (In general n³ − n = (n − 1)n(n + 1) contains an even number, so it is always even.)
5. Prove by contradiction that there is no largest even number.
Assume E is the largest even number. Then E + 2 is also even and E + 2 > E. This contradicts E being the largest. So there is no largest even number. ∎
6. Two lines AB and CD cross at O. Prove that ∠AOC = ∠BOD.
∠AOC + ∠COB = 180° (angles on line AB). ∠COB + ∠BOD = 180° (angles on line CD). So ∠AOC = 180° − ∠COB = ∠BOD. ∎ (Vertically opposite angles are equal.)
Common mistakes
- Checking a few examples and calling it a proof. Examples show it might be true; a proof must cover every case.
- Using the same letter for two different numbers: two odd numbers are 2a + 1 and 2b + 1, not 2n + 1 twice.
- Assuming the converse is true. P ⇒ Q does not mean Q ⇒ P.
- Writing geometric steps without reasons. Every line needs 'given', a definition or a theorem name.