你学算法可能要用的数学知识（1）——求和与求积

Matrix_J · 2025-11-22 21:48:21 · 算法·理论

问题是数学的心脏。——哈尔莫斯

update

upd on 2025/11/23: 经过再三考虑，加入如何计算级数界的一章。

upd on 2025/11/26 & 2025/11/27: 修改了几个笔误和错别字。

前言

本章为该系列的第一章，该系列共有四章，主要讲述学 OI 需要的一下数学知识。不定期更新。

本章主题为求和与求积。

:::warning[提醒]{open}

再看例子之前，先自己尝试用之前介绍的方法或自己已知的方法来解题，在看例子。

::::

引言

当一个算分中包含如 while 或 for 等的循环结构，我们可以将算法的运行时间表示为每一次执行循环体所用的时间之和，进而可以计算时间复杂度。例如可以计算出下面这段代码：

for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
        ans+=a[i][j];

的时间复杂度是 O(n^2) 的。

求和

给定一个有限数列 a_1,a_2,\dots,a_n，其中 n 是非负整数，则

a_1+a_2+\dots+a_n=\sum\limits_{i=1}^n a_i

显然的，若 n=0，那么该式值为零。

给定一个无限数列 a_1,a_1,\dots，则

a_1+a_2+\dots=\sum\limits_{i=1}^\infty a_i

也可写作 \lim\limits_{n\to\infty}\sum\limits_{i=1}^n a_i。

当其极限不存在时，该级数发散；存在时，收敛。（级数指一列属的求和）

线性性质

对于任意实数 k 和有限序列 \{a_n\}，都有

\sum\limits_{i=1}^n {ka_i}=k\sum\limits_{i=1}^n a_i

对于任意两个有限序列 \{a_n\} 和 \{b_n\}，都有

\sum\limits_{i=1}^n {(a_i+b_i)}=\sum\limits_{i=1}^na_i+\sum\limits_{i=1}^nb_i

线性性质可以用来对项中包含渐进符号的何时进行求和，如

\sum\limits_{i=1}^n {O(f(i))}=O(\sum\limits_{i=1}^n {f(i)})

一堆和的公式

等差级数

如果一个数列 \{a_n\}，从第一项 a_1 开始，以后每一项都是前一项加上一个固定的数 d，即

a_1,a_1+d,a_1+2d,\dots,a_1+(n-1)d

对于这个数列，我们称之为等差数列，将 d 称为公差。

对等差数列中的各项求和，得：

\begin{aligned} S_n = \sum\limits_{i=1}^na_i &=na_1+\frac{n(n-1)}{2}d \\ &=\frac{1}{2}(a_1+a_n)n\end{aligned}

称为等差级数。

特别的，当 a_1=1 且 d=1 时，有

\sum\limits_{i=1}^ni=\frac{1}{2}n (n+1)

平方数和立方数和公式

这里直接给出结论：

\sum\limits_{i=1}^n{i^2}=\frac{n(n+1)(2n+1)}{6}

\sum\limits_{i=1}^n{i^3}=\frac{n^2(n+1)^2}{4}

等比级数（又称几何级数）

如果一个数列 \{a_n\}，从第一项 a_1 开始，以后每一项都是前一项乘上一个固定的数 q，即

a_1,a_1q,a_1q^2,\dots,a_1q^{n-1}

对于这个数列，我们称之为等比数列，将 d 称为公比。

对等差数列中的各项求和，得：

S_n = \sum\limits_{i=1}^na_i=a_1\frac{q^n-1}{q-1} (q\ne1)

称为等比级数。

特别的，当 \left\vert x\right\vert<1 时，有

\sum\limits_{i=0}^\infty x^i=\frac{1}{1-x}

调和级数

对于正整数 n，第 n 个调和数式是

H_n=1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}=\sum\limits_{i=1}^n\frac{1}{i}=\ln(n+1)+C

其中 C 为一个常数。

利用该式可以知道下面这段代码：

for(int i=1;i<=n;++i)
    for(int j=1;j<=n/i;++j) 
        ++ans;

时间复杂度式是 O(n\log n) 的。

求积

有限积 a_1a_2\dots a_n 可以写作

\prod\limits_{i=1}^na_i

