Discrete Math III: Recursive Thinking (8 Week)

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
Definitions and Examples/The Fibonacci Sequence/Modeling with Recurrence Relations/Modeling with Recurrence Relations

Week 2: Closed-Form Solutions and Induction
Guessing a Closed-Form Solution/Polynomial Sequences: Using Differences

Week 3: Closed-Form Solutions and Induction/Recursive Definitions
Inductively Verifying a Solution/Recursive Definitions: Definitions and Examples

Week 4: Recursive Definitions
Writing Recursive Definitions/Recursive Geometry/Recursive Jokes

Week 5: Proof by Induction
The Principle of Induction/Examples

Week 6: Proof by Induction
Strong Induction/Structural Induction

Week 7: Recursive Data Structures
Lists/Efficiency/Binary Search Trees Revisited

Week 8: Review
Review of all topics