Recurrences and generating functions

Builds on

Required prerequisites, all the way down: 28

You will learn to

• Solve linear recurrences with constant coefficients using characteristic polynomials.
• Use generating functions to solve recurrences and counting problems.
• Compare growth rates using O, Ω and Θ notation.

Definition

• The ordinary generating function of a sequence (aₙ) is the formal power series Σ aₙxⁿ.
• f(n) = O(g(n)) means |f(n)| ≤ C|g(n)| for some constant C and all sufficiently large n.

Theorem

• Binet's formula: with F₀ = 0 and F₁ = 1, Fₙ = (φⁿ − ψⁿ)/√5 where φ = (1 + √5)/2 and ψ = (1 − √5)/2.
• The Catalan numbers C(2n, n)/(n + 1) count, among many other things, balanced sequences of n pairs of brackets.

Common misconceptions

• Thinking formal power series must converge to be useful.
• Reading big-O as an exact count rather than an upper bound up to a constant.

Leads to

Optional discoveries

• Algorithms, correctness and efficiency Recurrences describe the running time of recursive algorithms; mergesort satisfies T(n) = 2T(n/2) + O(n), so T(n) = O(n log n).

Further reading

• Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics (1989)
• Herbert S. Wilf, generatingfunctionology (1990)