大家熟悉的 $f(x) = ax^2 + bx + c$
$$ x = \pm \sqrt\frac{-1 + \sqrt 5}{2}$$
大家熟悉的 Fibonacci 数列
大家熟悉 (但也困扰已久) 的经典问题
如何定义 “$\ldots$”?
“无穷多项” 的多项式 = 多项式 + 数列 + 无穷求和
$$ \begin{align} f(x) & = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots \\ & = \sum_{ i \ge 0} a_i x^i \end{align} $$
等于号的含义
$$ F(x) = 1 + x + x^2 + x^3 + \ldots = {?}$$
例子
$$F(1/2) = 1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} \ldots $$
例子:等比数列求和公式
$$\frac{a_0}{1-q}(1-q^n)$$
$$\frac{1}{1-x} = 1 + x + x^2 + x^3 + \ldots\qquad(|x| < 1)$$
$$a = [1, 1, 1, 1, \ldots]$$
$$\sin(x) = x - \frac{1}{3!}x^3 + \frac{1}{5!}x^5 - \frac{1}{7!}x^7 + \ldots\quad(x\in\mathbb R)$$
$$a = [0, 1, 0, -\frac{1}{6}, 0, \frac{1}{120}, 0, -\frac{1}{40320}, \ldots]$$
$$F(x) = x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + \ldots = {?}$$
什么样的 $F(x)$ 生成了 Fibonacci 数列?
用函数 (多项式代数) 表示各种数列
求 Fibonacci 数列的通项公式
求 $f(n, k) = f(n - 1, k) + f(n - 1, k - 1)$ 的通项公式
用函数 (多项式代数) 表示各种数列
试试
$$F(x) \cdot \frac{1}{1-x}$$
例子
指数生成函数
$$F(x) = a_0 + a_1 x + a_2 \frac{x^2}{2!} + a_3 \frac{x^3}{3!} + \ldots$$
Dirichlet 级数生成函数
$$F(s) = a_1 + \frac{a_2}{2^s} + \frac{a_3}{3^s} + \frac{a_3}{3^s} + \ldots$$
练习:$F \cdot G$ 的推导
$$\zeta(s) = 1 + \frac{1}{2^s} + \frac{1}{3^s} + \ldots\quad(a_i = 1)$$
代数 (数论)
数学分析
求长度为 $n$ 的 01 字符串中不可分解字符串的个数
"100100100" == "100" * 3
可分解"1101"
不可分解一个无关的技巧
$$ f(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots $$
多项式
数列和递推
无限循环小数
数学的本质——探索和发现
“表达”、“抽象”、“建立联系”
Concrete Mathematics《具体数学》
Generatingfunctionology (by Herbert S. Wilf)
Burn Math Class (by Jason Wilkes) 《烧掉数学书》