本科低年级Discrete Mathematics计划中

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

本主题的课程尚未编写。下面的提纲是课程地图的一部分，尚未经过审校。

前置知识

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.

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