关于f(n)=O(g(n))能否推出求和式同阶的疑问及反例寻求

问题1：已知$f(n) \leq g(n)$，是否可推出$\sum_{n=1}^\infty f(n) \leq \sum_{n=1}^\infty g(n)$？ #

这个结论的成立与否需要分情况讨论：

• 当两个级数都收敛（和为有限实数）：
  对任意正整数$N$，部分和$S_N = \sum_{n=1}^N f(n) \leq \sum_{n=1}^N g(n) = T_N$。根据极限的保序性，当$N \to \infty$时，$\lim_{N \to \infty} S_N \leq \lim_{N \to \infty} T_N$，也就是$\sum_{n=1}^\infty f(n) \leq \sum_{n=1}^\infty g(n)$，此时结论成立。

• 当级数发散时（考虑扩展实数系）：
  如果我们允许用$\infty$或$-\infty$表示发散级数的和，那么：

  • 若$\sum f(n)$发散到$+\infty$，则由于每个$S_N \leq T_N$，$T_N$也必须发散到$+\infty$（否则$T_N$有上界，$S_N$也会有上界，不可能发散到$+\infty$），此时$\infty \leq \infty$在扩展实数系中是成立的；
  • 若$\sum g(n)$发散到$-\infty$，同理$\sum f(n)$也会发散到$-\infty$，$-∞ ≤ -∞$成立；
  • 若$\sum f(n)$收敛到有限值，$\sum g(n)$发散到$+\infty$，则有限值$≤ ∞$成立；
  • 若$\sum g(n)$收敛到有限值，$\sum f(n)$不可能发散到$+\infty$（否则$S_N$会超过$T_N$的上界），只会收敛或发散到$-∞$，此时$-∞ ≤$有限值成立。

• 不考虑扩展实数系时：
  如果级数发散，其和不存在，此时不等式没有意义。只有当两个级数都收敛时，结论才成立。

问题2：$f(n) = O(g(n))$是否能推出$\sum f(n) = O(\sum g(n))$？调换结论两边呢？ #

原结论：$f(n) = O(g(n)) \implies \sum_{k=1}^n f(k) = O\left(\sum_{k=1}^n g(k)\right)$ #

对于非负函数（题目中$f,g:ℕ→ℝ^+$），这个结论是成立的，推导如下：

由$f(n)=O(g(n))$，存在常数$c>0$和$m>0$，使得对所有$n>m$，$f(n) ≤ c \cdot g(n)$。那么对于任意$n>m$，部分和：
$$
\sum_{k=1}^n f(k) = \sum_{k=1}^m f(k) + \sum_{k=m+1}^n f(k) ≤ \sum_{k=1}^m f(k) + c \cdot \sum_{k=m+1}^n g(k)
$$
令$K = \sum_{k=1}^m f(k)$（常数），则：
$$
\sum_{k=1}^n f(k) ≤ K + c \cdot \sum_{k=1}^n g(k)
$$
当$n$足够大时，$\sum_{k=1}^n g(k)$要么收敛到有限值（此时$\sum f(k)$也收敛，显然满足大O关系），要么趋向$+\infty$（此时$K/\sum g(k) \to 0$，因此存在常数$C>c$，使得$\sum f(k) ≤ C \cdot \sum g(k)$）。因此$\sum_{k=1}^n f(k) = O\left(\sum_{k=1}^n g(k)\right)$成立。

调换结论两边：$\sum_{k=1}^n f(k) = O\left(\sum_{k=1}^n g(k)\right) \implies f(n) = O(g(n))$ #

这个结论是不成立的，我们可以构造反例：

令：

• $f(n) = \begin{cases}
  n & \text{当}n\text{为奇数} \
  1 & \text{当}n\text{为偶数}
  \end{cases}$
• $g(n) = \begin{cases}
  1 & \text{当}n\text{为奇数} \
  n & \text{当}n\text{为偶数}
  \end{cases}$

计算部分和：

• $\sum_{k=1}^n f(k)$：当$n$为偶数时，等于$\sum_{i=1}^{n/2} (2i-1) + \sum_{i=1}^{n/2}1 = \frac{n^2}{4} + \frac{n}{2} = O(n^2)$；
• $\sum_{k=1}^n g(k)$：当$n$为偶数时，等于$\sum_{i=1}^{n/2}1 + \sum_{i=1}^{n/2}2i = \frac{n}{2} + \frac{n(n+2)}{4} = O(n^2)$。

显然$\sum f(k) = O(\sum g(k))$，但$f(n)$不是$O(g(n))$：当$n$为奇数时，$f(n)=n$，$g(n)=1$，此时$\frac{f(n)}{g(n)}=n \to \infty$，不满足大O符号的定义（不存在常数$c>0$使得$n ≤ c \cdot 1$对所有足够大的奇数$n$成立）。

内容的提问来源于stack exchange，提问作者james