← 🧠 Propositional & First-Order Logic
Subtopic 6 of 6

1.6Proof techniques and induction

The idea

Mathematical induction proves a statement for every n ≥ b: show it for the base case, then show that P(k) forces P(k + 1). Like dominoes, one pushed domino and a guarantee that each topples the next.

Think of it like this: A ladder: you can stand on the first rung, and from any rung you can reach the next, so you can reach every rung.

Why it exists

Induction is the standard proof tool for sums, divisibility and recurrences, and "what is the base case" is a favourite trap.

How it works

  1. Base case: verify P at the first n of the claim (not always 1).
  2. Hypothesis: assume P(k) for an arbitrary k ≥ base.
  3. Step: use P(k) to prove P(k + 1).
  4. Conclude P(n) for all n ≥ base. Strong induction assumes P for all values up to k.

Worked example: 2ⁿ > n²

It is false at n = 2, 3, 4 and true from n = 5. The base case is n = 5, and the step is 2ᵏ⁺¹ = 2·2ᵏ > 2k² ≥ (k+1)² for k ≥ 3.

Now play with it

  • →Pick "2ⁿ > n²" and see where the green squares start.
  • →Pick "n² + n + 41 is prime" and find where checking cases lets you down.
123456789101112

First failure at n = 2. It is true again for every n ≥ 5 (up to 12).

false for n = 2, 3, 4, true for all n ≥ 5: the base case must be n = 5.

  1. Base case: check P at the first n where the claim should start.
  2. Hypothesis: assume P(k) for one arbitrary k ≥ base.
  3. Step: use P(k) to prove P(k + 1). Then every n ≥ base follows, like toppling dominoes.

Check yourself

For which n does 2ⁿ > n² hold?

Remember: Base case, then P(k) ⇒ P(k+1). Check where the claim really starts.
Exam notes (the dense version)

Direct proof, contrapositive (prove ¬q → ¬p), contradiction (assume the negation and derive absurdity), and mathematical induction: prove the base case P(b), then P(k) → P(k+1) for all k ≥ b. Strong induction assumes P(b..k). A claim that holds for many cases (n² + n + 41 prime for n ≤ 39) can still be false; the base case must be right (2ⁿ > n² starts at n = 5).

Previous year questions: Propositional & First-Order Logic (25)

PYQs are grouped by topic, so this is the full set for Propositional & First-Order Logic; try the ones that match this subtopic. Open all 25 on the topic page.