I find it somewhat strange that generating functions are introduced significantly before recurrences are (and that recurrences are introduced last!). Does anyone know why the authors did that?
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.
I would guess that it's something like SICP introducing assignment halfway through the book, dramatic, unexpected, and you've been using a weaker version for many chapters now. (Chapter 6 is about recursive data types, and comes immediately after chapter 5's induction to give some perspective.) But it might also be because, as an introductory mathematics course, it wants to stay a good distance away from algorithms and messy concepts like big-O notation.
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:
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.