# CS 173, Fall 2014: Skills list for eighth examlet

The proof for this examlet will be long. Therefore, you should expect a correspondingly smaller amount of short-answer material.

• Recursive definition
• Understand how to read a recursive definition, e.g. compute selected values or objects produced by that definition.
• Know that a recursive definition, and an inductive proof, require a both a base case and an inductive step/formula.
• Define the Fibonacci numbers.
• Know the definition of the k-dimensional hypercube graph, its shorthand name Qk, and how many vertices it contains.
• Unrolling
• Given a recursively defined function, find its closed form by "unrolling". Test questions will involve either doing certain key steps or a very simple example, not an entire long messy unrolling.
• Induction
• Write inductive proofs that need to use the truth of the claim for more than one immediately previous value, e.g. multiple previous values, a previous value several steps back.
• Determine whether an inductive proof requires more than one base case and, if so, which ones.
• Use induction to prove facts about a recursively defined function, e.g. that it has some specific closed form.
• For recursively defined sets of objects (e.g. graphs), use induction to prove that they have some specific property (e.g. number of edges) and/or write a recurrence for the values of some property of the objects (e.g. number of edges).