本节主要介绍数列的基础知识，其中大部分内容已经在高中数学提及。

数列(Number sequence)，是由许多个数排成一列组成的有序对象。在不至于引起混淆时，也可称为序列(Sequence)或简称列，但严格来说，序列不止包括数列（如向量列、函数列也是序列）。

数列可以是有限的，也可以是无限的。不过，不加说明时，数列指的通常是无限数列。

数列可以表示为：

（其中\(a_1, a_2, \dots, a_n, \dots\)表示不同的数），通常简记为\(\{a_n\}\)。在一些严格的数学分析教材中，也会记为\(\{a_n\}_{n=1}^{m}\)（表示有限数列\(a_1,a_2,\dots,a_m\)）或\(\{a_n\}_{n=1}^{\infty}\)（表示无限数列）。

数列是重要的离散对象，在许多科学领域应用广泛。

数列可以视为一个从自然数集\(\N\)或正整数集\(\Z^+\)（或其子集）映射到实数集\(\R\)或复数集\(\C\)的函数：

其中\(a_n\)表示数列的第\(n\)项。

函数\(f(n)\)称为数列的通项公式，通项公式未必唯一。

Example

数列\(1,4,9,16,25,\dots\)的通项为\(a_n = n^2\)；

数列\(0,1,2\)的通项可以是\(a_n=n-1(n=1,2,3)\)，也可以是\(a_n=(n-1)!\)。

数列\(-1,1,-1,1,\dots\)的通项可以是\(a_n = (-1)^{n}\)，也可以是\(\cos\xfrac{n\pi}{2}\)。

数列的递推公式(Recurrence formula)或递推关系(Recurrence relation)，简单来说，就是将项\(a_n\)表示为之前项的函数。也就是说，\(a_n = f(a_{n-1},\dots,a_1)\)。

这种关系式一般给定了几个项的值（如\(a_1 = 1\)），称为初值条件(initial condition)。

Example

斐波那契数列(Fibonacci sequence)是典型的递推关系数列。用\(\{f_n\}\)表示Fibonacci数列，则\(\{f_n\}\)的递推关系和初值条件为：

（初值也可以写为\(f_0=0,f_1=1\)）

这个数列和兔子繁殖问题有关：设一对小兔子需要两个月成熟，从第三个月起一对成熟的兔子会产生一对小兔子，新生的小兔子同样需要两个月成熟。第\(n\)个月有多少对小兔子？

这个问题最先由Fibonacci提出，并得到了上面的递推关系式。因此，我们称这个数列为Fibonacci数列，而其中的每一项称为Fibonacci数。

一个数列的子列(Subsequence)，指的是从其中取出一部分项（可以有限或无限）并且不破坏原来的顺序关系构成的新数列。

例如，数列\(1,2,3,\dots,n,\dots\)的一个子列是\(1,3,5\)（有限子列），一个子列也可以是\(1,3,5,\dots\)（无限子列）。而\(5,3,1\)，\(3,2,1,5,6,\dots\)不是这个数列的子列，因为它们改变了项的顺序。

数列\(\{ a_n \}\)的子列通常用\(\{ a_{n_k} \}\)表示，其中\(\{n_k\}\)每一项皆为自然数（或正整数），且\(\forall k: n_{k+1} > n_k\)（也就是\(\{n_k\}\)严格递增，数列“严格递增”的定义见下面“单调性”）。或者，简单说，这就是一个“复合数列”。

一个数列的差分(Difference)，指的是数列的相邻两项之差。

差分分为两种，数列 \({a_n}\) 的前向差分为 \(a_{n+1} - a_{n}\)，记为 \(\Delta a_n\)。而后向差分则是 \(a_{n} - a_{n - 1}\)，记为 \(\nabla a_n\) （并且通常补充定义 \(\nabla a_1 = a_1\)）。

前向差分和后向差分实际上只差一个平移。容易发现 \(\nabla a_{n + 1} = \Delta a_n\) （\(n \ge 2\)）。

差分依然是一个数列，可以继续做差分运算。一般地，一个数列差分 \(k\) 次之后的数列称为其 \(\boldsymbol{k}\) 阶差分，可以分别定义 \(k\) 阶前向差分和 \(k\) 阶后向差分,记为 \(\Delta^k a_n\) 和 \(\nabla^k a_n\)。

一个数列的求和 (Summation)，通常指的是前 \(\boldsymbol{n}\) 项和，在算法领域也称为前缀和。数列的前\(n\)项和也是一个新的数列，通常记作\(s_n\)或\(S_n\)。也就是说，数列\({a_n}\)的前\(n\)项和为：

其中符号\(\displaystyle \sum\)称为连加号或求和符号，其性质可以参考数列的求和一节。

