Concrete Mathematics

The chapter on generating functions is the reason to read this.

Before it, a recurrence was a thing I solved by guessing a closed form and confirming by induction, a procedure that works but teaches nothing. After it, a recurrence is a statement about a formal power series, and solving it is algebra.

The shift is that you stop treating the sequence $a_0, a_1, a_2, \dots$ as the object and start treating

$A(z) = \sum_{n \ge 0} a_n z^n$

as the object. A recurrence relating $a_n$ to $a_{n-1}$ becomes an equation relating $A(z)$ to $zA(z)$, and equations you can solve.

The margin notes are also genuinely funny, which no other book at this level manages.