Discrete Math Part III: Recursive Thinking

Course Description
Topics include Recursive Relations: Definitions, The Fibonacci Sequence, and Modeling with Recurrence Relations; Closed-Form Solutions and Induction: Polynomial Sequences, Recursive Definitions and Geometry, Proof By Induction, Weak and Strong Induction, Structural Induction, Recursive Data Structures, Lists, Efficiency, and a return to Minary Search Trees.

Prerequisites
The class is taught with the assumption that the student has a strong understanding of Algebra, Discrete Logic, and Relational Thinking.

Calculator
Although this is a Mathematics course, a calculator will be of little to no use for the topics and problems we will discuss.

Purpose
Discrete Mathematics is designed for prospective math/computer science majors as well as for students whose primary interest is engineering or the physical and social sciences.

Discrete Mathematics Part III
Course Schedule
Class meets twice weekly

Week 1: Recursive Relations/Closed-Form Solutions and Induction
Lesson 1: Definitions and Examples/The Fibonacci Sequence/Modeling with Recurrence Relations/Modeling with Recurrence Relations
Lesson 2: Guessing a Closed-Form Solution/Polynomial Sequences: Using Differences

Week 2: Closed-Form Solutions and Induction/Recursive Definitions
Lesson 1: Inductively Verifying a Solution/Recursive Definitions: Definitions and Examples
Lesson 2: Writing Recursive Definitions/Recursive Geometry/Recursive Jokes

Week 3: Proof by Induction
Lesson 1: The Principle of Induction/Examples
Lesson 2: Strong Induction/Structural Induction

Week 4: Recursive Data Structures
Lesson 1: Lists/Efficiency/Binary Search Trees Revisited
Lesson 2: Exam