AHL 1.15 (HL)—Advanced proof

Choose induction or contradiction to prove a claim.

Induction proves a statement for all integers by a base case plus an implication from k to k+1; contradiction assumes the claim is false and derives impossibility.

Worked example
For 1+2+…+n=n(n+1)/2, verify n=1, then assume k and prove k+1.

Worked example
What must induction include besides the algebra? a valid base case and the inductive link.

Common boundary
Checking several values is not induction.

Contradiction example: assume $\sqrt2=p/q$ in lowest terms. Then $p^2=2q^2$, so $p$ is even; writing $p=2k$ shows $q$ is also even, contradicting lowest terms. Counterexample example: the claim 'there are no positive integer solutions to $x^2+y^2=10$' is false because $(x,y)=(1,3)$ gives $1^2+3^2=10$. State exactly which universal claim the example violates.