Program, Semester Week 6

Induction

This week will cover the topic of induction, a method of proof that relies on recursive definitions. This is a tool that will explore the truth value for all natural numbers \(n\) of propositions where \(n\) is included as a parameter. For example, identities like \(\sum_{i=1}^n i = \frac{n(n+1)}{2}\) can be shown to be true for all \(n \in \mathbb{N}\) using induction. At its core, induction is a technique to verify whether a proposed expression or description of some behaviour indeed is valid.

Key Terms

The induction principle and proof by induction. Base case and induction step. The induction hypothesis.

Preparation and Syllabus

This week will cover Sections 5.4 and 5.5 from Chapter [05 - Recursion and induction].

Exercises

Exercises for Long Day.

Short Day is dedicated to Theme Exercise 2.