{%hackmd @YuRen-tw/article-theme %}

# 形式冪級數

> :::spoiler 目錄
> [TOC]
> :::

## 形式冪級數
### 基本定義

<div class="definition" data-info="形式冪級數">

交換環 $R$ 上的形式冪級數（formal power series）就是 $R$ 上的無窮序列 $A = (a_0, a_1, \dotsc)$。
我們形式上將它寫成
\\[ A(x) = \sum_{k\ge 0} a_k x^k \\]
其中 $a_k$ 稱為係數（coefficients），而 $x^k$ 為不定元（indeterminate） $x$ 的形式冪。
</div>

> 要注意這個寫法只是「形式」上寫成冪級數，我們只不過是把序列類比成冪級數的形式來操作，但並不在乎這個級數是否收斂。

對於形式冪級數 $A(x) = \sum_k a_k x^k$，我們稱 $a_0$ 為 $A(x)$ 的常數項。
如果有整數 $m$ 使得對於 $k > m$ 都有 $a_k = 0$，則 $A(x)$ 就稱為多項式（polynomial）。

<div class="definition" data-info="加法與乘法">

交換環 $R$ 上的所有形式冪級數構成另一個交換環，記為 $R[[x]]$，並配備有下列加法與乘法運算：
- $(\sum_k a_k x^k) + (\sum_k b_k x^k) := \sum_k (a_k + b_k) x^k$,
- $(\sum_k a_k x^k) \cdot (\sum_k b_k x^k) := \sum_k (\sum_{j=0}^k a_j b_{k-j}) x^k$,

後面的乘法有時被稱為柯西乘積（Cauchy product）或離散捲積（discrete convolution）。
</div>

<div class="definition" data-info="合成">

對於形式冪級數 $A(x) = \sum_k a_k x^k$ 與 $B(x) = \sum_k b_k x^k$，它們的合成 $A(B(x))$ 或 $(A \circ B)(x)$ 定義為
\\[
A(B(x)) := \sum_{k\ge 0} a_k(B(x))^k.
\\]
當 $b_0 = 0$ 或 $A(x)$ 是多項式時，這個合成是定義良好的。
</div>

<div class="definition" data-info="係數提取算子">

令 $[x^n]$ 為係數提取算子（coefficient extraction operator）並定義為
\\[
[x^n] \Bigl( \sum_{k\ge 0} a_k x^k \Bigr)
:= a_n.
\\]
</div>

### 合成有結合律

> 這整段都是為了證明結合律……

> 下面的符號定義不是常見的寫法，是這篇筆記為了推論方便而自創的。

<div class="definition">

對於形式冪級數 $A(x) = \sum_n a_n x^n$，我們令
\\[
A^m_k := [x^k](A(x))^m,
\\]
也就是說 $A^m_k = \sum_{n_1 + \dotsb + n_m = k} \prod_{i=1}^m a_{n_i}$。
</div>

按照乘法的定義，我們有 $(A \cdot B)^1_n = \textstyle\sum_k A^1_k B^1_{n-k}$。
而由於 $R[[x]]$ 是一個交換環，我們進一步有
\begin{align*}
(A \cdot B)^m_n &= \textstyle\sum_k A^m_k B^m_{n-k},\\
A^{m_1 + m_2}_n &= \textstyle\sum_k A^{m_1}_k A^{m_2}_{n-k}.
\end{align*}

另一方面根據合成的定義，我們有 $(A \circ B)^1_n = \textstyle\sum_k A^1_k B^k_n$。
更進一步，我們有以下的定理：

<div class="theorem">

對於形式冪級數 $A(x) = \sum_k a_k x^k$ 與 $B(x) = \sum_k b_k x^k$，我們有
\\[
(A \circ B)^m_n = \textstyle\sum_k A^m_k B^k_n.
\\]
</div>
<div class="proof">

在 $m$ 上做歸納法：
\begin{align*}
&(A \circ B)^{m+1}_n\\
&= \bigl((A \circ B)^m \cdot (A \circ B)\bigr)^1_n\\
&= \textstyle\sum_\ell (A \circ B)^m_\ell (A \circ B)^1_{n-\ell}\\
&= \textstyle\sum_\ell \bigl(\sum_i A^m_i B^i_\ell \bigr) \bigl(\sum_j A^1_j B^j_{n-\ell} \bigr)\\
&= \textstyle\sum_\ell\sum_i\sum_j A^m_i A^1_j B^i_\ell B^j_{n-\ell}\\
&= \textstyle\sum_i\sum_j A^m_i A^1_j \bigl(\sum_\ell B^i_\ell B^j_{n-\ell} \bigr)\\
&= \textstyle\sum_i\sum_j A^m_i A^1_j B^{i+j}_n\\
&= \textstyle\sum_k \bigl(\sum_{i+j=k} A^m_i A^1_j \bigr) B^k_n\\
&= \textstyle\sum_k A^{m+1}_k B^k_n.
\end{align*}
</div>

<div class="theorem corollary">

形式冪級數的合成運算有結合律。
</div>
<div class="proof">

令 $A(x)$, $B(x)$, $C(x)$ 為形式冪級數。
則我們有
\begin{align*}
((A \circ B) \circ C)^m_k
&= \textstyle\sum_i (A \circ B)^m_i C^i_k\\
&= \textstyle\sum_i \sum_j A^m_j B^j_i C^i_k\\
&= \textstyle\sum_j A^m_j (B \circ C)^j_k\\
&= (A \circ (B \circ C))^m_k.\\
\end{align*}
特別地，有 $((A \circ B) \circ C)^1_k = (A \circ (B \circ C))^1_k$。
於是比較係數後可得 $(A \circ B) \circ C = A \circ (B \circ C)$。
</div>

> ---
> *Work In Progress*...
>
> ---