当 n=0 时，该式为 1。

求值和证明的一些方法

变形

即将一个项分成另一种形式，使之能够与其他项消掉。下面分别举一个求和与一个求积的例子。

:::success[eg1]

考虑

\sum\limits_{i=1}^{n-1}\frac{1}{i(i+1)}

::::info[answer]

可以将每一项改写成

\frac{1}{i(i+1)}=\frac{1}{i}-\frac{1}{i+1}

所以可得

\sum\limits_{i=1}^{n-1}\frac{1}{i(i+1)}=\sum\limits_{i=1}^{n-1}(\frac{1}{i}-\frac{1}{i+1})=1-\frac{1}{n}

:::

:::success[eg2]

考虑

\prod\limits_{i=2}^n(1-\frac{1}{i^2})

::::info[answer]

可以将每一项写成

1-\frac{1}{i^2}=\frac{i^2-1}{i^2}=\frac{(i-1)(i+1)}{i^2}

所以可得

\prod\limits_{i=2}^n(1-\frac{1}{i^2})=\prod\limits_{i=2}^n\frac{(i-1)(i+1)}{i^2}=\frac{\prod_{i=3}^{n-1}i^2}{\prod_{i=2}^{n}i^2}\times2n(n+1)=\frac{n+1}{2n}

:::

数学归纳法

数学归纳法是证明关于正整数 n 的命题 P(n) 成立与否时经常使用的方法，它是下面的归纳公理的一个直接推论：

归纳公理

设 S 是正整数集的一个子集，满足条件：

若 n \in S，则 n+1 \in S。

那么 S 与正整数集相等。

归纳公理式由皮亚诺提出的关于正整数的五条公理中的一条，它是数学归纳法的基础。

下面是我们常用的第一数学归纳法：

第一数学归纳法

设 P(n) 是关于正整数 n 的一个命题（或性质），如果

当 n=1 时，P(n) 成立；
由 P(n) 成立可以推出 P(n+1) 成立。

那么对于任意正整数 n，P(n) 都成立。

举个例子：

:::success[eg3]

正实数数列 \{a_n\} 满足 a_n^2 \leqslant a_n-a_{n+1}，n=1,2,\dots。证明：对任意正整数 n，都有 a_n<\frac{1}{n}。

::::info[answer]

当 n=1，a_1 \le a_1-a_2<a_1，故 a_1<1，同时，a_2 \le a_1-a_1^2=\frac{1}{4}-(a_1-\frac{1}{2})^2 \le \frac{1}{4}<\frac{1}{2}。因此，命题对 n=1,2 成立。

现设命题对 n(n\ge2) 成立，则 a_{n+1} \le a_n-a_n^2=\frac{1}{4}-(a_n-\frac{1}{2})^2。~~注意到~~，由归纳假设知 a_n<\frac{1}{n}\le\frac{1}{2}，所以 \frac{1}{2}-a_n>\frac{1}{2}-\frac{1}{n}\ge0，因此 a_{n+1}<\frac{1}{4}-(a_n-\frac{1}{2})^2=\frac{n-1}{n^2}<\frac{1}{n+1}，即命题对 n+1 成立，得证。

:::

读者可以自己尝试一下用数学归纳法推导等差数列求和公式。

显然有第二数学归纳法，读者可以自行探索，原理几乎无异（主观上）。

计算级数界

有时我们不要级数的精确值，而是需要某个级数的界。而有很多方法可以用来求级数的界，包括上面的数学归纳法。这里介绍几个方法。

计算各项的界

有时，可以通过求级数中每一项的界，就可以获得该级数一个理想的界。通常可以用级数中最大的项作为其他项的界。下面是一个例子：

\sum\limits_{i=1}^ni\le\sum\limits_{i=1}^nn=n^2

通常，对于级数 \sum\limits_{i=1}^na_i，如令 A=\max\limits_{1\le i \le n}a_i，则有

\sum\limits_{i=1}^na_i\le nA

当一个级数能以等比级数为界时，用级数中最大的数最为每一项的界并不理想。给定级数 \sum\limits_{i=0}^na_i，满足对于所有 i\ge0，都有 \frac{a_{i+1}}{a_i}\le q，其中 0<q<1 是常数。由上式可得，a_i<a_0q^i，则我们可以用无限递减级数作为和的界：

