基础代数（一）代数的起源

科斯特利金的代数学书写的挺不错的
有一些现代的问题也值得研究

数学归纳法原理

从美国数学月刊的一个征解问题说起
美国数学月刊, $1977, \text{V.84, No.6}$
给定圆周上任意 $n$ 个点, 确定 $n \choose 2$条弦
划分圆内的区域数 $R_n$, 任意三条弦在圆内不相交

$$\begin{gathered} R_n = 1+\left(\begin{gathered} n \\ 2 \end{gathered}\right)+\left(\begin{gathered} n \\ 4 \end{gathered}\right) \end{gathered}$$

根据数学归纳法, $n = 1$ 显然成立, 如果 $n = k$ 时成立, 那么只要证明

$$\begin{gathered} R_{n+1}-R_{n}=n+\left(\begin{gathered} n \\ 3 \end{gathered}\right) \end{gathered}$$

而这个式子是成立的, 证明如下
$\textbf{i)}$ 加入的新点 $q$, 与 原来 $\forall n$ 构成弦
这个弦将原来的区域划分出了一块新的区域 $S$
如阴影部分所示, $\{S \in D_1\} \cup \{S \in D_2\} \cup \cdots$
这样的 $S$ 有$\left(\begin{gathered} n \\ 1 \end{gathered}\right)$ 个, 所以划分区域增加

$$\Delta_1=\left(\begin{gathered} n \\ 1 \end{gathered}\right)$$

$\textbf{ii)}$ 加入新点 $q$, 构成相交弦, 在圆内产生交点
从 $n$ 中任取 $3$ 个点, $\{a_1, a_2, a_3\}$, 不失一般性
假设$(q, a_3)$ 与 $(a_1, a_2)$ 相交, 交点位于圆内
增加的区域如下

$$\Delta_{2}=\left(\begin{gathered} n \\ 3 \end{gathered}\right)$$

$\textbf{证毕}$

$\textbf{practice1}$

$$\begin{gathered} S(n)+\sin(n+1) \varphi=\frac{\sin \frac{n \varphi}{2} \sin \frac{(n+1) \varphi}{2}}{\sin \frac{\varphi}{2}}+\frac{\sin (n+1) \varphi \sin \frac{\varphi}{2}}{\sin \frac{\varphi}{2}} \\ \ \\ \Rightarrow 2 \sin \frac{(n+1) \varphi}{2} \cos \frac{(n+1) \varphi}{2} \sin \frac{\varphi}{2}+\sin \frac{n \varphi}{2} \sin \frac{(n+1) \varphi}{2} \\ \ \\ \Rightarrow \sin \frac{(n+1) \varphi}{2}\left(2 \cos \frac{(n+1) \varphi}{2} \sin \frac{\varphi}{2}+\frac{\sin n \varphi}{2}\right) \\ \ \\ \Rightarrow \cos \frac{n \varphi}{2} \sin \varphi-2 \sin \frac{n \varphi}{2} \sin ^{2} \frac{\varphi}{2}+\frac{\sin n \varphi}{2} \\ \ \\ =\sin \left(\frac{n \varphi}{2}+\varphi\right) \end{gathered}$$

$\textbf{practice2}$

$$\begin{gathered} \sin \frac{n \varphi}{2} \cos \frac{(n+1) \varphi}{2}+\cos (n+1) \varphi \sin \frac{\varphi}{2} \\ \ \\ \Rightarrow 2 \cos ^{2} \frac{(n+1) \varphi}{2} \sin \frac{\varphi}{2}-\sin \frac{\varphi}{2}+\sin \frac{n \varphi}{2} \cos \frac{(n+1) \varphi}{2} \\ \ \\ \Rightarrow \cos \frac{(n+1) \varphi}{2}\left(2 \cos \frac{(n+1) \varphi}{2} \sin \frac{\varphi}{2}+\sin \frac{n \varphi}{2}\right)-\sin \frac{\varphi}{2} \\ \ \\ \text{bracket} \Rightarrow 2\left(\cos \frac{n \varphi}{2} \cos \frac{\varphi}{2}-\sin \frac{n \varphi}{2} \sin \frac{\varphi}{2}\right) \sin \frac{\varphi}{2}+\sin \frac{n \varphi}{2} \\ \ \\ =\sin \left(\frac{n \varphi}{2}+\varphi\right) \\ \ \\ \ \\ \Rightarrow \sin \left(\frac{(n+1) \varphi}{2}+\frac{\varphi}{2}\right) \cos \frac{(n+1) \varphi}{2}-\sin \frac{\varphi}{2} \\ \ \\ \Rightarrow 2 \sin \frac{(n+1) \varphi}{2} \cos \frac{(n+1) \varphi}{2} \cos \frac{\varphi}{2}+2 \cos ^{2} \frac{(n+1) \varphi}{2} \sin \frac{\varphi}{2}-2 \sin \frac{\varphi}{2} \\ \ \\ \Rightarrow \frac{\sin (n+1) \varphi \cos \frac{\varphi}{2}+\sin \frac{\varphi}{2} \cos (n+1) \varphi-\sin \frac{\varphi}{2}}{2 \sin \varphi / 2} \\ \ \\ \Rightarrow \frac{\sin \left((n+1) \varphi+\frac{\varphi}{2}\right)-\sin \frac{\varphi}{2}}{2 \sin \frac{\varphi}{2}}=\frac{\sin \frac{(n+1) \varphi}{2} \cos \frac{(n+2) \varphi}{2}}{\sin \frac{\varphi}{2}} \end{gathered}$$

