学习笔记·数列

数列

数列（sequence）是数字的序列。一般来说，数列是一个定义在正整数集的子集上的函数，记$a_{n} = f(n)$，则数列可以表示为$\{a_{n}\}$。数列中的每一个数称为数列的项（term），$a_{1}$称为数列的首项（initial term）。定义在无限集合上的数列叫做无穷数列（infinite sequence）；否则叫做有穷数列（finite sequence），最后一项称为数列的末项。
有时候，我们也允许零甚至负数的下标，如$a_{0}, a_{-1}$等。我们通过额外的标注来表现这些，例如$\{a_{n}\}_{0}^{\infty}$表示一个从$a_{0}$开始的无穷数列。

对于数列$\{a_{n}\}$，如果$\forall n \in \mathbb{N}^{\ast}, a_{n + 1} \ge a_{n}$成立，则称其为递增数列（monotonically increasing sequence）；如果$\forall n \in \mathbb{N}^{\ast}, a_{n + 1} \le a_{n}$成立，则称其为递减数列（monotonically decreasing sequence）。递增数列和递减数列统称单调数列（monotonic sequence）。所有项都相等的数列称为常数列（constant sequence）。
如果存在正整数$k$，使得$\forall n \in \mathbb{N}^{\ast}, a_{n + k} = a_{n}$成立，则称数列$\{a_{n}\}$为周期数列（periodic sequence），$k$就是数列的周期（period）。周期数列一定有最小正周期（minimal positive period）。

数列$\{a_{n}\}$的第$n$项$a_{n}$与$n$之间存在某种关系，这个关系式就是数列的通项公式，也就是数列的函数解析式。例如，对于数列$-\dfrac{1}{2}, \dfrac{1}{4}, -\dfrac{1}{8}, \dfrac{1}{16}, \cdots$，$a_{n} = (-\dfrac{1}{2})^{n}$是它的一个通项公式。
递推公式（recurrence relation）给出了项与前一项的关系式，同样能确定数列。一般地，递推公式可以表示为$f(a_{1}, \cdots, a_{n}) = 0$。例如，斐波那契数列（Fibonacci sequence）的递推公式是$a_{n} = a_{n - 1} + a_{n - 2}$。

对于数列$\{a_{n}\}$，令$S_{n} = \sum\limits_{i=1}^{n} a_{i}$，则$S_{n}$称为数列的前$n$项和（series）。显然，$a_{n} = S_{n} - S_{n - 1} (n \ge 2)$。

等差数列与等比数列

等差数列

观察自然数序列$0, 1, 2, 3, \cdots$，可以发现，数列的每一项与前一项的差都是常数$1$。一般地，数列$\{a_{n}\}$若满足存在常数$d$使得$\forall n \in \mathbb{N}^{\ast}, a_{n + 1} - a_{n} = d$，则称为等差数列（arithmetic progression），常数$d$称为等差数列的公差（common difference）。
最简单的等差数列只有三项。对于等差数列$a, A, b$，显然$A = \dfrac{a + b}{2}$。$A$称为$a, b$的等差中项，它实际上也是两个数的算术平均数。

根据定义，每一项与前一项相差$d$，那么第$n$项就与首项相差$(n - 1) d$，于是得到等差数列的通项公式：

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

等差数列的通项公式是一个关于$n$的一次函数，反过来，通项公式是一次函数的数列也都是等差数列。

从通项公式出发，还能进一步得到：

$$\begin{align} & a_{n} = a_{k} + (n - k) d (n, k \in \mathbb{N}^{\ast}) \\ & d = \dfrac{a_{m} - a_{n}}{m - n} (m \ne n) \end{align}$$

如果有正整数$m, n, p, q$，使得$m + n = p + q$，那么有：

$$a_{m} + a_{n} = a_{p} + a_{q}$$

证明如下：

$$\begin{align} a_{m} + a_{n} &= a_{1} + (m - 1) d + a_{1} + (n - 1) d \\ &= 2a_{1} + (m + n - 2) d \\ &= 2a_{1} + (p + q - 2) d \\ &= a_{1} + (p - 1) d + a_{1} + (q - 1) d \\ &= a_{p} + a_{q} \quad \Box \end{align}$$

从这条性质出发可以得到：

$$a_{n - k} + a_{n + k} = 2a_{n} (n, k \in \mathbb{N}^{\ast}, k < n)$$

