入门级-数学-数列

# 数列

<div style="display:none;" class="hidden-latex">
\[
\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}}
$$
</div>

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

---

## 数列的概念

**数列**(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$ 或复数集 $\mathbb{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\frac{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)，指的是从其中<u>取出一部分项</u>（可以有限或无限）并且<u>不破坏原来的顺序关系</u>构成的新数列。

例如，数列$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$称为**连加号**或**求和符号**，其性质可以参考<a href="/初等数学/数列/02数列的求和/">数列的求和</a>一节。

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

---

## 数列的性质

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

---

### 有限性

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

---

### 有界性

若存在实数$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$，用数学归纳法证明如下：

1. 当$n=1$时，$a_1 = a_1 + d(1-1)$显然成立；
2. 假设$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$。同样地，这个公式可以由数学归纳法证明。

Proof
可以自己尝试。

---

#### 等比中项

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

Notation

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