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

数学归纳法原理

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

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

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

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

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

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

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

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

01

证毕\textbf{证毕}

practice1\textbf{practice1}

S(n)+sin(n+1)φ=sinnφ2sin(n+1)φ2sinφ2+sin(n+1)φsinφ2sinφ2 2sin(n+1)φ2cos(n+1)φ2sinφ2+sinnφ2sin(n+1)φ2 sin(n+1)φ2(2cos(n+1)φ2sinφ2+sinnφ2) cosnφ2sinφ2sinnφ2sin2φ2+sinnφ2 =sin(nφ2+φ)\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}

practice2\textbf{practice2}

sinnφ2cos(n+1)φ2+cos(n+1)φsinφ2 2cos2(n+1)φ2sinφ2sinφ2+sinnφ2cos(n+1)φ2 cos(n+1)φ2(2cos(n+1)φ2sinφ2+sinnφ2)sinφ2 bracket2(cosnφ2cosφ2sinnφ2sinφ2)sinφ2+sinnφ2 =sin(nφ2+φ)  sin((n+1)φ2+φ2)cos(n+1)φ2sinφ2 2sin(n+1)φ2cos(n+1)φ2cosφ2+2cos2(n+1)φ2sinφ22sinφ2 sin(n+1)φcosφ2+sinφ2cos(n+1)φsinφ22sinφ/2 sin((n+1)φ+φ2)sinφ22sinφ2=sin(n+1)φ2cos(n+2)φ2sinφ2\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}

置换

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

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

lkq=Cardπ,πlk(i)=i πk=(i,π(i),π2(i),,πlk1(i))=(iπ(i)πk2(i)π(i)π2(i)πk1(i)) jΩk,π(j)=πk(j)\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}

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

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

πs(i)=π(i)=αt(i), if we have πsk(i)=πk(i)=αtk(i) ππSk(i)=πk+1(i)=παtk(i),根据交换性πskπ(i)=πk+1(i)=αtkπ(i) πsk+1(i)=πk+1(i)=αtk+1(i),k={0,1,2} let k=0,πs=αt\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}

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

π=τ1τ2τkπ=τ1τ2τkk+k是一个偶数\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}

i)\textbf{i)}

(τs)2=e,τ1τ2τkτkτ2τ1=e lete=σ1σ2σm1σm,m>0 只要证明, 将m个因子消减成m2\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}

ii)\textbf{ii)}

e=σ1σ2σp1σpσp+1σm σp=(s,t),s{σp+1,σm} 1)σp1=(st),σp1σp=(st)(st)=e m2 对换分解 2)σp1=(s,r),rs,t σp1σp=(s,r)(s,t)=(s,t)(r,t) 3)σp1=(t,r),rs,t σp1σp=(t,r)(s,t)=(s,t)(t,r) 4)σp1=(q,r),{q,r}{s,t}=ϕ σp1σp=(q,r)(s,t)=(s,t)(q,r)\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}

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

e=σ1σ2σm,σ1=(s,t),s{σ2,σ3,σm} k>1,σk(s)=s,s=e(s)=σ1(s)=ts\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}