Proof: Induction, Contradiction and Inequality Arguments
Core concepts
Ext 1 proof questions ask you to construct a logical argument, not just compute. Master mathematical induction (base case, inductive hypothesis, inductive step, conclusion), proof by contradiction (classic irrationality of $\sqrt2$, infinitude of primes), direct proof, and inequality arguments using squares ($x^2\ge0$), the AM–GM inequality, or analysing a difference. Also be able to disprove a statement with a single counterexample and to write converses and contrapositives correctly.
Traps
- Skipping the base case or the explicit statement of the inductive hypothesis.
- Not using the hypothesis in the inductive step - the proof must depend on it.
- Confusing proof by contradiction with proof by contrapositive.
- In inequality proofs, multiplying by a variable without knowing its sign.
- Asserting what you are trying to prove; each line must follow from previous lines.
Rule of thumb
For induction, write the goal for $n=k+1$ before manipulating, then force the $n=k$ expression to appear. For inequalities, consider the difference of the two sides and show it is non-negative by completing the square.
Worked example
Prove $\sum_{r=1}^{n}r^2=\frac{n(n+1)(2n+1)}{6}$ by induction. Base $n=1$: LHS $=1$, RHS $=\frac{1\cdot2\cdot3}{6}=1$. Assume true for $n=k$. For $n=k+1$: add $(k+1)^2$ to the hypothesis, giving $\frac{k(k+1)(2k+1)}{6}+(k+1)^2=\frac{(k+1)[k(2k+1)+6(k+1)]}{6}=\frac{(k+1)(2k^2+7k+6)}{6}=\frac{(k+1)(k+2)(2k+3)}{6}$, which is the formula with $n=k+1$. Hence true for all $n\ge1$.