Recurrences and generating functions

前置知识

28 项必需的前置知识（一直追溯到底）

你将学会

• 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.

定义

• 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.

定理

• 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.

常见误解

• 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.

通向

可选发现

• 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).

延伸阅读

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