学习笔记·数列

数列

数列（sequence）是数字的序列。一般来说，数列是一个定义在正整数集的子集上的函数，记\(a_{n} = f(n)\)，则数列可以表示为\(\{a_{n}\}\)。数列中的每一个数称为数列的项（term），\(a_{1}\)称为数列的首项。定义在无限集合上的数列叫做无穷数列（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\)成立。

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