Formalizing Recursion and Induction

This week is devoted to formalizing our work. We will use rigorous formulae to develop computer program to generate and analyze the triangle, formally define the notion of recursion, and its counterpart, the Principle of Mathematical induction

• Recursion. Explore what it means to be a "recursive definition". Review recursive definition for Pascal's triangle. Discuss other examples of recursive definitions (Fibonacci sequence, etc.)

• Writing computer programs for generating the triangle: Algorithms:
  • Without memory storage: recursive/functional algorithm.
  • With memory storage.

• Programming the graphing calculator to plot remainders in two colors (black for non-zero, white for 0) mod 2, mod 3, mod 4, mod 5, mod 6, mod 7, mod 8, mod 9, mod 25

• Define induction, give inductive proofs of algebraic formulae in the triangle. Practice inductive proofs for homework. (Sum of the numbers 1,2,..n; 1²,2²,...,n², etc.)