Session 8: Induction I — Naturals and Strong Induction

Overview

Where induction comes from, why it is valid, and how to use the induction hypothesis correctly.

Lecturer

Yara Sleem (CSE + Mathematics)

Session Information

Core Concepts

  • The induction principle stated as an inference rule
  • Why it is valid: the well-ordering of ℕ (detailed)
  • Peano axioms: zero, successor function, and induction
  • Ordinary induction (with attention to where the induction hypothesis is used)
  • Strong induction (and when the ordinary IH is insufficient)
  • Choosing what to induct on (with examples)
  • Classic failures and anecdotes: the “all horses are the same colour” proof
  • Course convention: every induction proof states the induction hypothesis explicitly (on its own line)

Slides

Session 8 Slides: Download PDF

Readings

Exercises & Extra Steps

  • Practice (not collected): prove 2ⁿ > n² for n ≥ 5
  • Practice (not collected): prove every integer n ≥ 2 has a prime factorization
  • Practice (not collected): find the exact n at which the horses argument breaks
  • Problem Set 2 due today — hand it in on paper at the start of the session

Questions? Reach out on the course WhatsApp!