Week 5

Main topic of week 5: closed form of recursive function and induction definition.

We further navigated some example on how to get the closed form of a function. Here is the idea:

1. Make a general conjecture of a closed form format

2. Build a linear equation based on the closed form.

3. Solve the equation by using different n values.

Then we talked about the definition of recursive set, for example, a binary tree can be defined recursively. In this sense, the most powerful tool to prove the correctness based on a recursive defined set would be induction, because they have very similarly structure.