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.
- 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.
- 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).