数列

· · 学习·文化课

7.1 数学归纳法

考虑证明命题 P(n) 对 n \ge n_0 的一切正整数 n 都成立。给出如下证明方法:

这一方法叫做第一数学归纳法,简称为数学归纳法。

下面再给出另一种归纳法,称作第二数学归纳法:

请读者体会两种方法的正确性所在。下面给出一些例题,帮助读者理解上述概念。

例题一:求证 \sum \limits_{i=1}^n i^2=\dfrac{n(n+1)(2n+1)}{6}。

:::::success[题解]

考虑第一数学归纳法,令命题 P(n) 为 \sum \limits_{i=1}^n i^2=\dfrac{n(n+1)(2n+1)}{6}。

当 n=1 时,等式左侧为 1,右侧为 \dfrac{1 \times 2 \times 3}{6}=1,故 P(1) 成立。

当 n=k 时,假定 P(k) 成立,于是

\begin{aligned} P(k+1) &\iff \sum_{i=1}^{k+1} i^2=\dfrac{(k+1)(k+2)(2k+3)}{6}\\ &\iff (k+1)^2+\sum_{i=1}^k i^2=\dfrac{(k+1)(k+2)(2k+3)}{6}\\ &\iff 6(k+1)^2 + k(k+1)(2k+1)=(k+1)(k+2)(2k+3)\\ &\iff 2k^2+7k+6=(k+2)(2k+3) \end{aligned}

显然成立。证毕。

::::::

例题二:记数列 a_n 满足 a_1=3,且 a_{n+1}=3a_n-4n,求 a_n 的通项公式。

:::::success[题解]

