[spicyj]

Recurrences are partially covered in chapters:

  13 (Sums and Asymptotics)
  15 (Generating Functions, as you mentioned)
  19 (Random Processes)
  20 (Recurrences)

and though they're not explicitly named as such in Chapter 5 (Induction), several of the problems in the chapter make use of them.

It seems to me that the first half of the chapter on recurrences covers recurrences more from a CS viewpoint such as the recurrence they list for mergesort:

  T(n) = 2 T(n/2) + n - 1

which is arguably less fundamental than the study of linear recurrences which come up more often in math. The second half of the chapter covers techniques for solving general recurrences, both for general linear recurrences and general divide-and-conquer recurrences using the Akra-Bazzi theorem (which is an extension of the Master Theorem).

Thus, perhaps the chapter "Recurrences" is misnamed – the authors certainly cover elementary recurrences in the earlier chapters and leave more complex topics recurrences (such as how to solve them in general) for the end because they are less important than most of the other topics in the book.