zsh

---

Formulas

$$C_t^{tp} \left({k \over N}\right )^{tp}\left(1-{k\over N}\right )^{t(1-p)}$$

三点形式

$$a_1+a_2+\cdots+a_n \tag{2.1}$$

有确定界限的表达形式，其中$a_k$为被加数

$$\sum^n_{k=1}a_k \tag{2.2}$$

推广形式

$$\sum_{1\le k \le n}a_k \tag{2.3}$$

一般化

$$\sum_{P(k)}a_k \tag{2.4}$$

艾弗森约定

$$\sum_k{a_k[P(k)]} \tag{2.5}$$

和式$S_n = \sum_{k=0}^na_k$等价于递归式

$$\begin{cases} S_0 &= a_0 \\ S_n &= S_{n-1} + a_n,\ n>0 \tag{2.6} \end{cases}$$

(2.6)中若$a_n=\beta+\gamma n$, 则可转换成一般形式：

$$\begin{cases} R_0&=\alpha \\ R_n&=R_{n-1} + \beta + \gamma n,\ n>0 \tag{2.7} \end{cases}$$

(2.7)的解的形式：

$$\begin{cases} R_n &= A(n)\alpha + B(n)\beta + C(n)\gamma \\ A(n) &= 1 \\ B(n) &=n \\ C(n) &= (n^2+n) / 2 \tag{2.8} \end{cases}$$

Hanoi塔的一般形式：

$$a_n T_n = b_n T_{n-1} + c_n \tag{2.9}$$

用求和因子法求得解为(要求所有a和所有b都不为0)：

$$\begin{cases} T_n = {1 \over {s_n a_n}}\left(s_1b_1T_0 + \sum^n_{k=1}s_kc_k\right) \\\\ s_n = {a_{n-1}a_{n-2}\cdots a_1\over b_n b_{n-1} \cdots b_2} \tag{2.10} \end{cases}$$

快速排序方法所作的比较步骤的平均次数满足递归式：

$$\begin{cases} C_0 &= C_1 = 0 \\ C_n &= n+1+{2 \over n}\sum^{n-1}_{k=0}C_k,\ n>1 \tag{2.12} \end{cases}$$

引入调和数

$$H_n = 1 + {1 \over 2} + \cdots + {1 \over n} = \sum_{k=1}^n{1\over k} \tag{2.13}$$

求得快速排序的解：

$$C_n = 2(n+1)H_n - {8\over3}n - {2\over3},\ n>1 \tag{2.14}$$

和式的一些处理公式：

$$\sum_{k\in K}ca_k = c\sum_{k\in K}a_k; (分配律) \tag{2.15}$$ $$\sum_{k\in K}(a_k + b_k) = \sum_{k\in K}a_k + \sum_{k\in K}b_k; (结合律) \tag{2.16} \label{2.16}$$ $$\sum_{k\in K}a_k = \sum_{p(k)\in K} a_{p(k)}; (交换律) \tag{2.17}\label{2.17}$$

小试牛刀求等差数列的和：

$$S = \sum_{k=0}^n(a+bk) = \left(a+{1\over2}bn\right)(n+1) \tag{2.18}\label{2.18}$$

对交换律$\eqref{2.17}$的限制放松一点后的例子：

$$\sum_{k\in K, k\ is\ even}a_k = \sum_{n\in K, n\ is\ even}a_n = \sum_{2k\in K, 2k\ is\ even}a_{2k} = \sum_{2k\in K} a_{2k} \tag{2.19}\label{2.19}$$

结合艾弗森约定，有：

$$\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 \label{2.20}\tag{2.20}$$

$\eqref{2.20}$由如下公式结合三大定律可以推出：

