D.7: Recurrence, Recursion and Induction

From

Revision as of 23:26, 31 July 2010

Discrete Math Learning modules

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.