德国数学家高斯（Carl Friedrich Gauss，1777－1855）读小学时就发现了求等差数列前$n$项和的方法。把$S_{n}$的加项倒过来可得$S_{n} = \sum\limits_{i=1}^{n} a_{n + 1 - i}$，那么，$2S_{n} = \sum\limits_{i=1}^{n} (a_{i} + a_{n + 1 - i}) = \sum\limits_{i=1}^{n} (a_{1} + a_{n}) = n (a_{1} + a_{n})$，即

$$S_{n} = \dfrac{n (a_{1} + a_{n})}{2}$$

这就是等差数列的前$n$项和公式。
代入$a_{n} = a_{1} + (n - 1) d$，可得

$$S_{n} = na_{1} + \dfrac{n (n - 1)}{2} d$$

设正整数$N$为常数，等差数列$\{a_{n}\}$的前$n$项和是$S_{n}$，令$S_{0} = 0$，则不难发现，数列$\{S_{nN} - S_{(n - 1) N}\}$也是等差数列。
设$\{a_{n}\}$的公差是$d$，直接计算：

$$\begin{align} S_{nN} - S_{(n - 1) N} &= nNa_{1} + \dfrac{nN (nN - 1)}{2} d - (n - 1) Na_{1} - \dfrac{(n - 1) N ((n - 1) N - 1)}{2} d \\ &= Na_{1} + \dfrac{(2n - 1) N^{2} - N}{2} d \\ &= n \cdot N^{2} d + Na_{1} - \dfrac{N (N + 1)}{2} d \quad \Box \end{align}$$

顺便得到这个数列的公差是$N^{2} d$。

等差数列的概念可以进一步推广。数列$\{a_{n + 1} - a_{n}\}$称为数列$\{a_{n}\}$的差分。根据定义，等差数列的差分是常数列。如果对数列差分再进行差分，即$(a_{n + 2} - a_{n + 1}) - (a_{n + 1} - a_{n}) = a_{n + 2} - 2a_{n + 1} + a_{n}$，得到的数列称为$\{a_{n}\}$的二阶差分。以此类推，可以得到数列的$N$阶差分。如果一个数列的$N$阶差分是非零常数列，那么称其为$N$阶等差数列。二阶及以上的等差数列统称为高阶等差数列。

等比数列

一般地，数列$\{a_{n}\}$若满足存在常数$q \ne 0$使得$\forall n \in \mathbb{N}^{\ast}, \dfrac{a_{n + 1}}{a_{n}} = q$，则称为等比数列（geometric progression），常数$q$称为等比数列的公比（common ratio）。
最简单的等比数列只有三项。对于等比数列$a, G, b$，显然$q = \dfrac{G}{a} = \dfrac{b}{G}$，即$G = \pm \sqrt{ab}$。$G$称为$a, b$的等比中项，它的绝对值实际上也是两个数的几何平均数。

等比数列的通项公式是：

$$a_{n} = a_{1} \cdot q^{n - 1}$$

等比数列有类似等差数列的推论：

$$\begin{align} & a_{n} = a_{k} \cdot q^{n - k} (n, k \in \mathbb{N}^{\ast}) \\ & q^{m - n} = \dfrac{a_{m}}{a_{n}} (m \ne n) \end{align}$$

如果有正整数$m, n, p, q$，使得$m + n = p + q$，那么有：

$$a_{m} a_{n} = a_{p} a_{q}$$

从这条性质出发可以得到：

$$a_{n - k} a_{n + k} = a_{n}^{2} (n, k \in \mathbb{N}^{\ast}, k < n)$$

等比数列的前$n$项和公式可以利用错位相减法推出：
由定义，有$S_{n} = \sum\limits_{i=1}^{n} a_{i}$。两边同时乘以$q$，得$qS_{n} = \sum\limits_{i=1}^{n} qa_{i} = \sum\limits_{i=1}^{n} a_{i + 1} = \sum\limits_{i=2}^{n + 1} a_{i}$。两式相减，$(1 - q) S_{n} = a_{1} - a_{n + 1} = a_{1} (1 - q^{n})$，即得

$$S_{n} = a_{1} \cdot \dfrac{1 - q^{n}}{1 - q}$$

从第$k$项开始求和，结果类似：

