2.4 序列与求和

序列

定义1\(\qquad\) 序列是从整数集的一个子集（通常是集合\(\{0, 1, 2,\cdots\}\)或集合\(\{1, 2, 3, \cdots\}\)）到一个集合 \(S\) 的函数。记号\(a_n\)表示整数\(n\)的像，称为序列的一个项。

定义2\(\qquad\) 序列 $$ a,ar,ar^2,\cdots,ar^n,\cdots $$ 称为几何级数，其中首项 \(a\)和公比\(r\) 都是实数。

定义3\(\qquad\) 序列 $$ a,a+d,a+2d,\cdots,a+nd,\cdots $$ 称为算术级数，其中首项 \(a\)和公差\(d\) 都是实数。

计算机科学中将形如 \(a_1, a_2, \cdots, a_n\) 的有穷序列称为串。 这个串也可以记作 \(a_1a_2\cdots a_n\)。

比特串是比特的有限序列。

递推关系

定义4\(\qquad\) 对所有满足\(n\ge n_0\)（\(n_0\)为非负整数）的\(n\)，将\(a_n\)用序列前面项，即\(a_0, a_1, \cdots, a_{n-1}\)中的一项或多项来表示，称为序列\(\{a_n\}\)的递推关系。

如果一个序列的项满足递推关系，则该序列就称为是递推关系的一个解。

定义5\(\qquad\) 斐波那契数列\(f_0, f_1, f_2, \cdots\)是初始条件为\(f_0 = 0\)和\(f_1 = 1\)且满足递推关系 $$ f_n = f_{n-1} + f_{n-2}\qquad n = 2, 3, \cdots $$ 的序列。

如果为序列的项找到一个显示公式，即闭公式，那么就说明求解了一个带有初始条件的递推关系。

求和

对于序列\(a_m, a_{m+1}, a_{m+2}, \cdots, a_n\)，可以使用记号 $$ \sum_{j=m}^{n}a_j\quad\text{或}\quad \sum_{m\le j\le n}a_j $$ 表示 $$ a_m+a_{m+1}+\cdots+a_n $$

定理1\(\qquad\)如果\(a\)和\(r\)都是实数且\(a\ne0\),则 $$ \sum_{j=0}^{n}ar^j = \begin{cases} a\frac{1-r^{n+1}}{1-r}\quad\text{当}r\ne1 \ a(n+1)\quad\text{当}r=1 \end{cases} $$