和式

1) 和式有两种写法 $$\sum_{k=1}^na_k\quad \text{and} \quad \sum_{1\leq k \leq n}a_k$$ 换句话说，一种是index，一种是集合。因为和式并不关心相加的顺序，所以集合的写法更准确的捕捉了和式的含义，并且，集合写法有时候更方便，因为集合的变换更容易理解。

比如index变量的替换，现在把$k$变$k+1$，集合的写法是 $$\sum_{1\leq k \leq n}a_k=\sum_{1\leq k+1 \leq n}a_{k+1}$$ 而index写法，必须修改上下边界常数。

2) 集合的indicator与和式

如果把indicator记为$[p(k)]$其中$p$的含义是property，如果k index的term具有property $p$那么$[p(k)]=1$否则$[p(k)]=0$。

和式可以写成 $$\sum_k a_k [p(k)]$$ 比如小于等于$N$的所有的素数的倒数之和记为 $$\sum_k[k \text{ is prime}][k \leq N]\frac{1}{k}$$

3) 和式与递归

$$ \begin{array}{l} &S_0=a_0\\ &S_n=S_{n-1}+a_n \end{array}\tag{1} $$ 简单形式的$a_n$决定的简单形式的$S_n$

假设$a_n$具有简单的形式 $$ \begin{array}{l} &a_0=\alpha\\ &a_n=\beta+\gamma n \end{array} $$ 假设$S_n$的封闭形式是 $$S_n=A(n)\alpha+B(n)\beta+C(n)\gamma$$

我们知道递归公式和$S_n$的封闭形式一一对应，这点可以通过归纳法证明，所以如果给出一个封闭形式，可以推出递归公式里的量$\alpha, \beta, \gamma $，

再通过我们假设的和式的，可以得到一个恒等式，两边都是刚才给出的封闭形式

$$S_n=1 \Rightarrow \alpha=1, \beta=0, \gamma=0 \Rightarrow 1=A(n)$$ 同样的 $$S_n=n \Rightarrow \alpha=0, \beta=1, \gamma=0 \Rightarrow n=B(n)$$ 进一步 $$S_n=n^2 \Rightarrow \alpha=0, \beta=-1, \gamma=2 \Rightarrow n^2=-B(n)+2C(n)$$ 第一个$\Rightarrow$是因为$a_n$形式的假设，第二个是因为$S_n$形式的假设。

递归化为和式得封闭形式

观察和式的递归形式，第二个式子特点是$S_n$和$S_{n-1}$的系数都为1，剩下的一个项是$a_n$。

对于一般的递归公式 $$a_nT_n=b_nT_{n-1}+c_n$$ 如果能在这个式子两边乘一个n的函数$s_n$，化为式子(1)的形式，比较我们可以得和式的$a_n$，然后把和式写成 $$S_n=\sum a_k$$ 计算得到$S_n$后，从里面除去$s_na_n$得到$T_n$。

因子$s_n$可以通过关系 $$s_nb_n=s_{n-1}a_{n-1}$$ 或者 $$s_n=s_{n-1}\frac{a_{n-1}}{b_n}$$ 得到。

4) 合并两个和式

$$\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$$

5) 得和式$S_n$的递归的一个方法

利用恒等式 $$\sum_{k=0}^na_k+a_{n+1}=a_0+\sum_{k=1}^{n+1}a_k$$ 如果能化为 $$S_n+a_{n+1}=a_0+F(S_n)$$ 例如等比数列和式$S_n=\sum_{k=0}^nax^k$ $$F(S_n)=xS_n$$

5) $S=\sum_{1\leq j\leq k\leq n}a_ja_k$

$$ \begin{array}{l} 2S&=\sum_{1\leq j\leq k\leq n}a_ja_k+\sum_{1\leq k\leq j\leq n}a_ja_k\\ &=\sum_{1\leq j,k\leq n}a_ja_k+\sum_{1\leq j=k\leq n}a_ja_k\\ &=(\sum_{1\leq k\leq n}a_k)^2+\sum_{1\leq k\leq n}a^2_k \end{array} $$

6) $S=\sum_{k=0}^n k^2$

利用高一级和式的恒等式$k^3$ $$\sum_{k=0}^n k^3+(n+1)^3=\sum_{0\leq k\leq n+1} k^3=\sum_{0\leq k+1\leq n+1} (k+1)^3$$ 也就是 $$\sum_{0\leq k\leq n} (k+1)^3=\sum_{0\leq k\leq n} (k^3+3k^2+3k+1)$$ 消去$\sum_{k=0}^n k^3$解代数方程可得需要的和式。