$$\sum\limits_{i=k}^{n} a_{i} = a_{k} \cdot \dfrac{1 - q^{n - k + 1}}{1 - q} = a_{1} \cdot \dfrac{q^{k - 1} - q^{n}}{1 - q}$$

设正整数$N$为常数，等比数列$\{a_{n}\}$的前$n$项和是$S_{n}$且$S_{N} \ne 0$，令$S_{0} = 0$，则不难发现，数列$\{S_{nN} - S_{(n - 1) N}\}$也是等比数列。
设$\{a_{n}\}$的公比是$q$，直接计算：

$$\begin{align} S_{nN} - S_{(n - 1) N} &= a_{1} \dfrac{1 - q^{nN}}{1 - q} - a_{1} \dfrac{1 - q^{(n - 1) N}}{1 - q} \\ &= a_{1} \dfrac{q^{(n - 1) N} - q^{nN}}{1 - q} \\ &= \dfrac{a_{1} (1 - q^{N})}{1 - q} \cdot q^{(n - 1) N} \quad \Box \end{align}$$

顺便得到这个数列的公比是$q^{N}$。

递推数列

逐差法

如果数列的递推公式可以转化为$a_{n + 1} - a_{n} = f(n)$的形式，那么就可以像推导等差数列通项公式一样累加，这种求解递推数列的方法叫做逐差法：

$$a_{n} = a_{1} + \sum\limits_{i=1}^{n - 1} f(i)$$

例如，设数列$\{a_{n}\}$满足$a_{1} = 1, a_{n + 1} - 2a_{n} = 3^{n}$，求$\{a_{n}\}$的通项公式：
等式两边同时除以$2^{n}$，得到$\dfrac{a_{n + 1}}{2^{n}} - \dfrac{a_{n}}{2^{n - 1}} = (\dfrac{3}{2})^{n}$。令$b_{n} = \dfrac{a_{n}}{2^{n - 1}}$，则$b_{1} = 1, b_{n + 1} - b_{n} = (\dfrac{3}{2})^{n}$。根据等比数列的前$n$项和公式，$b_{n} = b_{1} + \sum\limits_{i=1}^{n - 1} (\dfrac{3}{2})^{i} = 2 ((\dfrac{3}{2})^{n} - 1)$。所以$a_{n} = 2^{n - 1} b_{n} = 3^{n} - 2^{n}$。

齐次常系数线性递推数列

最常见的递推数列就是齐次常系数线性递推数列，递推公式形如

$$a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2} + \cdots + c_{k} a_{n - k} (n > k)$$

其中$c_{1}, \cdots, c_{k}$是与$n$无关的常数，$c_{k} \ne 0$。数列$\{a_{n}\}$称为齐次常系数$k$阶线性递推数列。一阶线性递推数列就是等比数列。

二阶线性递推数列比较重要。设数列$\{a_{n}\}$满足$a_{n} = ua_{n - 1} + va_{n - 2} (n \ge 3)$。可以通过等比数列求解，设复数$\alpha, \beta$满足$a_{n} - \alpha a_{n - 1} = \beta (a_{n - 1} - \alpha a_{n - 2})$，则数列$\{a_{n} - \alpha a_{n - 1}\}$是等比数列。比较递推公式，满足$\begin{cases} \alpha + \beta = u \\ \alpha \beta = -v \end{cases}$，也就是说$\alpha, \beta$是方程$x^{2} - ux - v = 0$的两根。
如果$\alpha \ne \beta$，即$u^{2} + 4v \ne 0$，根据等比数列通项公式，有$a_{n + 1} - \alpha a_{n} = \beta^{n - 1} (a_{2} - \alpha a_{1}) = c \beta^{n}$，其中$c = \dfrac{1}{\beta} (a_{2} - \alpha a_{1})$。两边同时除以$\alpha^{n}$，$\dfrac{a_{n + 1}}{\alpha^{n}} - \dfrac{a_{n}}{\alpha^{n - 1}} = c (\dfrac{\beta}{\alpha})^{n}$。利用逐差法，$\dfrac{a_{n}}{\alpha^{n - 1}} = a_{1} + \sum\limits_{i=1}^{n - 1} c (\dfrac{\beta}{\alpha})^{i} = a_{1} + c \dfrac{\beta - \dfrac{\beta^{n}}{\alpha^{n - 1}}}{\alpha - \beta}$，即$a_{n} = (a_{1} + \dfrac{c \beta}{\alpha - \beta}) \alpha^{n - 1} - \dfrac{c}{\alpha - \beta} \beta^{n} = c_{1} \alpha^{n} + c_2 \beta^{n}$，其中$c_{1} = \dfrac{1}{\alpha} (a_{1} + \dfrac{c \beta}{\alpha - \beta}) = \dfrac{a_{2} - \beta a_{1}}{\alpha (\alpha - \beta)}, c_{2} = -\dfrac{c}{\alpha - \beta} = \dfrac{a_{2} - \alpha a_{1}}{\beta (\beta - \alpha)}$。
如果$\alpha = \beta$，即$u^{2} + 4v = 0$，那么$\alpha^{n}$，$\dfrac{a_{n + 1}}{\alpha^{n}} - \dfrac{a_{n}}{\alpha^{n - 1}} = c$，其中$c = \dfrac{1}{\alpha} (a_{2} - \alpha a_{1})$。这样就得到一个等差数列，$\dfrac{a_{n}}{\alpha^{n - 1}} = a_{1} + (n - 1) c$，即$a_{n} = (a_{1} - c + cn) \alpha^{n - 1} = (c_{1} + c_{2} n) \alpha^{n}$，其中$c_{1} = \dfrac{1}{\alpha} (a_{1} - c) = \dfrac{2\alpha a_{1} - a_{2}}{\alpha^{2}}, c_{2} = \dfrac{c}{\alpha} = \dfrac{a_{2} - \alpha a_{1}}{\alpha^{2}}$。

