求证5n²+2n-1是O(n²)（n≥1）：我的证明是否正确？

你的证明确实存在漏洞，咱们一步步拆解问题出在哪，再给出严谨的推导过程。

先回顾大O符号的正式定义 #

若函数$f(n)$是$O(g(n))$，则需要找到两个常数：$C>0$和$n_0 \geq 1$，使得对于所有$n \geq n_0$，都有$|f(n)| \leq C|g(n)|$。
因为这里$n \geq 1$，所有项都是正数，所以可以去掉绝对值，只需要证明$5n^2 + 2n -1 \leq Cn^2$对所有$n \geq n_0$成立。

你的推导错在哪里？ #

你写的$5n^2 +2n -1 <5n^2 +2n$这一步是对的，但接下来直接跳去说$5n^2 -1 <5n^{2$完全没抓住重点——$5n}2 +2n$是严格大于$5n^{2$的，你没法从$5n}2 +2n -1 <5n^2 +2n$直接推导出它小于$5n^2$，这中间跳过了最关键的一步：处理掉$2n$这个额外的项。
而且你得出的$C=5$根本不成立：当$n \geq1$时，$5n^2 +2n -1 =5n^2 + (2n-1)$，而$2n-1 \geq1>0$，所以$5n^2 +2n -1$总是比$5n^{2$大，不可能满足$5n}2 +2n -1 \leq5n^2$，这是核心错误。

正确的推导过程 #

我们需要把$2n$转化为$n^{2$的倍数，这样才能合并到$n}2$的项里：

• 当$n \geq1$时，$n \leq n^2$（两边乘$n$，$n\geq1$时不等号方向不变），因此$2n \leq 2n^2$。
• 代入原式可得：
  $$
  5n^2 +2n -1 \leq5n^2 +2n^2 -1 =7n^2 -1
  $$
• 又因为$n\geq1$时，$7n^2 -1 \leq7n^{2$（减去负数只会让左边更小），所以对于所有$n\geq1$，都有$5n}2 +2n -1 \leq7n^2$。

这时候我们就找到了符合要求的常数：$C=7$，$n_0=1$，完美满足大O的定义。

如果你想选更小的$C$，可以调整$n_0$：
比如取$n_0=2$，当$n\geq2$时，$2n \leq n^{2$（因为$n\geq2$时，$n}2-2n=n(n-2)\geq0$），那么：
$$
5n^2 +2n -1 \leq5n^2 +n^2 -1=6n^2 -1 \leq6n^2
$$
这时候$C=6$，$n_0=2$也成立。

总结 #

你的推导忽略了对$2n$项的处理，错误地认为$C=5$可行，实际上$C$必须大于5，搭配对应的$n_0$才能满足大O的定义。

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