2.4. 序列与求和

序列是元素的有序列表，在离散数学中有许多应用。序列也是计算机科学中一种重要的数据结构。一个序列中的项可以通过一个适用于序列中每一项的公式描述。

序列

序列

序列（sequence）是一个从整数集的一个子集（通常是集合$\set{0,1,2,\dots}$或集合$\set{1,2,3,\dots}$）到一个集合$S$的函数。用记号$a_n$表示整数$n$的像。称$a_n$为序列的一个像(term)。

序列$\set{a_n}$，其中$\displaystyle a_n = \frac{1}{n}$。从$a_1$开始的这个序列项的列表，即

$$1, \frac{1}{2},\frac{1}{3},\frac{1}{4},\dots$$

几何级数

集合级数是如下形式的序列

$$a, ar, ar^2,\dots,ar^n,\dots$$

其中初始项$a$和公比$r$都是实数。

评注：几何级数是指函数$f(x)=ar^x$的离散的对应体。

算数级数

算数级数是如下形式的序列

$$a,a+d,a+2d,\dots,a+nd,\dots$$

其中初始项$a$和公差$d$都是实数。

评注：算数级数是指函数$f(x)=dx+a$的离散的对应体。

递推关系

递推关系

关于序列${a_n}$的一个递推关系(recurrence relation)是一个等式，对所有满足$n \ge n_0$的$n$，它把$a_n$用序列中前面项即$a_0,a_1,\dots,a_{n-1}$中的一项或多项来表示，这里$n_0$是一个非负整数。如果一个序列的项满足递推关系，则该序列就称为是递推关系的一个解。（一个递推关系称为递归定义了一个序列）

如$a_n=a_{n-1} + 3$，$a_0=2$，$n=1,2,3,\dots$

递归定义的序列的初始条件指定了在递推关系定义的首项前的那些项。

斐波那契数列

斐波那契数列$f_0,f_1,f_2,\dots$，由初始条件$f_0=0, f_1=1$和下列递推关系定义

$$f_n=f_{n-1}+f_{n-2}，n=2,3,4,\dots$$

特殊的整数序列

求和

用记号

$$\sum_{j=m}^{n} a_j,\sum_{m \le j \le n}^{n} a_j$$

来表示$a_m + a_{m+1} + \dots + a_n$，此处变量$j$称为求和下标，而字母$j$作为变量可以是任意的，即可以使用任何其他字母。

$$\sum_{j=1}^{n}(ax_j + by_j) = a\sum_{j=1}^{n} x_j + b\sum_{j=1}^{n} y_j$$

如果$a$和$r$都是实数且$r \neq 0$，则

$$\sum_{j=0}^{n} ar^j = \begin{cases} \displaystyle \frac{ar^{n+1} - a}{r -1} & r \neq 1 \\ \\ (n+1)a & r \neq 1 \\ \end{cases}$$

多个有用的求和公式

和	闭形式
$\displaystyle\sum_{k=0}^{n} ar^k(r \neq 0)$	$\displaystyle\frac{ar^{n+1} - a}{r - 1}, r \neq 1$
$\displaystyle\sum_{k=1}^{n} k$	$\displaystyle\frac{n(n+1)}{2}$
$\displaystyle\sum_{k=1}^{n} k^2$	$\displaystyle\frac{n(n+1)(2n+1)}{6}$
$\displaystyle\sum_{k=1}^{n} k^3$	$\displaystyle\frac{n^2(n+1)^2}{4}$
$\displaystyle\sum_{k=0}^{\infty} x^k, \: \mid x \mid <1$	$\displaystyle\frac{1}{1 - x}$
$\displaystyle\sum_{k=1}^{\infty} kx^{k-1}, \: \mid x \mid <1$	$\displaystyle\frac{1}{(1 - x)^2}$