置换

$\Omega=\{1,2, \ldots, n\}$, 通过不相交的类分解, 可以有
$\Omega=\Omega_{1} \cup \Omega_{2} \ldots \cup \Omega_{p}$ 称为轨道

$$\Omega_{k}=\left\{i, \pi(i), \pi^{2}(i), \ldots \pi^{l_{k}-1}(i)\right\}$$

$$\begin{gathered} l_{k} \leqslant q=\operatorname{Card}\langle\pi\rangle, \quad \pi^{l_{k}}(i)=i \\ \ \\ \pi_{k}=\left(i, \pi_{(i)}, \pi^{2}(i), \ldots, \pi^{l_{k}-1}(i)\right)=\left(\begin{gathered} i & \pi(i) & \cdots & \left.\pi^{k-2} (i)\right. \\ \pi ( i) & \pi^{2}(i) & \cdots & \left.\pi^{k-1}(i)\right. \end{gathered}\right) \\ \ \\ \forall j \in \Omega_{k}, \quad \pi(j)=\pi_{k}(j) \end{gathered}$$

置换的唯一分解
$\pi=\pi_{1} \pi_{2} \ldots \pi_{m}, \quad l_{k}>1, \quad 1 \leqslant k \leqslant m$
如果存在另一种分解, 不妨设为 $\pi=\alpha_{1} \alpha_{2} \ldots \alpha_{r}$

$$\exists \pi_{s}, \alpha_{t}, \quad \pi_{s}(i) \neq i, \quad \alpha_{t}(i) \neq i$$

$$\begin{gathered} \pi_{s}(i)=\pi(i)=\alpha_{t}(i), \text{ if we have} \\ \ \\ \pi_{s}^{k}(i)=\pi^{k}(i)=\alpha_{t}^{k}(i) \\ \ \\ \Rightarrow \pi \pi_{S}^{k}(i)=\pi^{k+1}(i)=\pi \alpha_{t}^{k}(i), \text{根据交换性} \Rightarrow \pi_{s}^{k} \pi(i)=\pi^{k+1}(i)=\alpha_{t}^{k} \pi(i) \\ \ \\ \pi_{s}^{k+1}(i)=\pi^{k+1}(i)=\alpha_{t}^{k+1}(i), \quad \forall k=\{0,1,2 \dots\} \\ \ \\ \text{let } k = 0, \pi_{s}=\alpha_{t} \end{gathered}$$

置换的符号是唯一的
证明的结论等价于置换的两个分解

$$\begin{gathered} \begin{gathered} &\pi=\tau_{1} \tau_{2} \ldots \tau_{k}\\ &\pi=\tau_{1}^{\prime} \tau_{2}^{\prime}\ldots \tau_{k'}^{\prime} \end{gathered} \\ k + k'\text{是一个偶数} \end{gathered}$$

$\textbf{i)}$

$$\begin{gathered} \left(\tau_{s}^{\prime}\right)^{2}=e, \quad \tau_{1} \tau_{2} \ldots \tau_{k} \tau_{k^{\prime} \cdots \cdots}^{\prime} \tau_{2}^{\prime} \tau_{1}^{\prime}=e \\ \ \\ \text{let} \quad e=\sigma_{1} \sigma_{2} \cdots \sigma_{m-1} \sigma_{m}, m>0 \\ \ \\ \text{只要证明, 将} m \text{个因子消减成} m-2 \text{个} \end{gathered}$$

$\textbf{ii)}$

$$\begin{gathered} e=\sigma_{1} \sigma_{2} \ldots \sigma_{p-1} \sigma_{p} \sigma_{p+1} \ldots \sigma_{m} \\ \ \\ \sigma_{p}=(s, t), \quad s \notin\left\{\sigma_{p+1}, \ldots \sigma_{m}\right\} \\ \ \\ \textbf{1)} \quad \sigma_{p-1}=(s\quad t) ,\quad \sigma_{p-1} \sigma_{p}=(s \quad t)(s \quad t)=e \Rightarrow \\ \ \\ m-2 \ \text{对换分解} \\ \ \\ \textbf{2)} \quad \sigma_{p-1}=(s, r), r \neq s, t \\ \ \\ \Rightarrow \sigma_{p-1} \sigma_{p}=(s, r)(s, t)=(s, t)(r, t) \\ \ \\ \textbf{3)} \quad \sigma_{p-1}=(t, r), r \neq s, t \\ \ \\ \Rightarrow \sigma_{p-1} \sigma_{p}=(t, r)(s, t)=(s, t)(t, r) \\ \ \\ \textbf{4)} \quad \sigma_{p-1}=(q, r), \quad\{q, r\} \cap\{s, t\}=\phi \\ \ \\ \sigma_{p-1} \sigma_{p}=(q, r)(s, t)=(s, t)(q, r) \end{gathered}$$

$\textbf{iii)}$
可以使用这样的操作, 把 $(s,t)$ 不断提前

$$\begin{gathered} e=\sigma_{1}^{\prime} \sigma_{2}^{\prime} \ldots \sigma_{m}^{\prime}, \sigma_{1}^{\prime}=\left(s, t^{\prime}\right), \quad s \notin\left\{\sigma_{2}^{\prime}, \sigma_{3}^{\prime},\ldots \sigma_{m}^{\prime}\right\} \\ \ \\ k>1, \quad \sigma_{k}^{\prime}(s)=s, \quad s=e(s)=\sigma_{1}^{\prime}(s)=t^{\prime} \neq s \end{gathered}$$