5. Induction and Recursion

In this chapter we will explore one last proof technique. This proof technique is the most important proof technique of this course. Unfortunately, it is also the hardest to understand. Be patient with yourself as you learn about induction. You will need to do lots of practice to really internalize the ideas of induction. Induction will be required a million times over throughout your education and careers in computer science.

As we will see in Section 5.2 and Section 5.3, there are many applications of induction in computer science. Recursive algorithms, data structures, and loop invariants are just some applications that we will see in this chapter.

• 5.1. Induction
  • 5.1.1. Mathematical Induction
    • Why does induction work?
    • More Induction Examples
    • An Induction Cheatsheet
  • 5.1.2. Strong Induction
  • 5.1.3. Well-Ordering Principle
  • 5.1.4. Exercises
• 5.2. Recursion
  • 5.2.1. Recursive Definitions
  • 5.2.2. Recursive Functions and Algorithms
  • 5.2.3. Proving Recursive Algorithms
  • 5.2.4. Exercises
• 5.3. Computer Program Verification