Direct proof and mathematical induction
A row of dominoes falls completely if the first falls and each one knocks over the next. That is exactly how induction works.
A direct proof starts from what is given and uses definitions and known results step by step. Mathematical induction proves P(n) for all natural numbers n in two steps: P(1) is true, and if P(k) is true then P(k + 1) is true.
Formula: P(1) true and P(k) ⇒ P(k + 1) ⇒ P(n) true for all n
Rule 1: Straightforward proof — Write each step with its reason.
- Easy: If x² − 7x + 12 = 0 then (x − 3)(x − 4) = 0, so x = 3 or x = 4.
- Medium: f(x) = 3x + 4 is one-one: 3a + 4 = 3b + 4 gives a = b.
- Exam-type: The sum of two even numbers is even: 2m + 2n = 2 (m + n).
Rule 2: Induction — Show the base case, then the step.
- Easy: 1 + 2 + ... + n = n (n + 1) / 2: for n = 1 it is 1 = 1; adding (k + 1) to k (k + 1) / 2 gives (k + 1)(k + 2) / 2.
- Medium: 1 + 3 + 5 + ... + (2n − 1) = n²: adding (2k + 1) to k² gives (k + 1)².
- Exam-type: 2ⁿ > n: for n = 1, 2 > 1; if 2ᵏ > k then 2ᵏ⁺¹ > 2k ≥ k + 1.
The induction step must use the assumption P(k); the base case alone is not enough.
Checking a few values of n and calling it a proof.
First domino falls, and each domino knocks the next.
Practice questions
- 1Prove: if x² − 5x + 4 = 0 then x = 1 or x = 4.
- 2Prove that the sum of two odd numbers is even.
- 3Show that f(x) = 5x − 2 is one-one.
- 4For 1 + 2 + ... + n = n (n + 1) / 2, check P(1).
- 5Prove that the product of two odd numbers is odd.
- 6Prove by induction: 2 + 4 + 6 + ... + 2n = n (n + 1).
- 7Prove by induction that n² + n is even for every natural number n.
- 8Given that 1² + 2² + ... + k² = k (k + 1)(2k + 1) / 6, show the formula for k + 1.
Show answers (try them yourself first)
- 1x² − 5x + 4 = (x − 1)(x − 4) = 0, so x = 1 or x = 4
- 2(2m + 1) + (2n + 1) = 2 (m + n + 1), which is even
- 35a − 2 = 5b − 2 gives 5a = 5b, so a = b
- 4Left side 1, right side 1 × 2 / 2 = 1, so P(1) is true
- 5(2m + 1)(2n + 1) = 2 (2mn + m + n) + 1, which is odd
- 6P(1): 2 = 1 × 2. If the sum is k (k + 1), adding 2 (k + 1) gives (k + 1)(k + 2)
- 7P(1): 2 is even. (k + 1)² + (k + 1) = (k² + k) + 2 (k + 1), a sum of two even numbers
- 8Add (k + 1)²: (k + 1)[k (2k + 1) + 6 (k + 1)] / 6 = (k + 1)(2k² + 7k + 6) / 6 = (k + 1)(k + 2)(2k + 3) / 6
Indirect proofs: contrapositive, contradiction and counterexample
To show that no one is in the room, you can show that if someone were there, a contradiction would follow. Sometimes the backwards road is the easier road.
To prove "p ⇒ q" by the contrapositive, prove "not q ⇒ not p". In proof by contradiction, assume the opposite of what is to be proved and reach an impossible result. A counterexample is one example that disproves a "for all" statement.
Formula: p ⇒ q is equivalent to (not q) ⇒ (not p)
Rule 1: Contrapositive and contradiction — Choose the form that is easier to start.
- Easy: "If n² is even then n is even": if n is odd, n² is odd, so the contrapositive is true.
- Medium: "If 3n + 2 is odd then n is odd": if n is even, 3n + 2 is even.
- Exam-type: √2 is irrational: if √2 = p / q in lowest terms then p² = 2q², so p is even; then q is even too, which contradicts lowest terms.
Rule 2: Counterexample — Find one case where the statement fails.
- Easy: "Every prime is odd" is false because of the prime 2.
- Medium: "n² + n + 41 is prime for every n" is false: for n = 40 it equals 41², which is not prime.
- Exam-type: "If a² = b² then a = b" is false: a = 2 and b = −2.
One counterexample is enough to disprove a statement; no number of examples is enough to prove it.
Trying to prove a statement by giving examples.
Prove with logic, disprove with one example.
Practice questions
- 1Give a counterexample to "all odd numbers are prime".
- 2Give a counterexample to "x² > x for all real x".
- 3Write the contrapositive of "if n² is odd then n is odd".
- 4Write the contrapositive of "if ab is even then a or b is even".
- 5Prove by contradiction that there is no integer between 3 and 4.
- 6Prove that √3 is irrational.
- 7Give a counterexample to "the sum of two irrational numbers is irrational".
- 8Prove using the contrapositive: if 5n + 3 is even then n is odd.
Show answers (try them yourself first)
- 19 is odd but not prime
- 2x = 1 gives 1 > 1, which is false (x = 1/2 also fails)
- 3If n is even then n² is even
- 4If a and b are both odd then ab is odd
- 5If an integer n had 3 < n < 4 then n − 3 would be an integer between 0 and 1, impossible
- 6If √3 = p / q in lowest terms then p² = 3q²; 3 divides p, p = 3m, so q² = 3m² and 3 divides q too, a contradiction
- 7√2 + (−√2) = 0, which is rational
- 8If n is even, 5n is even and 5n + 3 is odd, so the contrapositive holds