数列¶

\[ \renewcommand{\xfrac}{\displaystyle \frac} \renewcommand{\xsqrt}{\displaystyle \sqrt} \newcommand{\icr}{\!+\!\!+} \renewcommand{\N}{\mathbb{N}} \renewcommand{\Z}{\mathbb{Z}} \renewcommand{\R}{\mathbb{R}} \renewcommand{\C}{\mathbb{C}} \] $$ \renewcommand{\xfrac}{\displaystyle \frac} \renewcommand{\xsqrt}{\displaystyle \sqrt} \newcommand{\icr}{\!+\!\!+} \renewcommand{\N}{\mathbb{N}} \renewcommand{\Z}{\mathbb{Z}} \renewcommand{\R}{\mathbb{R}} \renewcommand{\C}{\mathbb{C}} $$

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

数列的概念¶

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

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

数列可以表示为：

\[ a_1, a_2, \dots, a_n, \dots \]

（其中$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$的函数：

\[ \begin{align} f: &\N\to\R \\ &n \mapsto a_n \\ \end{align} \]

其中$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_{n} = f_{n-1} + f_{n-2},f_1=1,f_2=1. \]

（初值也可以写为$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$项和为：

\[ S_n = a_1 + a_2 + \cdots + a_n = \sum_{k=1}^n a_k. \]

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

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

数列的性质¶

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

有限性¶

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

有界性¶

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

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

单调性¶

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

若一个数列$\{a_n\}$满足$\forall n \in \N: a_{n+1} \ge a_{n}$，则称这个数列单调递增（或者单调增加、单调上升），简称递增，一般记为$\{a_n\} \uparrow$或者$\{a_n\} \nearrow$，并称这个数列为递增数列。
若这个数列满足的是$\forall n \in \N: a_{n+1} > a_{n}$，则称这个数列严格递增，或称这个数列是严格递增数列。

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

若一个数列$\{a_n\}$满足$\forall n \in \N: a_{n+1} \le a_{n}$，则称这个数列单调递减（或者单调减少、单调下降），简称递减，一般记为$\{a_n\} \downarrow$或者$\{a_n\} \searrow$，并称这个数列为递减数列。
若这个数列满足的是$\forall n \in \N: a_{n+1} < a_{n}$，则称这个数列严格递减，或称这个数列是严格递减数列。

Tip

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

周期性¶

如果存在某一个正整数 $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+1} - a_n \equiv d. \]

等差数列的通项¶

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

Proof

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

当$n=1$时，$a_1 = a_1 + d(1-1)$显然成立；
假设$a_n-1 = a_1 + d((n-1)-1)$，那么

\[ \begin{align} a_{n+1} =& a_n + d \\ =& a_1 + d((n-1) - 1) + d \\ =& a_1 + d(n-1) \end{align} \]

也成立。

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

Q.E.D.

等差中项¶

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

等比数列（几何数列）¶

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

定义的条件可以表示为：

\[ \frac{a_{n+1}}{a_n} \equiv q. \]

等比数列的通项¶

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

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

Proof

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

\[ \ln{a_{n+1}} - \ln{a_{n}} \equiv \ln{q}. \]

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

\[ \ln{a_n} = \ln{a_1} + (n-1)\ln{q} = \ln{a_1 q^{n-1}}. \]

所以有$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)直译为“几何数列”。这和代数平均数、几何平均数是一致的。实际上，等差中项就是相邻两个数的（代数）平均数，而等比中项就是相邻两个数的几何平均数。