Some thoughts on CLRS's treatment on recurrence relation

As you may observed, I have been stuck in Chapter 4 for quite a while.  Notably on Section 4.3 and 4.4.  There are exercises which I don't fully grok.  That obviously makes me think of why.  This usually gives me some insight.

When you take a look of teaching material on recurrence relations,   most of the honest text will tell you that solving general recurrence relationship is in essence a guess job.   This is where the substitution method shines.

Of course we all know that there are useful exceptions.  There is the divide-and-conquer type.  That is when you have the situation where there is a term T(n/a).   Basically, tree method, the master method shine.

Now of course, if you talk about Math, many interesting things could happen.  So for example, just on the divide-and-conquer type of recurrence - so what if we have a linear combination of the term T(n/a)?  This is where master method will not work and you need to retreat back to tree method.

If you are looking for a standard method,  then you have to use Akra-Bassi method which states the general solution of  T(n) =  Sum T(n/a_i) + f(n) .  This is the stated in the bibliographical references but not covered in CLRS.

Now how about another important class where.   T(n) = Sum T(n-a_i)?  This is usually known as linear recurrence relation (ref: the famous "Discrete Mathematics and Applications").  In that case, one needs to introduce powerful method such as generating function to solve this kind of question.  Again, this is not something which is not covered in CLRS.

So here you have it, CLRS basically hadn't covered many standard techniques in solving recurrence relation.  But its exercises are a bit unforgiving because it has question such as 4.3-6 which require solving recurrence such as T(n) = T(n/2+17) + n or 4.4.5 which requires solving T(n) = T(n/2) + T(n-1) + n.  In a ways, both of them are kinds of recurrence relation which are both linear and divide-and-conquer.  The goal is to train the reader to learn "how to guess?".

That is perhaps why some of these problems are not easy. 4.3-6, for example, takes some space to explain if you try to solve it using substitution method.

In a way, CLRS's treatement on recurrence is both too simple and too difficult.  I don't blame the authors.  In my opinion. its real strength, especially in 3rd edition, is that it motivates the reader how to think of recurrence relation and how they occur.   Concrete Mathematics reads similarly but it would take 7 chapters before the readers can reach the point of learning how to solve recurrence using generating function.  So as an introductory text, CLRS is doing a fairly good job.

But for readers who are looking for an encyclopedic text, do bear in mind that, CLRS needs to be supplemented by other books.  If you want to understand the "full" story, you still need to read TAOCP and CMath.

Ah learning, learning.