总结一下：设数列$\{a_{n}\}$满足$a_{n} = ua_{n - 1} + va_{n - 2} (n \ge 3)$，$\alpha, \beta$是方程$x^{2} - ux - v = 0$的两个复数根，
若$\alpha \ne \beta$，则$a_{n} = c_{1} \alpha^{n} + c_2 \beta^{n}$，其中$c_{1}, c_{2}$满足方程组$\begin{cases} c_{1} \alpha + c_{2} \beta = a_{1} \\ c_{1} \alpha^{2} + c_{2} \beta^{2} = a_{2} \end{cases}$；
若$\alpha = \beta$，则$a_{n} = (c_{1} + c_{2} n) \alpha^{n}$，其中$c_{1}, c_{2}$满足方程组$\begin{cases} (c_{1} + c_{2}) \alpha = a_{1} \\ (c_{1} + 2c_{2}) \alpha^{2} = a_{2} \end{cases}$。

方程$x^{2} - ux - v = 0$称为特征方程，$\alpha, \beta$称为特征根。这种方法就称为特征根法。

对于一般的递推公式$a_{n} = c_{1} a_{n - 1} + \cdots + c_{k} a_{n - k} (n > k)$，其特征方程是$x^{k} - \sum\limits_{i=1}^{k} c_{i} x^{k - i} = 0$。

若特征方程有$k$个两两不同的特征根$\alpha_{1}, \cdots, \alpha_{k}$，则数列的通项公式为$a_{n} = \sum\limits_{i=1}^{k} u_{i} \alpha_{i}^{n}$，其中常数$u_{1}, \cdots, u_{k}$满足方程组$\begin{cases} u_{1} \alpha_{1} + \cdots + u_{k} \alpha_{k} = a_{1} \\ u_{1} \alpha_{1}^{2} + \cdots + u_{k} \alpha_{k}^{2} = a_{2} \\ \quad \vdots \\ u_{1} \alpha_{1}^{k} + \cdots + u_{k} \alpha_{k}^{k} = a_{k} \end{cases}$。

若有些特征根相同，可以将特征方程因式分解为$\prod\limits_{i=1}^{t} (x - \alpha_{i})^{m_{i}}$，其中$\alpha_{i}$为互不相同的复数，$m_{i} \in \mathbb{N}^{\ast}, \sum\limits_{i=1}^{t} m_{i} = k$。数列的通项公式则是$a_{n} = \sum\limits_{i=1}^{t} P_{i}(n) \alpha_{i}^{n}$，其中$P_{i}$为低于$m_{i}$次的多项式。

不动点法

