Lecture 16

We did examples of two big techniques from chapter 12:

• unrolling a recursive definition to find a closed form
• using induction to prove the closed form correct

We saw an example where the recursive definition, and thus the inductive proof, used the values from two smaller input values.