Untitled

定义

$A(x) = \sum_{n \ge 0} a_n x^n$

• 这是一个 generating function 生成函数
• 我们称 x 是变量 variable 或者 indeterminate
• 如果要获得 x 的值，我们需要用序列 $a_n = ( 0, 1, 0,\cdots )$ 来进行获得
• 我们也可以写作 $[x^n]A(x) = a_n$

性质

对于形式幂级数 $A(x) = \sum_{n\ge 0}a_n x^n$, $B(x) = \sum_{n\ge 0}b_n x^n$m $C(x) = \sum_{n\ge 0}c_n x^n$

1. 等价 equality: $A(x) = B(x) \Leftrightarrow a_n = b_n$
2. 加法 addition: $A(x) + B(x) = \sum_{n\ge 0}(a_n + b_n)x^n$
   1. 交换律 $A(x) + B(x) = B(x) + A(x)$
   2. 结合律 $(A(x) + B(x)) + C(x) = A(x) + (B(x) + C(x))$
   3. 零元 $A(x) + 0 = A(x)$
   4. 相反元 $A(x) + (-A(x)) = 0$
3. 乘法 multiplication: $A(x)B(x) = \sum_{n\ge 0}(\sum_{k=0}^n a_k b_{n-k})x^n$
4. 交换律 $A(x)B(x) = B(x)A(x)$
5. 结合律 $(A(x)B(x))C(x) = A(x)(B(x)C(x))$
6. 单位元 $A(x)1 = A(x)$, $1 = a + 0x + 0x^2 \cdots$
7. 分配律 $A(x)(B(x) + C(x)) = A(x)B(x) + A(x)C(x)$
   整体来说，形式幂级数是一个交换环
8. 可逆性 invertibility: 如果 $A(x)B(x) = 1$, 那么 我们说 A 是 invertible, 其中$B(x)$ 并不需要是形式幂级数，只是一个函数
   写法: $B(x) = A(x)^{-1} = \frac{1}{A(x)}$

可逆性定理

一个形式幂级数可以当且仅当$a_0 \not= 0$

证明

首先我们从 $a_0 b_0 = 1$ 得出：

$b_0 = \frac{1}{a_0}$

然后求递推公式​

$b_n = -\frac{1}{a_0}\sum_{k=1}^n a_k b_{n-k}$

复合运算符 Composition

对于形式幂级数 $A(x) = \sum_{n\ge 0}a_n x^n$ 和 $B(x) = \sum_{n\ge 0}b_n x^n$, $a_0= 0$, 我们定义复合运算符为：

$(B\circ A)(x) = B(A(x)) = \sum_{n\ge 0}b_n A(x)^n$

形式幂级数求导 formal derivative

令 $A(x) = \sum_{n\ge 0} a_n x^n$ 是一个形式幂级数，那么我们称

$DA(x) = \sum_{n \ge 0} na_nx^{n-1} = \sum_{n\ge 0}(n+1)a_{n+1}x^n$

求导性质

1. homogeneous: $D(\alpha A(x) + \beta B(x)) = \alpha DA(x) + \beta DB(x)$
2. product rule: $D(A(x)B(x)) = DA(x)B(x) + A(x)DB(x)$
3. composition rule: $D(B(A(x))) = DB(A(x))DA(x)$
4. inverse rule: $D(A(x)^{-1}) = -A(x)^{-2}DA(x)$ 要求 $a_0\not =0$