D.7: Recurrence, Recursion and Induction
From
Oregon Department of Education knowledge and skills for Recurrence, Recursion, Induction
D.7 Recurrence, Recursion and Induction: Understand and apply recurrence, recursive, and inductive methods to solve problems.
D.7.1 Use recursive and iterative thinking to solve problems such as population growth and decline, exponential functions, problems involving sequential change and compound interest.
D.7.2 Use finite differences to solve problems and to find explicit formulas for recurrence relations.
D.7.3 Use mathematical induction to prove recurrence relations and concepts in number theory such as sums of infinite integer series, divisibility statements, and parity statements.
D.7.4 Use mathematical induction to analyze the validity of an iterative algorithm.
D.7.5 Describe arithmetic and geometric sequences recursively.
D.7.6 Use understanding of relationship of finite and infinite geometric series, including how the concept of limits connects them.
D.7.7 Apply recurrence or recursion to the design and understanding of sorting and searching algorithms.
D.7.8 Analyze algorithms for efficiency, including how the number of steps grows as a function of the size of the problem.
D.7.9 Compare the efficiency of iterative and recursive solutions of a problem.
Discrete Math Learning modules
Recurrence & Recursion overview (from Terrel Smith's class, MS-Powerpoint slide set)
Sequences & Mathematical Induction overview (from Terrel Smith's class, MS-Powerpoint slide set)
Recursion-Iteration Java exercises (from Don Kirkwood's class)
Linear Homogeneous Recurrence Relations and their solutions (ppt lesson)
Resources for Recurrence, Recursion, and Induction
