读《具体数学》

简要笔记

2.1记号

$\sum_{k=1}^{n}a_{}^{k}$ 

其中a_k是被加数,k介于下限1和上限n之间

$\sum_{k=1}^{\pi(N)} \frac{1}{p}$

其中p_k表示第K个素数，$\pi(N)$表示<=N的素数的个数

这个和式指出了接近N的随机整数平均而言约有多少个素因子，对于大的N，其值近似等于ln ln N+M

其中M约为0.261 497 212 847 642 783 755 426 838 608 695 859 051 566 6

2.2和式和递归式

对于一个递归式

$ R_{0}=\alpha $ 

$ R_{n} = R_{n-1} + \beta + \gamma n $   n>0

通解

$R_{n} = A\left ( n \right )\alpha  + B\left ( n \right )\beta + c\left ( n \right )\gamma$

求解方法：使用成套方法，用简单函数代替R_n，求得$\alpha $ $\beta$ $\gamma$

利用待定系数法，计算出R₀  R₁  R₂ 三个方程解三个未知数，解出$\alpha $ $\beta$ $\gamma$ 便可得到答案

a_nT_n = b_nT_n-1+c_n

事实上我们可以把任何形式的a_nT_n = b_nT_n-1+c_n转化为和式

只要我们找到一个实当的求和因子s来乘以两边：

s_na_nT_n = s_nb_nT_n-1+s_nc_n

恰当选择s_n使得

s_nb_n=s_n-1a_n-1

这样的话就得到新的和式-递归式

S_n-1=S_n-1+s_nc_n

从而

$S_{n}=s_{0}a_{0}T_{0}+\sum_{k=1}^{n}s_{k}c_{k}$

那么其实，T_n答案的解就是

$T_{n}=\tfrac{1}{s_{n}a_{n}}(s_{0}a_{0}T_{0}+\sum_{k=1}^{n}s_{k}c)$

那么如何求解S_n?

利用s_n=s_n-1a_n-1/b_n把上下展开

$s_{n}=\frac{a_{n-1}a_{n-2}\cdots a_{1}}{b_{n}b_{n-1}\cdots b_{2}}$

调和数：

$H_{n}=1+\frac{1}{2}+\cdots+\frac{1}{n}=\sum_{k=1}^{n}\frac{1}{k}$

2.3 和式的处理

三条法则

分配律$\sum_{k\in K}ca_{k}=c\sum_{k\in K}a_{k}$

结合律$\sum_{k\in K}\left ( a_{k}+b_{k} \right )=\sum_{k\in K}a_{k}+\sum_{k\in K}b_{k}$

交换律$\sum_{k \in K}a_{k}=\sum_{p\left (k \right)\in K}a_{p{\left ( k \right )}}$

需要注意的是，一般的交换律中的函数p(k)，都是假设所有整数的排列，即对于每一个整数n都恰好存在一个整数k，使得p(k)=n，否则可能错误。

扰动法

扰动法基本公式$\sum_{k \in K}a_{k}+\sum_{k \in K'}a_{k'}=\sum_{k \in K\cap K'}a_{k}+\sum_{k \in K\cup K'}a_{k}$

把一项分出去的运算，便是扰动法，它可以用来封闭形式来计算和式

步骤：从未知的和式开始，并记录它的S_n

$S_{n}=\sum_{0\leq k\leq n}a_{k}$

然后通过把它的最后一项和第一项分离出来，用两种方法改写S_n+1

$S_{n}+a_{n+1}=\sum_{0\leq k\leq n+1}a_{k}=a_{0}+\sum_{1\leq k\leq n+1}a_{k}$

           $=a_{0}+\sum_{1\leq k+1\leq n+1}a_{k+1}$

           $=a_{0}+\sum_{0\leq k\leq n}a_{k+1}$

然后对最后的那个和式子进行相应处理，用S_n表示出来，从而建立S_n的方程。

当然求解不仅限于这一种方法，求导，错位相减，等初等技巧，也是求解和式的好方法。

2.4 多重和式

如果P(j,k)是j与k的一种性质，所有使得p(j,k)为真的项a_i,k之和可以用这两种表示

$\sum _{P\left ( j,k \right )}a_{j,k}=\sum _{j,k}a_{j,k}[P(j,k)]$

有如下公式

$\sum _{P\left ( j,k \right )}a_{j,k}=\sum _{j} \sum _{k}a_{j,k}[P(j,k)]=\sum _{k} \sum _{j}a_{j,k}[P(j,k)]$

适当选择求和次序，使得问题简化

一般的分配律：

$\sum_{j\in J,k\in K}a_jb_k=(\sum_{j\in J}a_{j})(\sum_{k\in K}b_{k})$

切比雪夫单调不等式：

$(\sum_{k=1}^{n}a_{k})(\sum_{k=1}^{n}b_{k})\leq n\sum _{k=1}^{n}a_{k}b_{k}$ 其中a₁<=...<=a_n 且 b₁<=...<=b_n 

$(\sum_{k=1}^{n}a_{k})(\sum_{k=1}^{n}b_{k})\geq n\sum _{k=1}^{n}a_{k}b_{k}$ 其种a₁<=...<=a_n

且 b₁>=...>=b_n

积分形式

$(\int _{a}^{b}f(x)dx)(\int _{a}^{b}g(x)dx)\leq (b-a)(\int _a^bf(x)g(x)dx)$

$\sum _{0\leq k< n}H_{k}=nH_n-n$