Proof and Mathematical Reasoning
Core ideas
Direct proof, proof by contradiction, proof by contrapositive, proof by exhaustion, and mathematical induction. Understanding the structure of a rigorous argument - clear assumptions, logical steps, and a definitive conclusion - is central. Recognising counterexamples and the difference between necessary and sufficient conditions is also tested.
Traps
- Induction requires three parts: base case, inductive hypothesis, and inductive step. Omitting the base case invalidates the proof.
- In proof by contradiction, you assume the negation of the statement, not the statement itself.
- Contrapositive ('if not Q then not P') is logically equivalent to the original; converse is not.
- Counterexamples disprove universal statements but do not prove existential ones.
- Be explicit about the domain and any assumptions used.
Rule of thumb
For induction: prove the statement for n = 1 (or the smallest relevant n), assume it holds for n = k, then show it holds for n = k + 1 using that assumption. State each step clearly.
Worked example
Prove by induction that 1 + 3 + 5 + ... + (2n - 1) = n^2. Base case n = 1: LHS = 1, RHS = 1. Assume true for n = k: sum = k^2. For n = k + 1, add the next odd term 2(k+1) - 1 = 2k + 1: k^2 + 2k + 1 = (k + 1)^2. Hence true for all positive integers n.