Algorithms: Recurrence relations from CLRS

Answer 1

The funny leap-of-faith step is a shortcut for mathematical induction. Basically, it goes like so:

• Check that the assumption is true for some base case (e.g. only one non-leaf node).
• Given that it is true for the nth non-base case, make sure it is true for the n+1st non-base case.

You can usually shortcut this by just assuming that what you want to prove is true, plugging it in, and showing that it works. Whether this is the case in this particular instance, I can't quite tell.

There is often a bit of inspiration involved in solving these sorts of problems, since you have to pick out the right form for the recurrence in order to get the induction step to work, but it's not usually picking things out of thin air; in this case, it's picking things out of very thick air that arises from careful examination of the relationship between the leaf nodes and the others.