背景：三个熟悉的数学问题

(1) 多项式

大家熟悉的 $f(x) = ax^2 + bx + c$

  • 问题：求方程的解 ($f(x) = 0$)
  • 例子：求 $x^4 + x^2 - 1 = 0$ 的解

$$ x = \pm \sqrt\frac{-1 + \sqrt 5}{2}$$

(2) 数列和递推

大家熟悉的 Fibonacci 数列

  • $f(0) = 0$, $f(1) = 1$
  • $f(n) = f(n-1) + f(n-2)$ ($n \ge 2$)
    • 0, 1, 1, 2, 3, 5, 8, ...

(3) $0.\dot{9}$ 和 $1$ 谁大谁小？

大家熟悉 (但也困扰已久) 的经典问题

  • $0.\dot{9} = 1$ 吗？
    • 看起来，左边总是 “小一点” ($0.\dot{9} < 1$)
    • $0.\dot{1} = \frac{1}{9}$, 所以 $0.\dot{9} = 9 \cdot \frac{1}{9} = 1$
  • 哪里出了问题？

如何定义 “$\ldots$”？

  • $0.\dot{9} = \frac{9}{10} + \frac{9}{100} + \frac{9}{1000} + \frac{9}{10000} + \ldots $
    • 右边是无穷多个数字的和
      • 如果它一定要 “等于” 一个数 $a$，应该是多少呢？

三个问题之间的关联

“无穷多项” 的多项式 = 多项式 + 数列 + 无穷求和

$$ \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} $$

等于号的含义

  • 在某个范围内 (例如 $0 < x < 1$)，等式左右 “要多接近有多接近”

神奇的多项式

$a = [1, 1, 1, \ldots]$ 的多项式

$$ 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 数列？

  • $f(0) = 0$, $f(1) = 1$
  • $f(n) = f(n-1) + f(n-2)$

数列的生成函数

生成函数：函数与数列之间的桥梁

试试 Wolfram Alpha

  • “series x/(1-x-x^2) to order 20”
  • “simplify[x/(1-x-x^2)]”

生成函数：函数与数列之间的桥梁 (cont'd)

用函数 (多项式代数) 表示各种数列

  • $c\cdot F(x)$ → 数列倍增
  • $x\cdot F(x)$ → 数列右移 (补 0)
  • $[F(x) - f(0)] / x$ → 数列左移
  • $F_1(x) \pm F_2(x)$ → 数列求和/差

桥梁：例子

求 Fibonacci 数列的通项公式

  • $f(0) = 0$, $f(1) = 1$
  • $f(n) = f(n-1) + f(n-2)$
  • $F(x) = x/(1-x-x^2)$

求 $f(n, k) = f(n - 1, k) + f(n - 1, k - 1)$ 的通项公式

  • $f(n, 0) = 1$
  • $B_n(x) = \sum_{k\ge 0} f(n,k) x^k$

生成函数：函数与数列之间的桥梁

用函数 (多项式代数) 表示各种数列

  • $F'(x)$ → 数列乘幂次 + 左移
    • 导数: $(c)' = 0$, $(x^n)' = nx^{n-1}$
  • $F_1(x) \cdot F_2(x)$ → 数列卷积

神奇的卷积

试试

$$F(x) \cdot \frac{1}{1-x}$$

例子

  • 求 $1 + 2^2 + 3^2 + 4^2 + \ldots$

函数与数列的桥梁

更多的生成函数

指数生成函数

$$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$ 的推导

Riemann's Zeta Function

$$\zeta(s) = 1 + \frac{1}{2^s} + \frac{1}{3^s} + \ldots\quad(a_i = 1)$$

代数 (数论)

  • $\displaystyle F(s) \cdot G(s) = \sum_{n \ge 1} \sum_{d|n} a_d b_{n/d}$

数学分析

  • $\displaystyle \zeta(2) = 1 + \frac{1}{2^2} + \frac{1}{3^2} + \ldots = \frac{\pi^2}{6}$
  • 3Blue1Brown 的视频

(今天唯一的) 例题

求长度为 $n$ 的 01 字符串中不可分解字符串的个数

  • “不可分解” 指不能写成两个或多个相同字符串的拼接
    • "100100100" == "100" * 3 可分解
    • "1101" 不可分解

一个无关的技巧

  • 多学会一种编程语言，可能有奇效 (brute-force.py)
    • Python: 快速尝试、对拍……的最佳选择
      • Linux 自带

总结

迈向 “高等” 数学的第一步

$$ f(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots $$

多项式

  • $f(x) = ax^2 + bx + c$

数列和递推

  • $f(0) = 0$, $f(1) = 1$, $f(n) = f(n-1) + f(n-2)$ ($n \ge 2$)

无限循环小数

  • $0.\dot{9} = \frac{9}{10} + \frac{9}{100} + \frac{9}{1000} + \frac{9}{10000} + \ldots = {?}$

数学 $\ne$ 做数学题

数学的本质——探索和发现

“表达”、“抽象”、“建立联系”

延伸阅读

Concrete Mathematics《具体数学》

Generatingfunctionology (by Herbert S. Wilf)

  • 足够满足 OI/MO 的所有生成函数技巧

Burn Math Class (by Jason Wilkes) 《烧掉数学书》

  • 适合中学生的第一本数学分析 (但有点难，需要老师教)
  • 书评：“首先需要警惕的是把学生训练成做题机器的数学辅导书”、“还有一类需要警惕的书是用严格性折磨学生的大学数学课本”

End.