数列的求和与差分互为逆运算。

数列作为特殊的函数，同样可以讨论它的一些函数性质，并利用这些性质进行分类。

有限数列和无限数列上面已有涉及。

若存在实数\(m,M\)，使得\(\forall n: m < a_n < M\)，则称数列\(\{a_n\}\)是有界(Bounded)的，\(m,M\)分别为这个数列的上界(Upper bound)和下界(Lower bound)。

或者，我们可以直接讨论数列的值域。数列的值域也是一个数集，我们完全可以讨论这个数集的有界性，并把值域的有界性作为数列的有界性。这个定义和上面的定义是等价的。

类似于函数的单调性，但由于数列是离散的，我们只需要比较每对相邻的项：

同样地，递减也可以定义：

很容易验证这个定义和函数的单调性是一致的。或者说，如果将数列视为一个定义在自然数或正整数上的函数，那么函数的单调性和数列的单调性等价。

如果存在某一个正整数 \(T\)，使得 \(\forall n: a_{n+T} = a_{n}\)，则称数列 \(\{a_n\}\) 是周期数列(Periodic sequence)，数 \(T\) 是这个数列的周期(Period)。

容易发现若 \(T\) 是一个数列的周期，则 \(2T, 3T, \dots\) 也是这个数列的周期，因此我们称其中最小的一个周期为数列的 最小周期。不加说明时，数列的周期通常指的是最小周期。不同于取值连续的函数，一个数列若是周期数列，则其最小周期必定存在。

周期函数离散化之后未必是周期数列。例如 \(f(x) = \sin{x}\) 是一个典型的周期函数，但 \(x_n = \sin{n}\) 不是一个周期数列。一般地，设 \(\{x_n\}\) 为 \(f(x)\) 在 \(x = 1, 2, \dots\) 处抽样得到的离散化数列，若 \(f(x)\) 的一个周期是有理数，则 \(\{x_n\}\) 是周期数列。

两个周期数列相加之和依然是周期数列。设 \(\{a_n\}\) 的周期为 \(T_1\)，\(\{b_n\}\) 的周期为 \(T_2\)，则有 \(\{a_n + b_n\}\) 的一个周期为 \([T_1, T_2]\)（未必最小），其中 \([T_1, T_2]\) 表示 \(T_1\) 和 \(T_2\) 的最小公倍数。

如果一个数列的邻项之差（也就是差分）都等于同一个数，那么这个数列就是等差数列(arithmetic sequence)，这个数称为公差(common difference)，一般用字母\(d\)表示。

定义的条件可以用符号表示为：

等差数列的通项为\(a_n = a_1 + d(n-1)\)或\(a_n = a_0 + dn\)，这个公式可以由数学归纳法证明。

设等差数列的第一项为\(a_1\)，公差为\(d\)，用数学归纳法证明如下：

也成立。

所以通项公式对所有的\(n \in \Z^+\)都成立。

Q.E.D.

等差数列的连续三项\(a_1,a_2,a_3\)中，\(a_2\)称为\(a_1\)和\(a_3\)的等差中项。

如果一个数列的邻项之比都等于同一个数，则称这个数列为等比数列或几何数列(geometric arithmetic)，这个数称为数列的公比(common ratio)，一般用字母\(q\)表示。

定义的条件可以表示为：

等比数列的通项公式为\(a_n = a_1 q^{n-1}\)或者\(a_n = a_0 q^n\)。同样地，这个公式可以由数学归纳法证明。

不过，重复这种数学归纳过程有点trivial，所以以下我们尝试用等差数列推出等比数列公式的证明：

当\(a_1>0\)且\(q>0\)时，我们可以对\({a_{n+1}}/{a_n} \equiv q\)取对数，得到：

这说明\(\{\ln{a_{n+1}}\}\)是公差为\(\ln{q}\)的等差数列，它的通项公式为：

所以有\(a_n = a_1 q^{n-1}\)。

当\(a_1 > 0\)但\(q < 0\)时，我们可以乘上\((-1)^{n+1}\)，转换为公比为正的数列。

当\(a_1 < 0\)时，我们则可以取相反数得到首项为正的等比数列。

Q.E.D.

等比数列的连续三项\(a_1,a_2,a_3\)中，\(a_2\)称为\(a_1\)和\(a_3\)的等比中项。

Notation

从等差数列和等比数列的英文可以发现，等差数列(arithmetic sequence)的直译为“代数数列”，而等比数列(geometric sequence)直译为“几何数列”。这和代数平均数、几何平均数是一致的。实际上，等差中项就是相邻两个数的（代数）平均数，而等比中项就是相邻两个数的几何平均数。