1.15 Proof by induction, contradiction and counterexample

1.15 Proof by induction, contradiction and counterexample

IB Maths: Analysis and Approaches HL: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • Induction: basis, assumption, inductive step, and a full conclusion.
  • Induction works for sums, divisibility, derivatives and De Moivre.
  • Contradiction: assume the opposite and reach an impossibility, such as a fraction not in lowest terms.
  • Counterexample: one case disproves a "for all" claim, but you must show why it fails.
  • Many examples that work never prove a universal claim.

Structure of induction

Show the basis, assume P(k)P(k), prove P(k+1)P(k+1), then state the full conclusion.

Mathematical induction proves P(n)P(n) for every n∈Z+n\in\mathbb Z^+. IB mark schemes award the final reasoning mark only if the basis and inductive step are both done properly, so always write the full conclusion.

Write "assume P(k)P(k) is true", not "let n=kn=k": you are assuming, not setting a value. Write the target P(k+1)P(k+1) before the inductive step so you know what to aim for.

  1. 1

    Basis

    Show P(1)P(1) is true

  2. 2

    Assumption

    Assume P(k)P(k) is true for some k∈Z+k\in\mathbb Z^+

  3. 3

    Inductive step

    Using it, show P(k+1)P(k+1) is true

  4. 4

    Conclusion

    P(1)P(1) true and P(k)⇒P(k+1)P(k)\Rightarrow P(k+1), so true for all nn by induction

The four parts of every induction proof

Worked example

Prove that ∑r=1nr=n(n+1)2\sum_{r=1}^{n}r=\frac{n(n+1)}2 for all n∈Z+n\in\mathbb Z^+.

Which is the correct way to start the inductive step?

Induction in context

Sums, divisibility, derivatives and De Moivre all follow the same pattern.

In each case assume P(k)P(k), then rewrite P(k+1)P(k+1) in terms of it.

For a sum, add the (k+1)(k+1)th term and factorise. For divisibility, rewrite the assumption (for example 5k=4m+15^k=4m+1) and substitute. For a derivative, differentiate the assumed kkth derivative, for example f(k)(x)=2k−1(2x+k)e2xf^{(k)}(x)=2^{k-1}(2x+k)\mathrm e^{2x}. For De Moivre, multiply cis(kθ)\mathrm{cis}(k\theta) by cis θ\mathrm{cis}\,\theta.

  1. 1

    Base case

    show P(1) is true

  2. 2

    Assume P(k)

    for some positive integer k

  3. 3

    Rewrite P(k + 1)

    in terms of P(k): add a term, substitute or differentiate

  4. 4

    Conclude

    true for n = 1, and P(k) ⇒ P(k+1), so true for all positive integers n

The pattern shared by every induction proof.

Sums

  • Add the (k+1)(k+1)th term
  • Then factorise

Divisibility

  • Assume a multiple
  • Rewrite P(k+1)P(k+1) using it

Derivatives

  • Differentiate the assumed form

De Moivre

  • Multiply by cis θ\mathrm{cis}\,\theta
  • Compound angle identities

Worked example

Show that 5n−15^n-1 is divisible by 4 for all n∈Z+n\in\mathbb Z^+.

To show 7n−17^n-1 is divisible by 6, assume 7k−1=6m7^k-1=6m. What is 7k+1−17^{k+1}-1?

Proof by contradiction

Assume the statement is false and show this leads to something impossible.

For 53\sqrt[3]5: assume 53=pq\sqrt[3]5=\frac pq in lowest terms. Then p3=5q3p^3=5q^3, so 5 divides pp; write p=5mp=5m, giving q3=25m3q^3=25m^3, so 5 divides qq. That contradicts lowest terms.

Euclid: assume finitely many primes p1,…,pnp_1,\dots,p_n. N=p1⋯pn+1N=p_1\cdots p_n+1 leaves remainder 1 on division by each, so it has a prime factor not in the list. NN need not be prime itself. Always state "in lowest terms" at the start.

  1. 1

    Assume the opposite

    Suppose the statement is false

  2. 2

    Deduce

    Follow logical steps from that

  3. 3

    Impossibility

    For example, a fraction both in and not in lowest terms

  4. 4

    Conclude

    The assumption was wrong, so the statement is true

The shape of a proof by contradiction

In the proof that 53\sqrt[3]5 is irrational, where does the contradiction come from?

Counterexamples

One counterexample disproves a "for all" claim, but you must show why it breaks the claim.

A counterexample is a single case where the claim fails. Stating it alone is not enough: show why, for example by exhibiting a factorisation or evaluating both sides of an inequality.

Examples that work never prove a universal claim: n2+n+41n^2+n+41 is prime for n=1,…,39n=1,\dots,39 yet fails at n=40n=40. Watch non-strict inequalities: x=0x=0 satisfies x2≥xx^2\ge x, so it is not a counterexample to it.

51015202530354045200400600800100012001400160018002000xyn = 39: 1601 (prime)n = 40: 41²y = n² + n + 41
n² + n + 41 is prime for n = 1 to 39, but at n = 40 it equals 1681 = 41², a counterexample to the claim 'always prime'.
  • Many examples that workprove nothing
  • One counterexampledisproves "for all"

Worked example

Disprove the claim that n2+41n+41n^2+41n+41 is prime for all n∈Z+n\in\mathbb Z^+.

Which value is a counterexample to "x2>xx^2>x for all real xx"?

Try an exam question

Prove by induction that 5n−15^n-1 is divisible by 4 for all n∈Z+n\in\mathbb Z^+.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Find the common value of both sides of P(n)P(n) when n=4n = 4.

1 mark, marked against the mark scheme

Revision notes