Hints, Tips, and FAQ
====================

General:
--------
Q: Do we have to use induction?
A: You should solve the problems using ideas taught in this course, so 
   yes, you should be using induction.

Q: Do we have to do all the picky little things like on assignment 1?
A: No, that was a one time deal. But we do still expect that it should be
   clear what you're trying to prove, and we do expect full, well-written,
   formal proofs.

Problem 1:
----------
Hint: Keep in mind that induction doesn't work well with two variables. Try
   inducting on m or n, but not both at once.

Problem 3:
----------
a) Hint: If we are in the inductive step and trying to prove the case for 
      n+1, the naive approach would be to take 
      a_1/b_1 + a_2/b_2 + ... + a_n/b_n + a_(n+1)/b_(n+1) and apply the
      induction hypothesis to a_1/b_1 + a_2/b_2 + ... + a_n/b_n. This, 
      unfortunately, doesn't work since b_1, ..., b_n is not necessarily
      a permutation of a_1, ..., a_n.

      Play with the sequence to get something you can apply the induction
      hypothesis to. You may find it helpful to make some assumptions 
      (there are a number of things we can assume without loss of 
      generality), 

Problem 5:
----------
Q: Induction is on the natural numbers, so what do we do with a height of -1?
A: Two ways to think about this one. You can either treat the empty tree
   as a special case and use induction to prove the rest, or you can
   use a predicate P(n) that is a statement about a tree of height n-1.