CS285 · Chapter 5 · Annotated SlidesMathematical Induction and Recursion
Original
Overview

Mathematical Induction and Recursion

The principle of mathematical induction, its template, proofs of summation formulas, inequalities and divisibility, conjecturing a formula, and recursively defined functions.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 33 slides
  1. 1 Slide 1
  2. 2 Chapter Summary
  3. 3 Climbing an Infinite Ladder
  4. 4 Principle of Mathematical Induction (MI)
  5. 5 Remembering How Mathematical Domino Effect Induction Works -
  6. 6 Mathematical Induction
  7. 7 Mathematical Induction
  8. 8 Mathematical Induction
  9. 9 Mathematical Induction
  10. 10 Mathematical Induction
  11. 11 Mathematical Induction
  12. 12 Mathematical Induction
  13. 13 Mathematical Induction
  14. 14 Mathematical Induction
  15. 15 Mathematical Induction
  16. 16 Mathematical Induction
  17. 17 Mathematical Induction
  18. 18 Conjecturing and Proving Correct a Summation Formula
  19. 19 Mathematical Induction Example-p.316
  20. 20 Proof:
  21. 21 Mathematical Induction Example-p.318
  22. 22 Mathematical Induction Example-p.318
  23. 23 Slide 23
  24. 24 Recursive Definitions & Induction
  25. 25 Recursively Defined Functions
  26. 26 Recursively Defined Functions
  27. 27 Example 2
  28. 28 Example 3
  29. 29 Example 3
  30. 30 Example 4
  31. 31 Example 4
  32. 32 Example 5
  33. 33 Example 5
Slide 1 / 33

Slide 1

Slide 1: Slide 1
Slide 2 / 33

Chapter Summary

Slide 2: Chapter Summary
Slide 3 / 33

Climbing an Infinite Ladder

Slide 3: Climbing an Infinite Ladder
Slide 4 / 33

Principle of Mathematical Induction (MI)

Slide 4: Principle of Mathematical Induction (MI)

Exam angle

PredictionQ1

In an induction proof, the assumption that P(k) is true is called the:

Slide 5 / 33

Remembering How Mathematical Domino Effect Induction Works -

Slide 5: Remembering How Mathematical Domino Effect Induction Works -
Slide 6 / 33

Mathematical Induction

Slide 6: Mathematical Induction

Notes

  1. Template: state P(n) → basis → assume P(k) → show P(k + 1) → conclude.

Slide 7 / 33

Mathematical Induction

Slide 7: Mathematical Induction
Slide 8 / 33

Mathematical Induction

Slide 8: Mathematical Induction

Notes

  1. Sum example: 1 + 2 + … + n = n(n + 1)/2. Add (k + 1) to both sides of P(k).

Exam angle

PredictionQ1

Prove 1 + 2 + … + n = n(n + 1)/2 for n ≥ 1.

Compare with the model answer

Basis: n = 1: 1 = 1·2/2. Inductive step: assume 1 + … + k = k(k + 1)/2. Then 1 + … + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2, which is P(k + 1). So P(n) holds for all n ≥ 1.

Slide 9 / 33

Mathematical Induction

Slide 9: Mathematical Induction
Slide 10 / 33

Mathematical Induction

Slide 10: Mathematical Induction
Slide 11 / 33

Mathematical Induction

Slide 11: Mathematical Induction
Slide 12 / 33

Mathematical Induction

Slide 12: Mathematical Induction

Notes

  1. Divisibility example: n³ − n divisible by 3. Expand (k + 1)³ − (k + 1) = (k³ − k) + 3(k² + k).

Slide 13 / 33

Mathematical Induction

Slide 13: Mathematical Induction
Slide 14 / 33

Mathematical Induction

Slide 14: Mathematical Induction

Notes

  1. Inequality example: 2ⁿ < n!. The basis may start later than 1 (here n ≥ 4).

Exam angle

PredictionQ1

The basis step for "2ⁿ < n! for n ≥ 4" checks:

Slide 15 / 33

Mathematical Induction

Slide 15: Mathematical Induction
Slide 16 / 33

Mathematical Induction

Slide 16: Mathematical Induction
Slide 17 / 33

Mathematical Induction

Slide 17: Mathematical Induction
Slide 18 / 33

Conjecturing and Proving Correct a Summation Formula

Slide 18: Conjecturing and Proving Correct a Summation Formula

Notes

  1. Conjecture a formula by computing the first few values, then prove it by induction.

Slide 19 / 33

Mathematical Induction Example-p.316

Slide 19: Mathematical Induction Example-p.316
Slide 20 / 33

Proof:

Slide 20: Proof:
Slide 21 / 33

Mathematical Induction Example-p.318

Slide 21: Mathematical Induction Example-p.318
Slide 22 / 33

Mathematical Induction Example-p.318

Slide 22: Mathematical Induction Example-p.318
Slide 23 / 33

Slide 23

Slide 23: Slide 23
Slide 24 / 33

Recursive Definitions & Induction

Slide 24: Recursive Definitions & Induction
Slide 25 / 33

Recursively Defined Functions

Slide 25: Recursively Defined Functions

Exam angle

PredictionQ1

f(0) = 3, f(n + 1) = 2f(n) + 3. f(2) =

Slide 26 / 33

Recursively Defined Functions

Slide 26: Recursively Defined Functions
Slide 27 / 33

Example 2

Slide 27: Example 2
Slide 28 / 33

Example 3

Slide 28: Example 3
Slide 29 / 33

Example 3

Slide 29: Example 3
Slide 30 / 33

Example 4

Slide 30: Example 4
Slide 31 / 33

Example 4

Slide 31: Example 4
Slide 32 / 33

Example 5

Slide 32: Example 5
Slide 33 / 33

Example 5

Slide 33: Example 5