CS202: Discrete Structures

4.5: Mathematical Induction

• Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Induction I" URL

  You have encountered mathematical induction in some of the previous readings in this course. Read Sections 1 and 2 on pages 1 - 4. As you read about induction in the references, note that induction has a relationship to recursion. Then, read Section 3 and Section 4 on pages 5 - 7.

• Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Induction III" URL

  Read Section 2 on pages 2 - 5 and Section 4 on pages 8 - 12. These readings give helpful guidance in correct use of induction.

• University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Induction, Sequences, and Series" URL

  Study the applications of induction in Section 1 on pages IS-1 through IS-8. Then, read Section 1, example 2 on page IS-2. Finally, read Theorem 2 on pages 5 - 7, example 11 on page 22, and example 12 on page 23. Some of the examples are more difficult, but hard examples push our understanding and expand our skill. Afterwards, read example 4 on pages 3 and 4.

  This reading is a good formal review. Again, the presentation relies on a lot of examples. Don't forget to look over the exercises at the end of the section. Some of these examples will be utilized in following subunits.