Module: Induction and recursion

Inductive definitions, recurrence systems, proof by induction, recursive algorithms, recursion vs. iteration.

Learning Outcomes

Give inductive definitions for sets such as palindromes, unsigned integers, etc.
Prove properties using induction.
Write recursive algorithms to solve problems.

Mathematical induction, strong induction and well ordering, recursive definitions, structural induction, recursive algorithms

Textbook 61 pages

Inductive definitions, strings and languages, recurrence systems.

Lecture notes

Proof by induction, first and second principles of mathematical induction.

Lecture notes

Recursive way of thinking, recursive algorithms, recursion vs. iteration, verification of recursive algorithms.

Lecture notes

Proof by induction (Rosen Section 5.1)

Problems

Proof by induction (Rosen Section 5.1)

Solutions

Proof by strong induction (Rosen Section 5.2)

Problems

Proof by strong induction (Rosen Section 5.2)

Solutions

Proof by induction (Rosen Section 5.3)

Problems

Proof by induction (Rosen Section 5.3)

Solutions

Recursive algorithms (Rosen Section 5.4)

Problems

Recursive algorithms (Rosen Section 5.4)

Solutions