CS285 · Chapter 5 · Annotated SlidesInduction and Recursion (Handout)
Original
Overview

Induction and Recursion (Handout)

Worked handout: the ladder and domino intuition, the basis step and inductive step, solved induction proofs for sums, divisibility and inequalities, 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 34 slides
  1. 1 Mathematical Induction 5.1 & 5.3
  2. 2 1. We can reach the first rung of the ladder. 2. If we can reach a particular rung of the ladder, then we can reach the next rung.
  3. 3 Principle of Mathematical Induction: To prove that P(n) is true for all positive integers n, where P(n) is a propositional function,
  4. 4 Induction Works - Domino Effect
  5. 5 Slide 5
  6. 6 Slide 6
  7. 7 Mathematical Induction
  8. 8 Slide 8
  9. 9 Slide 9
  10. 10 Slide 10
  11. 11 Slide 11
  12. 12 Slide 12
  13. 13 Slide 13
  14. 14 Slide 14
  15. 15 Slide 15
  16. 16 Slide 16
  17. 17 Slide 17
  18. 18 Slide 18
  19. 19 Slide 19
  20. 20 k k
  21. 21 Slide 21
  22. 22 Slide 22
  23. 23 Slide 23
  24. 24 Slide 24
  25. 25 Slide 25
  26. 26 Recursively Defined Functions
  27. 27 Slide 27
  28. 28 Slide 28
  29. 29 Slide 29
  30. 30 Slide 30
  31. 31 Slide 31
  32. 32 Example 4
  33. 33 Example 5
  34. 34 Slide 34
Slide 1 / 34

Mathematical Induction 5.1 & 5.3

Slide 1: Mathematical Induction 5.1 & 5.3
Slide 2 / 34

1. We can reach the first rung of the ladder. 2. If we can reach a particular rung of the ladder, then we can reach the next rung.

Slide 2: 1. We can reach the first rung of the ladder. 2. If we can reach a particular rung of the ladder, then we can reach the next rung.
Slide 3 / 34

Principle of Mathematical Induction: To prove that P(n) is true for all positive integers n, where P(n) is a propositional function,

Slide 3: Principle of Mathematical Induction: To prove that P(n) is true for all positive integers n, where P(n) is a propositional function,
Slide 4 / 34

Induction Works - Domino Effect

Slide 4: Induction Works - Domino Effect

Notes

  1. Dominoes: first falls + each one knocks the next ⇒ all fall.

Slide 5 / 34

Slide 5

Slide 5: Slide 5
Slide 6 / 34

Slide 6

Slide 6: Slide 6
Slide 7 / 34

Mathematical Induction

Slide 7: Mathematical Induction

Notes

  1. Basis step: prove P(1) (or the first value). Inductive step: assume P(k) (the inductive hypothesis) and prove P(k + 1).

  2. Trap In the inductive step you must USE P(k); just proving P(k + 1) from scratch is not induction.

Slide 8 / 34

Slide 8

Slide 8: Slide 8
Slide 9 / 34

Slide 9

Slide 9: Slide 9
Slide 10 / 34

Slide 10

Slide 10: Slide 10
Slide 11 / 34

Slide 11

Slide 11: Slide 11
Slide 12 / 34

Slide 12

Slide 12: Slide 12
Slide 13 / 34

Slide 13

Slide 13: Slide 13
Slide 14 / 34

Slide 14

Slide 14: Slide 14
Slide 15 / 34

Slide 15

Slide 15: Slide 15
Slide 16 / 34

Slide 16

Slide 16: Slide 16
Slide 17 / 34

Slide 17

Slide 17: Slide 17
Slide 18 / 34

Slide 18

Slide 18: Slide 18
Slide 19 / 34

Slide 19

Slide 19: Slide 19
Slide 20 / 34

k k

Slide 20: k k
Slide 21 / 34

Slide 21

Slide 21: Slide 21
Slide 22 / 34

Slide 22

Slide 22: Slide 22
Slide 23 / 34

Slide 23

Slide 23: Slide 23
Slide 24 / 34

Slide 24

Slide 24: Slide 24
Slide 25 / 34

Slide 25

Slide 25: Slide 25
Slide 26 / 34

Recursively Defined Functions

Slide 26: Recursively Defined Functions
Slide 27 / 34

Slide 27

Slide 27: Slide 27
Slide 28 / 34

Slide 28

Slide 28: Slide 28
Slide 29 / 34

Slide 29

Slide 29: Slide 29
Slide 30 / 34

Slide 30

Slide 30: Slide 30
Slide 31 / 34

Slide 31

Slide 31: Slide 31
Slide 32 / 34

Example 4

Slide 32: Example 4
Slide 33 / 34

Example 5

Slide 33: Example 5
Slide 34 / 34

Slide 34

Slide 34: Slide 34