Concrete Mathematics 选读笔记
第一章 递归问题
1.1 汉诺塔（翻译是河内塔）
通项式：$ T_n=2^n-1$
思考过程就是考虑 \(n-1\) 个盘的操作为一个整体，然后对第 \(n\) 个盘和这一个整体进行一个 \(n=1\) 时的基本交换操作。
可以得到 \(T_n=2T_{n-1}+1\)
在这里学习了 数学归纳法
数学归纳法在我的理解可以分为简单的 \(2\) 步
对于基本简单的情况验证，比如说 \(n=1\) 的时候对整体验证。
然后假设猜测在前 \(n-1\) 项都成立，推第 \(n\) 项，仍然成立则成立。
\(\texttt{e.g.}\)
\[f_n=\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6} \]可以用归纳法证明，如下：
验证 \(f_1=1,f_2=5\) 符合
假设前 \(n-1\) 项成立
\[\begin{aligned} \therefore f_n & =f_{n-1}+n^2\\ &=\frac{n(n-1)(2n-1)}{6}+n^2\\ &=\frac{n(n+1)(2n+1)}{6} \end{aligned} \]另外，这种递推式貌似就叫 封闭形式
而 项数 与 变量 有关，那就不是封闭形式，通俗来说就是不要有省略号一类。
1.2 平面上的直线
多条直线划分平面的数学模型。
不难找规律发现 \(L_n=L_{n-1}+n\)
然后有 \(L_0=1,L_1=2,L_2=4\dots\)
所以我们发现可以不断展开：
\(L_n=L_{n-2}+n-1+n=\dots=L_0+1+2+\dots+n=1+\frac{n(n+1)}{2}\)
后面 折线 的那个思考题很有意思。
将 \(F_n\) ，也就是 \(n\) 条折线全部延长，然后扩展成 \(L_{2n}\) 再减去多出来的 \(2n\) 块。
有：
\[\begin{aligned} F_n=L_{2n}-2n &= 1+\frac{2n(n+1)}{2}-2n\\ &=1+n(2n+1)-2n\\ &=2n^2-n+1 \end{aligned} \]1.3 约瑟夫问题
这个进制推导式非常的有意思。
首先看约瑟夫问题幸存者的推导式。
\[\left\{\begin{aligned} J_1&=1;\\ J_{2n}&=2J_n-1,n\geq1;\\ J_{2n+1}&=2J_n+1,n\geq 1 \end{aligned}\right. \]其余一些扩展和封闭推导，归纳证明啥的具体看书。我们这里就聊聊这个式子的进制表达，真的很巧妙啊。
可以考虑 \(2n\) 和 \(2n+1\) 的常数项为进制位，因为求进制我们确实是一直求余数，所以这个可以表示递推式。先将 变量 转换为进制，再用通项式再转换进制位为另一进制。具体操作见书上草稿
对于一个式子 \(J_{2n{\color{red}+1}}={\color{red}2}J_{n}\color{red}+1\)
标红色的分别表示：进制位，二次转换的进制位数，以及每个数所占进制的大小。
即使是二进制，我们转换时也可以不在 \(\{0,1\}\) 集合内，因为需要可以改变进制位系数，具体还是看书吧。上面有很清楚的 draft 。
第二章 和式
2.1 和式
\(\sum\) 相关定义，略。
2.2 和式和递归式
这里有一个扰动法的技巧，其实就是我们中学数学常用的化简方法。
可以用这个玩意证明等比数列的公式，如下：
\[\begin{aligned} S_n &=\sum_{k=0}^n aq^k\\ S_n + a_{n+1}&=a_0+\sum_{k=1}^{n+1}aq^k\\ &=a_0+\sum_{k=0}^{n}aq^{k+1}\\ &=a_0+q\sum_{k=0}^nq^k\\ \therefore S_n+a_{n+1}&=a_0+qS_n\\ \therefore S_n&=\frac{a_0-a_{n+1}}{1-q}\\ S_n&=\frac{a_0-a_n\times q}{1-q}\\ \end{aligned} \]还有一个调和数的定义（字母 \(H\) (\(\text{Harmonic}\)) 表示 调和的 所以调和数为 \(H_n\) ），很有意思，简单记一下：
\[H_n=1+\frac{1}{2}+\dots+\frac{1}{n}=\sum_{k=1}^n\frac{1}{k} \]用这个可以辅以分析快排时间复杂度（运算次数），很有意思，具体可以看下书 (\(\texttt{P24}\))。
其实就是说对于长度为 \(n\) 的随机数列，快排的比较步骤次数的平均值满足一个递归式：
\[\left\{\begin{aligned} C_0&=C_1=0;\\ C_n&=n+1+\frac{2}{n}\displaystyle\sum_{k=0}^{n-1}C_k, n>1 \end{aligned}\right. \]我们最后通过推导得出：
\(\displaystyle C_n=2(n+1)H_n-\frac{8}{3}n-\frac{2}{3},n>1\)
可能比较奇怪，但是确实是对的。
2.3 和式的处理
和式有几条法则与推广：
- \(\displaystyle \sum_{k\in \mathbb K}ca_k=c\sum_{k\in\mathbb K}a_k;\) （分配律）
- \(\displaystyle \sum_{k\in\mathbb K}(a_k+b_k)=\sum_{k\in\mathbb K}a_k+\sum_{k\in\mathbb K}b_k;\) （结合律）
- \(\displaystyle\sum_{k\in\mathbb K}a_k=\sum_{p(k)\in\mathbb K}a_{p(k)}\) （交换律）
书上关于这些法则的应用举了很多例子，可以自行选择练习。
2.4 多重和式
对于多重和式，我们有 交换求和次序 法则，可以推出多重和式的结合律：
\(\displaystyle\sum_j\sum_ka_{j,k}[P(j,k)]=\sum_{P(j,k)}a_{j,k}=\sum_k\sum_ja_{j,k}[P(j,k)]\)
这一章提到了一个 切比雪夫单调不等式：
\(\displaystyle (\sum_{k=1}^na_k)(\sum_{k=1}^nb_k)\leq n\sum_{k=1}^na_kb_k, a\leq \dots \leq a_n \& b_1\leq\dots\leq b_n,\)
\(\displaystyle (\sum_{k=1}^na_k)(\sum_{k=1}^nb_k)\geq n\sum_{k=1}^na_kb_k, a\leq \dots \leq a_n \& b_1\geq\dots\geq b_n,\)
同时得出一个特例 具体见 (\(\texttt{P32}\))
\(\displaystyle (\sum_{k=1}^na_k)(\sum_{k=1}^nb_k)=n\sum_{k=1}^na_kb_k-\sum_{1\leq j
我们试着从小情况来证明一下
取 \(n=2\) ,假设符合第一行的情况 \((a_1
另外一行同理。
2.5 一般性的方法
咕咕咕
2.6 有限微积分和无限微积分
咕咕咕
2.7 无限和式
咕咕咕
（其实是笔者不会积分，还在努力学习，咕咕咕）
第五章 二项式系数
这里(Luogu)