4. Recurrence relations and generating functions
The way begets one; one begets two; two begets three; three begets the myriad creatures.
Lao Tse, Tao Te Ching (ca. 500 BC)
TOPICS: Fibonacci, Catalan and Bell numbers, derangements, [finite fields, sorting, binary trees, ‘Twenty Questions’]
TECHNIQUES: Recurrence relations, solution of linear recurrence relations with constant coefficients, generating functions and their manipulation, [the ring of formal power series]
ALGORITHMS: Computation of Fibonacci numbers, [QUICKSORT]
A recurrence relation expresses the value of a function ...