$$\sum_{k\in K}a_k = \sum_k a_k[k\in K] \tag{2.21}\label{2.21}$$ $$[k \in K] + [k \in K'] = [k \in K \cap K'] + [k \in K \cup K'] \tag{2.22} \label{2.22}$$

$\eqref{2.20}$的一个简单应用：将单独一项从和式中分出去

$$\sum_{0 \le k \le n}a_k = a_0 + \sum_{1 \le k \le n}a_k,\ n\ge 0 \tag{2.23}\label{2.23}$$

对于和式 $S_n = \sum_{0 \le k \le n} a_k$，应用扰动法，得到：

$$\begin{aligned} S_n + a_{n+1} = \sum_{0 \le k \le n+1} a_k &= a_0 + \sum_{1 \le k \le n+1} a_k \\ &= a_0 + \sum_{1 \le k+1 \le n+1} a_{k+1} \\ &= a_0 + \sum_{0 \le k \le n} a_{k+1} \end{aligned} \tag{2.24} \label{2.24}$$

用扰动法求几何级数$S_n = \sum_{0 \le k \le n} ax^k$的解为：

$$\sum_{k=0}^n ax^k = {a-ax^{n+1} \over 1-x},\ x \not= 1 \tag{2.25} \label{2.25}$$

用扰动法求另一个级数$S_n = \sum_{0 \le k \le n} k 2^k$的解为：

$$\sum_{k=0}^n kx^k = {x - (n+1) x^{n+1} + nx^{n+2} \over (1-x)^2},\ x \not= 1 \tag{2.26}\label{2.26}$$

在多重和式中对结合律$\eqref{2.16}$进行推广，得到交换求和次序的基本法则：

$$\sum_j\sum_k a_{j,k}[P(j,k)] = \sum_{P(j,k)} a_{j,k} = \sum_k\sum_j a_{j,k}[P(j,k)] \tag{2.27} \label{2.27}$$

一般分配律

$$\sum_{j \in J, k \in K} a_j b_k = \left( \sum_{j \in J} a_j\right) \left( \sum_{k \in K} b_k \right) \tag{2.28} \label{2.28}$$

$\eqref{2.27}$的变型之简易型；当$j$和$k$的范围相互无关时采用。

$$\sum_{j \in J} \sum_{k \in K} a_{j,k} = \sum_{j \in J, k \in K} a_{j,k} = \sum_{k \in K} \sum_{j \in J} a_{j,k} \tag{2.29} \label{2.29}$$

$\eqref{2.27}$的变型之复杂型；当$j$和$k$的范围有关联时采用。

$$\begin{aligned} \sum_{j \in J} \sum_{k \in K(j)} a_{j,k} = \sum_{k \in K'} \sum{j \in J'(k)} a_{j,k} \\ [j \in J][k \in K(j)] = [k \in K'][j \in J'(k)] \end{aligned} \tag{2.30} \label{2.30}$$

$\eqref{2.30}$中限制条件的一个经常出现的情况：

$$[1 \le j \le n][j \le k \le n] = [1 \le j \le k \le n] = [1 \le k \le n][1 \le j \le k] \tag{2.31} \label{2.31}$$

结合$\eqref{2.31}$与$\eqref{2.30}$有：

$$\sum_{j=1}^n \sum_{k=j}^n a_{j,k} = \sum_{1 \le j \le k \le n} a_{j,k} = \sum_{k=1}^n \sum_{j=1}^k a_{j,k} \tag{2.32} \label{2.32}$$

应用$\eqref{2.32}$求解上三角和式：

$$\sum_{1 \le j \le k \le n} a_j a_k = {1 \over 2} \left( \left( \sum_{k=1}^n a_k \right)^2 + \sum_{k=1}^n a_k^2 \right) \tag{2.33} \label{2.33}$$

应用$\eqref{2.32}$求解另一个和式：

$$\begin{aligned} \sum_{1 \le j \lt k \le n}(a_k-a_j)(b_k-b_j) = n \sum_{k=1}^n a_k b_k - \left( \sum_{k=1}^n a_k \right) \left( \sum_{k=1}^n b_k\right) \\ \left( \sum_{k=1}^n a_k \right) \left( \sum_{k=1}^n b_k\right) = n \sum_{k=1}^n a_k b_k - \sum_{1 \le j \lt k \le n}(a_k-a_j)(b_k-b_j) \end{aligned} \tag{2.34} \label{2.34}$$

指标（下标？）替换的一般公式：

$$\begin{aligned} \sum_{j \in J} a_{f(j)} &= \sum_{k \in K} a_k \# f^-(k) \\ f^-(k) &= \{j | f(j) = k\} \\ \# f^-(k) &= \# Elements\ in\ f^-(k) \end{aligned} \tag{2.35} \label{2.35}$$

关于调和级数的一个恒等式：

$$\sum_{0 \le k \lt n} H_k = n H_n - n. \tag{2.36} \label{2.36}$$

一般性方法讲了求解如下和式的多种方法

$$\square_n = \sum_{0\le k \le n} k^2, \quad n\ge 0 \tag{2.37} \label{2.37}$$

上式的解为：

$$\square_n = {n(n+{1\over 2})(n+1)\over 3} \tag{2.38} \label{2.38}$$

\eqref{2.38}更符合直觉的一种形式：

$$\square_n = {n(n+{1\over 2})(n+1)\over 3} \tag{2.39} \label{2.39}$$

利用成套方法求解，将\eqref{2.7}扩展

$$\begin{aligned} R_0 &= \alpha \\ R_n &= R_{n-1} + \beta + \gamma n + \delta n^2,\quad n>0 \end{aligned} \tag{2.40} \label{2.40}$$

\eqref{2.40}解的一般形式为：

$$R_n = A(n)\alpha + B(n)\beta + C(n)\gamma + D(n)\delta \tag{2.41} \label{2.41}$$

进入差分部分。
类似于无限微积分的定义$Df(x)=\lim\limits_{h \to 0} {f(x+h) - f(x) \over h}$，给出有限微积分的定义(差分)：

$$\Delta f(x) = f(x+1) - f(x) \tag(2.42) \label(2.42)$$

定义下降阶乘幂：

$$x^{\underline m} = x(x-1)\cdots (x-m+1),\quad Integer\ m \ge 0 \label{2.43} \tag{2.43}$$

定义上升阶乘幂：

$$x^{\overline m} = x(x+1)\cdots (x+m-1), \quad Integer\ m \ge 0 \tag{2.44} \label{2.44}$$

类似于有限微积分的公式$D(x^m) = m x^{m-1}$，有：

$$\Delta({x^{\underline m}}) = m x^{\underline{m-1}} \tag{2.45} \label{2.45}$$

类似于$g(x) = Df(x) \Leftrightarrow \int g(x) dx = f(x) + C$，有：

$$g(x) = \Delta f(x) \Leftrightarrow \sum g(x)\delta x = f(x) + C \tag{2.46} \label{2.46}$$

上式中$\sum g(x)\delta x$是$g(x)$的不定和式。函数$C$满足$C(x+1)=C(x)$即可，不需要一定是常数。

类似于$\int_a^bg(x)dx = f(x) |_a^b = f(b) - f(a)$，有和式：

$$g(x) = \Delta f(x) \Rightarrow \sum\nolimits_a^b g(x)\delta x = f(x) |_a^b = f(b) - f(a) \tag{2.47} \label{2.47}$$

对不定和式的公式：

$$\sum\nolimits_a^b g(x)\delta x = \sum\limits_{k=a}^{b-1}g(k) = \sum\limits_{a \le k \lt b} g(k), \quad Integer b \ge a. \tag{2.48} \label{2.48}$$ $$\sum\nolimits_a^b g(x)\delta x + \sum\nolimits_b^c g(x)\delta x = \sum\nolimits_a^c g(x) \delta x \tag{2.49} \label{2.49}$$

结合$\eqref{2.45}, \eqref{2.47}, \eqref{2.48}$, 有：

$$\sum_{0\le k \lt n} k^{\underline m} = \left.{k^{\underline{m+1} }\over m+1}\right|_0^n = {n^{\underline {m+1} }\over m+1}, \quad Integer\ n,m \ge 0 \tag{2.50} \label{2.50}$$

将下降幂扩展到负数：

$$x^{\underline{-m} } = {1 \over (x+1)(x+2)\cdots (x+m)}, \quad m > 0. \tag{2.51} \label{2.51}$$

类似于$x^{m+n} = x^m x^n$，有：

$$x^{\underline{m+n} } = x^{\underline m} (x-m)^{\underline n}, \quad m,n\ are\ Integers \tag{2.52} \label{2.52}$$

下降幂的和式的完整形式：

$$\sum\nolimits_a^b x^{\underline m} \delta x = \begin{cases} \left.{x^{\underline{m+1} }\over m+1}\right|_a^b, \quad &m \ne -1, \\ H_x |_a^b, \quad &m = -1. \end{cases}$$

类似于$D(uv) = uDv + vDu$，有：

$$\Delta(u(x)v(x)) = u(x)\Delta v(x) + v(x+1)\Delta u(x) \tag{2.54} \label{2.54}$$

定义移位算子 $Ef(x) = f(x+1)$，将$\eqref{2.54}$化为更紧凑的形式：

$$\Delta (uv) = u\Delta v + Ev\Delta u \tag{2.55} \label{2.55}$$

类似于$\int uDv = uv - \int vDu$，有分部求和法则：

$$\sum u\Delta v = uv - \sum Ev \Delta u \tag{2.56} \label{2.56}$$

关于调和级数的公式：

$$\sum\limits_{0\le k \lt n} k H_k = \sum\nolimits_0^n x H_x \delta x = {n^{\underline 2}\over 2}\left(H_n - {1\over 2}\right) \tag{2.57} \label{2.57}$$

Notations

利用(2.3)形式可以表达：

$$\sum_{p\le N,\ p\ is\ prime}{1 \over p}$$

对于(2.5)，我们约定当[xxx]中的条件为假时，整项为0，则可以表达如下和式：

$$\sum_p{[p\ is\ prime][p\le N]{1 \over p}}$$

和式和递归 Sums and Recurrences

和式的处理 Manipulation of Sums

$\eqref{2.17}$中$p(k)$需满足：对每个整数n，都恰好存在一个整数$k$，使得$p(k)=n$，否则交换律可能不成立。

$\eqref{2.19}$中放松要求的具体说明：对于$K$中的元素$n$，恰好有一个整数$k$满足$p(k)=n$。如果$n\not\in K$，则无所谓存在0个或多个整数$k$满足$p(k)=n$。

多重和式 Multiple Sums

考虑计算如下和式$S_n=\Sigma_{1 \le j \lt k \le n}{1 \over k-j}$

先对j或者先对k求和，可以得到：

$$S_n = \sum_{0 \le k \lt n} H_k$$

而先用$k+j$替换$k$，可以得到：

$$\begin{aligned} S_n &= \sum_{1 \le j \lt k \le n} {1 \over k-j} \\ &= \sum_{1 \le j \lt k+j \le n} {1 \over k} \\ &= nH_n - n \end{aligned}$$

结合以上两式可以得到$\eqref{2.36}$

一般性的方法 General Methods

成套方法

成套方法中，得到了$\eqref{2.40}$与$\eqref{2.41}$。
现在想求$A(n),B(n),C(n)$。

1. 令$\delta=0$，相当于求解$\eqref{2.7}$，可解得$A(n), B(n), C(n)$，结果在\eqref{2.8}中。
2. 取一个特例，令$R_n=n^3$，结合$\eqref{2.40}$可以得到$\alpha=0, \beta=1, \gamma=-3, \delta=3$，代入$\eqref{2.41}$，得到关于$D(n)$的关系式：$3D(n) - 3C(n) + B(n) = n^3$， 解得$D(n) = {n(n+{1\over 2})(n+1)\over 3}$。至此，所有参数已经解出来了。是个通解。

若$R_n = \square_n$, 则$\alpha=\beta=\gamma=0, \delta=1$，所以$\square_n = R_n = D(n)$

展开与收缩

$$\begin{aligned} \square_n &= \sum_{1\le k \le n} k^2 \\ &= \sum_{1\le j \le k \le n} k \\ &= \sum_{1 \le j \le n} \sum_{j \le k \le n} k \\ &= \sum_{1 \le j \le n} \left({j+n \over 2}\right)(n-j+1) \\ &= {1 \over 2} \sum_{1 \le j \le n}(n(n+1)+j-j^2) \\ &= {1 \over 2} n^2 (n+1) + {1 \over 4} n (n+1) - {1\over 2} \square_n \\ &= {1 \over 2} n (n+ {1 \over 2}) (n+1) - {1 \over 2} \square_n \end{aligned}$$

有限微积分和无限微积分 Finite and Infinite Calculus

注意分部求和公式$\eqref{2.45}$中有移位算子。

例子，求$\sum\nolimits_{0\le k \lt n} k H_k$。

令$u(x)=H_x,\ \Delta v(x) = x = x^{\underline 1}$,有$\Delta u(x) = x^{\underline{-1} }, v(x) = x^{\underline 2} / 2, Ev(x) = (x+1)^{\underline 2} / 2$,
则有

$$\begin{aligned} \sum x H_x \delta x &= \sum u(x) \Delta v(x) \\ &= u(x)v(x) - \sum Ev(x)\Delta u(x) \\ &= H_x x^{\underline 2}/2 - \sum {(x+1)^{\underline 2}\over 2}x^{\underline {-1} }\delta x \\ &= {x^{\underline 2}\over 2} H_x - {x^{\underline 2}\over 4} + C \end{aligned}$$

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。