设数列$\{a_{n}\}$有递推公式$a_{n + 1} = \dfrac{Aa_{n} + B}{Ca_{n} + D} (C \ne 0, AD - BC \ne 0)$，方程$x = \dfrac{Ax + B}{Cx + D}$的根称为数列$\{a_{n}\}$的不动点。
如果有两个不动点$x_{1}, x_{2}$，对$k \in \{1, 2\}$，$a_{n + 1} - x_{k} = \dfrac{Aa_{n} + B}{Ca_{n} + D} - \dfrac{Ax_{k} + B}{Cx_{k} + D} = \dfrac{(AD - BC) (a_{n} - x_{k})}{(Ca_{n} + D) (Cx_{k} + D)}$。两式相除，得到$\dfrac{a_{n + 1} - x_{1}}{a_{n + 1} - x_{2}} = \dfrac{Cx_{2} + D}{Cx_{1} + D} \cdot \dfrac{a_{n} - x_{1}}{a_{n} - x_{2}}$，数列$\{\dfrac{a_{n} - x_{1}}{a_{n} - x_{2}}\}$就是等比数列。
如果只有一个不动点$x_{0}$，那么$\dfrac{1}{a_{n + 1} - x_{0}} = \dfrac{1}{a_{n} - x_{0}} + \dfrac{2C}{A + D}$，数列$\{\dfrac{1}{a_{n} - x_{0}}\}$就是等差数列。

数列求和

高阶等差数列

等差数列的通项公式是一个一次多项式，前$n$项和是一个二次多项式。而对于一般的$N$阶等差数列，其通项公式是$N$次多项式，前$n$项和是$N + 1$次多项式。
设数列$\{a_{n}\}$的通项公式是$a_{n} = \sum\limits_{i=0}^{N} c_{i} n^{i}$，则前$n$项和是$S_{n} = \sum\limits_{k=1}^{n} a_{k} = \sum\limits_{k=1}^{n} \sum\limits_{i=0}^{N} c_{i} k^{i} = \sum\limits_{i=0}^{N} c_{i} (\sum\limits_{k=1}^{n} k^{i})$。
这样，就只要对$\sum\limits_{k = 1}^{n} k^{i}$求和，称为正整数的$i$次幂和。零次幂和即$\sum\limits_{k=1}^{n} 1 = n$；一次幂和就是等差数列求和，即$\sum\limits_{k=1}^{n} k = \dfrac{1}{2} n (n + 1)$。

对于$N$次幂和，可以借助$N$次之前的全部幂和来求解。例如，对任意正整数$k$，由$(k + 1)^{3} - k^{3} = 3k^{2} + 3k + 1$，从而累加可得$(n + 1)^{3} - 1 = \sum\limits_{k = 1}^{n} ((k + 1)^{3} - k^{3}) = \sum\limits_{k=1}^{n} (3k^{2} + 3k + 1)$。展开得到$n^{3} + 3n^{2} + 3n = 3 \sum\limits_{k=1}^{n} k^{2} + 3 \sum\limits_{k=1}^{n} k + n = 3 \sum\limits_{k=1}^{n} k^{2} + \dfrac{3}{2} n^{2} + \dfrac{5}{2} n$。化简得到

$$\sum\limits_{k = 1}^{n} k^{2} = \dfrac{1}{6} n (n + 1) (2n + 1)$$

类似地，可以得到三次幂和：

$$\sum\limits_{k = 1}^{n} k^{3} = \dfrac{1}{4} n^{2} (n + 1)^{2}$$

错位相减法

设$\{a_{n}\}, \{b_{n}\}$分别是等差数列和等比数列，公差和公比分别是$d, q$，求数列$\{a_{n} b_{n}\}$的前$n$项和。
令$S_{n} = \sum\limits_{i=1}^{n} a_{i} b_{i}$，那么有$qS_{n} = \sum\limits_{i=1}^{n} a_{i} (qb_{i}) = \sum\limits_{i=1}^{n} a_{i} b_{i + 1} = \sum\limits_{i=2}^{n + 1} a_{i - 1} b_{i}$。我们发现乘以公比之后$a_{i}, b_{i}$之间错开了一位。两式相减，得到

$$\begin{align} (1 - q) S_{n} &= \sum\limits_{i=1}^{n} a_{i} b_{i} - \sum\limits_{i=2}^{n + 1} a_{i - 1} b_{i} \\ &= a_{1} b_{1} - a_{n} b_{n + 1} + \sum\limits_{i=2}^{n} (a_{i} - a_{i - 1}) b_{i} \\ &= a_{1} b_{1} - a_{n} b_{n + 1} + d \sum\limits_{i=2}^{n} b_{i} \\ &= a_{1} b_{1} - (a_{1} + (n - 1) d) b_{1} q^{n} + db_{1} \dfrac{q - q^{n}}{1 - q} \end{align}$$

