Module: Induction and recursion

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

Learning Outcomes

Use induction and recursion to solve problems.

Readings

Rosen Sections 5.1-5.4

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

Textbook 61 pages

Induction and Recursion, Part 1

Inductive definitions, strings and languages, recurrence systems.

Lecture notes

Induction and Recursion, Part 2

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

Lecture notes

Induction and Recursion, Part 3

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

Lecture notes

Experiential Learning

A11: Homework 11

Homework for sections 5.1 and 5.2

Homework 20 Nov 05:45 PM

A12: Homework 12

Homework for sections 5.3 and 5.4

Homework 04 Dec 05:45 PM

Induction

Proof by induction (Rosen Section 5.1)

Problems

Induction

Proof by induction (Rosen Section 5.1)

Solutions

Strong Induction

Proof by strong induction (Rosen Section 5.2)

Problems

Strong Induction

Proof by strong induction (Rosen Section 5.2)

Solutions

Recursive definitions

Proof by induction (Rosen Section 5.3)

Problems

Recursive definitions

Proof by induction (Rosen Section 5.3)

Solutions

Recursive algorithms

Recursive algorithms (Rosen Section 5.4)

Problems

Recursive algorithms

Recursive algorithms (Rosen Section 5.4)

Solutions