- $n=1$ 显然成立。 - 当 $n=k$ 时,假定 $a_k=2k+1$ 成立,于是 $$ \begin{aligned} a_{k+1}&=3a_k-4k\\ &=3(2k+1)-4k\\ &=2(k+1)+1 \end{aligned} $$ ::::: 例题三:求证 $n$ 个点的树必然有 $n-1$ 条边。 :::::success[题解] 考虑第二数学归纳法: - $n=1$ 时,原命题显然成立。 - $n=k$ 时,可以将原树断开一条边,分解成大小为 $k_1$ 和 $k_2$ 的两棵子树,其中 $1 \le k_1,k_2 \le k$。由归纳假设,原树的边数为 $k_1-1+k_2-1+1=k-1$。 ::::: ## 7.2 等差 / 等比数列 对于数列 $\{a_n\}$,若其满足递推公式 $a_{n+1}-a_n=d$,则称 $\{a_n\}$ 为**等差数列**,$d$ 为公差,$a_1$ 为首项。 记 $S_n=\sum \limits_{i=1}^n a_i$,则等差数列具有如下性质: - 通项公式:$a_n=a_1+(n-1)d$。 - 前缀和:$S_n=\dfrac{a_1+a_n}{2}n=a_1n+\dfrac{n(n-1)}{2}d$。 - 由以上两个基本公式得到的推论: - $a_n=a_m+(n-m)d$。 - 若 $m+n=p+q$,则 $a_m+a_n=a_p+a_q$。 - $S_{2n-1}=(2n-1)a_n$。 - 若干个等差数列的线性组合还是等差数列。 这些结论的证明很简单,这里不给出了。 对于数列 $\{a_n\}$,若其满足递推公式 $\dfrac{a_{n+1}}{a_n}=q$,则称 $\{a_n\}$ 为**等比数列**,$q$ 为公比,$a_1$ 为首项。 仍记前缀和为 $S_n$,并且忽略 $q=1$ 的平凡情形。我们有: - 通项公式:$a_n=a_1 \times q^{n-1}$。 - 前缀和:$S_n=\dfrac{q^n-1}{q-1}a_1$。 - 由以上两个基本公式得到的推论: - $a_n=a_m \times q^{n-m}$。 - 若 $m+n=p+q$,则 $a_m\times a_n=a_p\times a_q$。 下面给出等比数列前缀和的证明: :::::success[证明] 根据定义,我们有 $$ \begin{aligned} S_n&=a_1+a_1q+a_1q^{2}+\cdots +a_1 q^{n-1}\\ qS_n&=\phantom{a_1}+a_1q+a_1q^2+\cdots+a_1q^{n-1}+a_1 q^n \end{aligned} $$ 两式相减得 $(q-1)S_n=(q^n-1)a_1$,即证 $S_n=\dfrac{q^n-1}{q-1} a_1$。 ::::: 等比数列的结论被用来解决一些重要的通项问题。 ## 7.3 线性常系数齐次递推 ### 7.3.1 不动点 问题:给出递推公式 $a_{n+1}=pa_n+q$,其中 $p \ne 0 \land p\ne 1$,求 $a_n$ 的通项公式。 :::::success[题解] 构造**不动点** $x$ 满足 $x=px+q$,解得 $x=\dfrac{q}{1-p}$。 对递推式进行变形: $$ \begin{aligned} a_{n+1}&=pa_n+q\\ a_{n+1}-x &= pa_n+q-x\\ a_{n+1}-x &= p(a_n-x) \end{aligned} $$ 记 $b_n=a_n-x$,上式给出 $b_{n+1}=pb_n$,由等比数列通项公式得 $b_n=b_1 p^{n-1}$。因此 $a_n$ 的通项为 $$ a_n=(a_1-x) p^{n-1}+x $$ 其中 $x=\dfrac{q}{1-p}$。 ::::: ### 7.3.2 特征根 问题:给出递推公式 $a_{n+1}=pa_n+qa_{n-1}$,其中 $p,q \ne 0$,求 $a_n$ 的通项公式。 :::::success[题解] 类比一阶线性递推的解法,我们猜想这个数列的本质也是某种等比数列。 构造**特征根** $x$ 满足 $x^{n+1} =px^n+qx^{n-1}$,化简得 $x^2-px-q=0$。将这一方程称为数列的**特征方程**。 由 $\Delta=p^2+4q$ 判定方程根的分布后,将问题分为三类求解: - 若 $\Delta>0$,可解得方程的两根 $x_1,x_2$。 由韦达定理 $p=x_1 +x _2 \land q=-x_1x_2$,代入递推式得 $a_{n+1}=(x_1+x_2)a_n-x_1x_2 a_{n-1}$,即 $a_{n+1}=x_1a_n+x_2a_n-x_1x_2a_{n-1}$。继续变形: - $a_{n+1}-x_1a_n=x_2(a_n-x_1a_{n-1})$。令 $b_n=a_n-x_1 a_{n-1}$,则上式给出 $b_n=x_2b_{n-1}$,得 $b_n=(a_2-x_1a_1)x_2^{n-2} $,记为 $\tt{①}$ 式。 - $a_{n+1}-x_2a_n=x_1(a_n-x_2a_{n-1})$。令 $c_n=a_n-x_2a_{n-1}$,则上式给出 $c_n=x_1 c_{n-1}$,得 $c_n=(a_2-x_2a_1)x_1^{n-2}$,记为 $\tt{②}$ 式。 记常数 $C_1=x_2^{-2}(a_2-x_1a_1), C_2=x_1^{-2}(a_2-x_2a_1)$,考虑消去 $a_{n-1}$。 将 $x_2 \times {\tt{①}}-x_1 \times \tt{②}$ 得 $(x_2-x_1)a_n=C_1 x_2^{n+1}-C_2 x_1^{n+1}$。移项即可解出 $a_n$。 直接写出通解过于复杂,我们不妨给出 $a_n=Ax_1^n+Bx_2^n$ 的形式,其中 $A,B$ 是一个常数。在实际应用中,根据这个形式可以较为快速地得到 $A,B$。 - 若 $\Delta=0$,方程有两个相等的实数根 $x_0$。 由韦达定理 $p=2x_0 \land q=-x_0^2$,代入递推式得 $a_{n+1}=2x_0a_n+x_0^2a_{n-1}$。 移项整理易知 $a_{n+1}-x_0a_n=x_0(a_n-x_0a_{n-1})$,令 $b_n=a_{n+1}-x_0a_n$,上式给出 $b_n=x_0 b_{n-1}$,得 $b_n=(a_2-x_0a_1)x_0^{n-1}$。 代回定义式后,将等式两边同时除以 $x_0^n$ 得 $\dfrac{a_n}{x_0^n}-\dfrac{a_{n-1}}{x_0^{n-1}}=\dfrac{a_2-x_0a_1}{x_0^2}$。 记 $c_n=\dfrac{a_n}{x_0^n}$ 且 $B=\dfrac{a_2-x_0a_1}{x_0^2}$,可得 $c_n-c_{n-1}=B$。由等差数列通项公式 $c_n=c_1+(n-1)B$。记 $A=c_1-B$ 得 $c_n=A+Bn$。 代回 $c_n$ 的定义式,最终我们得到 $a_n=(A+Bn)x_0^n$ 的形式,其中 $A,B$ 是一个常数。 - 若 $\Delta<0$,方程有两个共轭虚根,记其中一解为 $re^{i \theta}$。 这里的推导比较复杂,我们直接给出结论:$a_n=r^n(A \cos n \theta + B \sin n \theta)$,其中 $A,B$ 是一个常数。 ::::: 一般地,对于数列 $a_n$,若其满足 $$ a_n+C_1a_{n-1}+C_2a_{n-2}+\cdots+C_k a_{n-k}=0 $$ 且 $C_1 \sim C_k$ 和 $a_1 \sim a_k$ 是常数,则称 $a_n$ 满足 $k$ 阶线性常系数齐次递推。 使用 OGF 的观点,可以考虑构造**特征多项式** $$ C(x)=x^k+C_1 x^{k-1}+\cdots+C_{k-1}x+C_{k}=x^k+\sum_{i=1}^k C_i x^{k-i} $$ 并且仍分 $C(x)$ 无重根,有重根,有共轭复根的情形讨论。通解超出了 OI 的需要,感兴趣的读者请自行查阅资料。 ### 7.3.3 斐波那契数列 斐波那契数列 $F_n$ 由如下递推关系定义 $$ F_n=F_{n-1}+F_{n-2} $$ 边界情况为 $F_0=0, F_1=1, F_2=1$。 斐波那契是特殊的二阶线性常系数齐次递推,因此我们可以用特征根的方法求通项: :::::success[推导] 构造特征根 $x$ 满足 $x^2-x-1=0$。解得 $x_1=\dfrac{1 + \sqrt{5}}{2},x_2=\dfrac{1 - \sqrt{5}}{2}$。 根据二阶齐次线性递推的结论,可以设通项为 $F_n=Ax_1^n +Bx_2^n$。只需确定常数 $A,B$。 - 当 $n=0$ 时,$F_0=A+B=0$。 - 当 $n=1$ 时,$F_1=Ax_1+Bx_2=1$。 解方程组知 $A=\dfrac{\sqrt{5}}{5}, B=-\dfrac{\sqrt{5}}{5}$。 ::::: 得到通项公式为 $$ F_n=\dfrac{1}{\sqrt{5}} \left( \left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right) $$ 在 OI 中,斐波那契数往往需要在 $\mathbb{Z}_p$ 中计算。如果 $5$ 在模 $p$ 意义下没有二次剩余,我们还需要扩域,即引入 $i$ 并强行令 $i^2 \equiv 5 \pmod p$,然后用形如 $a+bi$ 的数进行求解。复杂度瓶颈在于求 $n$ 次方。 下面给出一些与斐波那契相关的组合恒等式,也可以称之为 $F_n$ 的性质: - Cassini 恒等式: $$ F_{n-1}F_{n+1}-F_n^2=(-1)^n $$ - 加法公式: $$ F_{m+n}=F_{m+1}F_n+F_mF_{n-1} $$ - GCD 性质: $$ F_{\gcd(n,m)}=\gcd(F_n, F_m) $$ - Zeckendorf 定理:任意自然数 $n$ 可以被唯一表示为若干不相邻斐波那契数的和,即 $$ n=F_{i_1}+F_{i_2}+\cdots+F_{i_k}\\ $$ 将斐波那契数作为底数,就得到又一种记数法。Zeckendorf 定理指出,一个自然数具有唯一的**斐波那契编码**。 求编码的过程是朴素贪心。每轮中,我们找到不超过 $n$ 的最大斐波那契数 $F_i$,将 $i$ 加入编码并令 $n \gets n-F_i$。解码直接相加即可。 斐波那契编码的长度为 $O(\log n)$ 级别。在一些构造题中,使用斐波那契编码会比二进制编码更有优势。 ## 7.5 多边形数 **三角形数** $P_3(n)$ 的几何意义是下图中第 $n$ 个图形的点数。 ![](https://cdn.luogu.com.cn/upload/image_hosting/07va9kww.png) 根据几何直观,容易得到递推式 $P_3(n)=P_3(n-1)+n$。由累加法求和即得通项 $P_3(n)=\dfrac{n(n+1)}{2}$。 自然地,将图形变成正方形,就得到了**四边形数** $P_4(n)$ 的几何意义: ![](https://cdn.luogu.com.cn/upload/image_hosting/g8o28c14.png) 递推式 $P_4(n)=P_4({n-1})+2n-1$,通项式 $P_4(n)=n^2$。因此四边形数又被称为平方数列。 类似地还有**五边形数**:递推式 $P_5(n)=P_5(n-1)+3n-2$,通项式 $P_5(n)=\dfrac{n(3n-1)}{2}$。 将 $P_5$ 的定义域由 $\mathbb{N}^{+}$ 扩展到 $\mathbb{N}$,仍然沿用通项式计算,称这样的 $P_5(n)$ 为**广义五边形数**。在 $n=1,-1,2,-2,3,-3,\cdots$ 时,五边形数数列为 $1,2,5,7,12,15,22,26,\cdots$。 一般地,我们有 $k$ 边形数 $P_k(n)$,其满足: - 递推式 $P_k(n)=P_k(n-1)+(k-2)(n-1)+1$。 - 通项式 $P_k(n)=\dfrac{(k-2)n^2-(k-4)n}{2}=(k-2)P_3(n-1)+n$。 **费马多边形数定理**指出,每个正整数都可以表示为最多 $k$ 个 $k$ 边形数的和。 一个特殊情形是**拉格朗日四平方和定理**,即每个正整数都可以表示为四个完全平方数的和。 ## 7.6 调和级数 调和级数是 OI 中常见的数列。记 $$ H_n=\sum_{i=1}^n \dfrac{1}{i} $$ 数列 $H_n$ 被称作**调和级数**。随着 $n \to +\infty$,$H_n \to +\infty$,即 $H_n$ 发散,这是相当经典的结论。事实上,$H_n$ 的级别为 $O(\log n)$。 使用微积分的方法,可以得到结论:$\sum \limits_{i=1}^n H_i=O(n \log n)$。考虑如下流程的算法: ```cpp line-numbers for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j += i); ``` 根据上述结论,该算法的复杂度为 $O(n \log n)$ 级别,称这一技巧为调和型枚举。 对于和式 $\sum \limits_{i=1}^n \frac{1}{i^k}$,可以证明其收敛当且仅当 $k>1$。取 $k=1$ 即为调和级数,取 $k=2$ 则得到著名的 Basel 问题: $$ \sum_{i \ge 0} \dfrac{1}{i^2}=\dfrac{\pi^2}{6} $$