CS 173: Skills list for Examlet 4

• Summations and products
  • Read summation and product notation
  • Extract the first or last term in a sum or product.
  • Move values outside the sum/product when they don't depend on the index variable.
  • Divide complex products/sums when the inside part is a sum/product.
  • Rewrite a sum or product to use a different index variable, perhaps starting at a different value.
  • Know the closed form for the sum of the first n integers.
  • Know the closed form for a geometric series, especially two special cases: sum of (1/2)^k and sum of 2^k.
• 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.
• 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.
  • Know the definition of the k-dimensional hypercube graph, its shorthand name Q_k, 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.
  • Use induction to prove (fairly simple) properties for objects such as graphs and strings.