\sum\limits_{i=0}^na_i\le a_0\sum\limits_{i=0}^\infty q^i=a_0\frac{1}{1-q}

注意：q 是常数,下面举一个错误的例子：

考利无限调和级数 \sum\limits_{i=1}^\infty \frac{1}{i}，虽然相邻项之比小于 1，但可知该级数发散：

\sum\limits_{i=1}^\infty \frac{1}{i}=\lim\limits_{n\to\infty}\sum\limits_{i=1}^n\frac{1}{i}=\lim\limits_{n\to\infty}(\ln(n+1)+C)

显然发散。

分割求和

正如其名，可将一个级数按下标的范围划分为多个级数的和，并分别对每个级数进行求界操作。

下面给一个例子：

:::success[eg4]

我们可确定调和级数 H_n=\sum\limits_{i=1}^n\frac{1}{i} 的界。

::::info[answer（一种近似）]

将下标范围 1 到 n 分成 \lfloor\log_{2}{n}\rfloor+1 段，对于第 i(0\le i \le \lfloor\log_{2}{n}\rfloor) 段，包含自 \frac{1}{2^i} 至 \frac{1}{2^{i+1}} （不含）的项（这里取 0 至 \lfloor\log_{2}{n}\rfloor，而不是取 1 到 \lfloor\log_{2}{n}\rfloor+1 是因为区间数后面更好表示），最后一段可能包含一段原没有的数，因此可通过计算每一段的界来求：

\sum\limits_{i=1}^n\frac{1}{i}\le\sum\limits_{i=0}^{\lfloor\log_{2}{n}\rfloor}\sum\limits_{j=0}^{2^i-1}\frac{1}{2^i+j}\le\sum\limits_{i=0}^{\lfloor\log_{2}{n}\rfloor}\sum\limits_{j=0}^{2^i-1}\frac{1}{2^i}=\sum\limits_{i=0}^{\lfloor\log_{2}{n}\rfloor}1\le\log_{2}{n}+1

:::

对于算法分析中的和式，通常可以将和式分割，并忽略其分割出的常数项，此处不再赘述。

积分求和近似

:::warning[警告]{open}

以下内容需要一定的微积分基础，不熟悉的读者可以跳过。

:::

考虑和式 \sum\limits_{x=m}^n f(x)，其中 f(x) 是一单调递增函数，则我们可以通过积分给出上下界：

\int_{m-1}^nf(x)\,dx\le\sum\limits_{x=m}^n f(x)\le \int_m^{n+1}f(x)\,dx

由于积分表示函数下方与坐标轴的面积，读者可以自己尝试画图证明。

若该函数单点递减，只需将符号反过来即可。

:::success[eg5]

考虑第 n 个调和数。

::::info[answer]

现在对第 n 个调和数进行估计：

由于

\int_1^{n+1}\frac{1}{x}\,dx=\ln(n+1)

且利用分割求和

\sum\limits_{i=2}^n\frac{1}{i}\le\int_1^n\frac{1}{x}\,dx=\ln(n)

故

\ln(n+1)\le H_n=\sum\limits_{i=2}^n\frac{1}{i}+1\le\ln(n)+1

:::

还有另一种积分近似方法：

若 f(x) 是在 \frac{1}{2} 到 n+\frac{1}{2} 之间的二阶可导函数，且 f''(x)>0，则

\sum\limits_{x=1}^{n}f(x)<\int_{\frac{1}{2}}^{n+\frac{1}{2}}f(x)\,dx

当 f''(x)>0 时，将符号反过来即可。

这里不做解释。

参考文献

《算法导论》
百度关于级数的说明等等（详见文章）
数学奥林匹克小丛书高中卷《数列与数学归纳法》
几类求和的积分放缩 by 靉靅浮雲

后记

预告：集合等离散数学内容（也不知道啥时候会出雾）

这篇是于笔者期中考试后完成的，想在这里发表一下自己的感想：

监考老师神人，年段第二科技。这咋考得过嘛！

还是那句话：做干净的奥赛，做干净的人。

谢谢你看到这里，若有问题或者改进建议可以在下面提出，我会尽可能地回答。

Wait,why?