CS 173: Skills list for "Examlet D"

• Summations
  • Know how to read summation notation, i.e. convert between it and a list of terms with ellipsis (...). Same for product notation.
  • Extract the first or last term in a sum or product.
  • Rewrite a sum or product so that its index variable starts at a different number.
  • Know how to adjust a closed form for changes in the start/end index values.
• (Easy) Induction
  • Given a claim, identify/state the key parts of an inductive proof: the induction variable, the claim P(n), base case, inductive step, inductive hypothesis, conclusion of the inductive step.
  • Be able to state a (strong) inductive hypothesis. (We always use and require strong hypotheses in this class, but some of you may have used weak hypotheses in other classes.)
  • Use induction to prove a formula (equality or inequality) is correct for all integers starting at some base case.
  • Use induction to prove that a non-formula claim (e.g. a divisibility relation) holds for all integers starting at some base case.
  • Any proofs for this first half of the examlet will have very simple structure. In particular, the truth of the claim at n=k depends only on the claim being true at n=k-1, with only one base case required​

• 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 requires both a base case (or cases) and a recursive step/formula.
  • Define the Fibonacci numbers.
• ​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.​​​​