Introduction to Induction

Return to List of Lectures

Previous Lecture

• Misc
  • My solution to problem set 6 is online in PDF and LaTeX form, via our “Exercises” page
  • Colloquium
    • Alex Rennet, University of Toronto Mississauga
    • “Incompleteness, Hercules and The Hydra”
    • Thursday, Oct. 20, 4:00 pm, Newton 203
    • Extra credit for going and writing a paragraph or so summarizing it and connections you make to it
• Questions?
• Induction
  • Section 4.1
  • Inductive sets
    • Inductive set is subset S of integers…
    • …With property that if k in S then k+1 in S
    • { 17, 18, 19, 20, … } is inductive
    • { 1, 3, 5, 7, … } is not inductive (numbers aren’t consecutive)
    • { x ∈ ℝ | x ≥ 1 } is not inductive (subset of reals, not integers)
    • { x ∈ ℤ | x ≥ -1000 } is inductive
  • Prove by induction that for every natural number n, 2ⁿ is even
    • e.g., 2² = 4, 2³ = 8, all even
    • Basis: n = 1, 2¹ = 2 which is even
    • Induction: Assume r is natural number and 2^r is even (and therefore an integer). Then 2^r+1= 2 2^r which is even since 2^r is an integer
    • So therefore by induction 2ⁿ is even for all natural numbers n
  • Connection to inductive sets?
    • If (2) S is an inductive set and (1) S contains 1 then ℕ is subset of S
      • (2a) Inductive set is subset of integers
      • (2b) With property that if k in S then k+1 in S
    • To prove P true of all naturals
      • Look at truth set of P
      • Prove that it has properties 1 and 2b above (2a is usually given but could in principle also need to be proven)
  • Problem set
• Next
  • More practice with and discussion of induction
  • No new reading

Next Lecture