也就是$S_{n} = \dfrac{a_{1} b_{1} - (a_{1} + (n - 1) d) b_{1} q^{n}}{1 - q} + \dfrac{db_{1} (q - q^{n})}{(1 - q)^{2}}$。这种求数列前$n$项和的方法叫做错位相减法。

裂项法

对任意数列$\{a_{n}\}$，求$S_{n} = \sum\limits_{i=1}^{n} a_{i}$时，如果存在一个数列$\{b_{n}\}$使得$a_{n} = b_{n + 1} - b_{n}$，则可以求出$S_{n} = \sum\limits_{i=1}^{n} (b_{i + 1} - b_{i}) = b_{n + 1} - b_{1}$，将求和问题转化为求解$\{b_{n}\}$。这种方法叫做裂项法。

例如，设数列$\{a_{n}\}$的通项公式是$a_{n} = \dfrac{1}{n (n + 1)}$，求$\{a_{n}\}$的前$n$项和。
令$S_{n} = \sum\limits_{i=1}^{n} \dfrac{1}{i (i + 1)}$，注意到$\dfrac{1}{i (i + 1)} = \dfrac{1}{i} - \dfrac{1}{i + 1}$，那么有$S_{n} = \sum\limits_{i=1}^{n} (\dfrac{1}{i} - \dfrac{1}{i + 1})$。求和中每一项的减数与下一项的被减数抵消，最后就得到结果$S_{n} = 1 - \dfrac{1}{n + 1} = \dfrac{n}{n + 1}$。

数学归纳法

要证明一个命题对所有值成立，我们可以证明命题对第一个值成立，而且从一个值到下一个值的过程有效。如同多米诺骨牌效应，第一块骨牌的倒下会导致所有骨牌都倒下。这种证明方法叫做数学归纳法（mathematical induction）。

第一数学归纳法原理有：
设$P(n)$是关于正整数$n$的命题。如果$P(1)$成立，且对任意正整数$k$，$P(k)$成立可以推出$P(k + 1)$成立，那么$P(n)$对任意正整数$n$成立。
用逻辑符号表示就是：

$$P(1) \land (\forall k \in \mathbb{N}^{\ast}, P(k) \to P(k + 1)) \to \forall n \in \mathbb{N}^{\ast}, P(n)$$

例如，用数学归纳法证明$\sum\limits_{i=1}^{n} i^{2} = \dfrac{1}{6} n (n + 1) (2n + 1)$。
$n = 1$时，$1^{2} = \dfrac{1}{6} \times 1 \times (1 + 1) \times (2 + 1)$成立；
假设命题对$n = k$成立，即$\sum\limits_{i=1}^{k} i^{2} = \dfrac{1}{6} k (k + 1) (2k + 1)$，则$n = k + 1$时，

$$\begin{align} \sum\limits_{i=1}^{k + 1} i^{2} &= \sum\limits_{i=1}^{k} i^{2} + (k + 1)^{2} \\ &= \dfrac{1}{6} k (k + 1) (2k + 1) + (k + 1)^{2} \\ &= \dfrac{1}{6} (k + 1) (k (2k + 1) + 6 (k + 1)) \\ &= \dfrac{1}{6} (k + 1) (k + 2) (2k + 3) \end{align}$$

命题对$n = k + 1$也成立。所以命题对任意正整数$n$成立。$\Box$

数学归纳法以良序原理（well-ordering theorem）为基础：
对$\mathbb{N}^{\ast}$的任意非空子集$S$，$S$必有最小元素。也就是存在$a \in S$，使得对任意$b \in S$都有$b \ge a$。

数学归纳法还有另一种形式，即第二数学归纳法原理：
设$P(n)$是关于正整数$n$的命题。如果$P(1)$成立，且对任意正整数$k$，$P(m)$对任意正整数$m \le k$成立可以推出$P(k + 1)$成立，那么$P(n)$对任意正整数$n$成立。

第二数学归纳法允许我们在证明中采用更强的假设。数学归纳法还有其它的形式，都可以由良序原理或者已有的归纳法原理推导出来。