Early undergraduateDiscrete MathematicsPlanned
Recurrences and generating functions
Recurrence relations such as the Fibonacci recurrence, solving linear recurrences, ordinary generating functions and asymptotic notation.
math.discrete.recurrences-generating-functions
The lesson for this topic has not been written yet. The outline below is part of the curriculum map and has not been reviewed.
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)