数列Sequence-of-number

第一节：数列的概念

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

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

数列可以表示为：

$$a_1,a_2,…,a_n,…$$

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

数列的函数性与通项公式

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

$$f:N→R\\ n↦a_n$$

其中$\{a_n\}$表示数列的第$n$项。

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

Example

数列$1,4,9,16,25,…$的通项为$a_n=n^2$

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

数列$−1,1,−1,1,…$的通项可以是$a_n=(−1)^n$，也可以是$a_n=\cos \frac {nπ}{2}$

数列的递推公式

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

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

Example

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

$$f_0=0,f_1=1\\f_n=f_{n−1}+f_{n−2}$$

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

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

数列的子列

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

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

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

数列的差分

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

差分分为两种，数列$a_n$的前向差分为$a_{n+1}−a_n$，记为$Δa_n$。而后向差分则是 $a_n−a_{n−1}$，记为 $∇a_n$ （并且通常补充定义 $∇a_1=a_1$）。

前向差分和后向差分实际上只差一个平移。容易发现$∇a_{n+1}=Δa_n （n≥2）$。

差分依然是一个数列，可以继续做差分运算。一般地，一个数列差分$k$次之后的数列称为其 $k$ 阶差分，可以分别定义 $k$ 阶前向差分和 $k$ 阶后向差分,记为 $Δ^ka_n$ 和 $∇^ka_n$​。

数列的求和

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

$$S_n=a_1+a_2+⋯+a_n=\sum_{k=1}^{n}ak$$

其中符号$\sum$​​称为连加号或求和符号，数列的求和与差分互为逆运算。

第二节：数列的性质

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

有限性

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

有界性

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

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

单调性

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

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

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

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

Tip:

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

周期性

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

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

周期函数离散化之后未必是周期数列。例如$f(x)=\sin x$ 是一个典型的周期函数，但 $x_n=\sin n$ 不是一个周期数列。一般地，设 $\{x_n\}$ 为 $f(x)$ 在$ x=1,2,…$ 处抽样得到的离散化数列，若 $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=d$$

等差中项

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

等差数列的通项

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

Proof:

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

1. 当$n=1$时，$a_1=a_1+d(1−1)$显然成立；
2. 假设$a_{n−1}=a_1+d((n−1)−1)$，那么

$$a_{n-1} = a_n + d \\ = a_1+d((n-1)-1)+d\\ = a_1+d(n-1)$$

也成立。

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

Q.E.D.

等差数列的前$n$项和

等差数列的前$n$项和为$S_n=\frac{n(a_1+a_n)}{2}$或者$S_n=na_1+\frac{n(n-1)}{2}d$

Proof:

设等差数列$\{a_n\}^{\infty}_{n=1}$的前$n$项为$a_1,a_2,a_3,...,a_n$，公差为$d$​。则有：

$$S_n = \sum^{n}_{i=1}a_i\\ = \frac{1}{2}\sum^{n}_{i=1}(a_i+a_{n-i+1})\\ = \frac{1}{2}n(a_1+a_n)\\ = \frac{n(a_1+a_n)}{2}$$

代入通项公式$a_n=a_1+d(n−1)$就有：

$$S_n = \frac{n(a_1+a_n)}{2}=na_1+\frac{n(n+1)}{2}d$$

Q.E.D.

等比数列（几何数列）

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

定义的条件可以表示为：

$$\frac {a_{n+1}} {a_n}=q.$$

等比中项

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

等比数列的通项

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

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

Proof:

（商化差，最先想到的是对数）

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

$$\ln a_{n+1}- \ln a_n=\ln q$$

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

$$\ln a_n=\ln a_1+(n−1)\ln q=\ln a_1q^{n−1}.$$

所以有$a_n=a_1q^{n−1}$

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

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

Q.E.D.

等比数列的前$n$​项和

当$q\neq 1$时，等差数列的前$n$项和为$S_n=\frac{a_1(1-q^n)}{1-q}$或者$S_n=\frac{a_1-a_nq}{1-q}$​

当$q=1$时，等差数列的前$n$项和为$S_n=na_1$​

下证$q \neq 1$的情况：

Proof:

设等比数列$\{a_n\}^{\infty}_{n=1}$的前$n$项为$a_1,a_2,a_3,...,a_n$，公比为$q$​。则有：

$$S_n=\sum^{n}_{i=1}a_1q^{n-1}\\ qS_n=\sum^{n}_{i=1}a_1q^n\\$$

所以有：

$$(1-q)S_n=a_1(1-q^n)\\ S_n=\frac{a_1(1-q^n)}{1-q}$$

代入通项公式$a_n=a_1q^{n−1}$就有：

$$S_n = \frac{a_1(1-q^n)}{1-q}=\frac{a_1-a_nq}{1-q}$$

Q.E.D.

Note:

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