求证(n+2)/2^n=Θ(1)：分母增速大于分子是否必为Θ(1)

• “分母增长速率大于分子就属于Θ(1)”的说法完全没有普适性，本质是对渐近符号的典型误解：它只记住了Θ(1)要求函数有固定上界，完全漏掉了Θ(1)必须同时满足存在固定正下界的核心约束。
• 你提到的1/n就是最直接的反例：分母n是线性增长，分子是常数，确实满足分母增长更快，但1/n会随着n增大无限接近0，根本找不到一个固定的正下界能覆盖所有足够大的n，自然不属于Θ(1)。
• 只要分式最终会无限趋近于0，不管分母是多项式还是指数式，都不满足Θ(1)的要求，和分母增长速度的量级无关。

先列不带极限的Θ(1)严格定义：

f(n)=Θ(1) 等价于存在三个固定的正实数c1、c2、n0，对所有n≥n0的整数n，同时满足：

• f(n) ≤ c2 （固定上界）
• f(n) ≥ c1 （固定正下界）

下面用数学归纳、递推比值的方法分别验证两个条件，全程不涉及极限运算：

上界验证 #

• 对所有n≥1，n+2 ≤3n恒成立：n≥1时2≤2n，两边加n即可推导。
• 数学归纳法证明对所有n≥1，2^n ≥2n恒成立：
  • 基例n=1：左边2^1=2，右边2*1=2，等式成立
  • 归纳步骤：假设n=k时2^{k≥2k成立，则n=k+1时2}(k+1)=2*2^k≥4k；k≥1时4k -2(k+1)=2k-2≥0，即4k≥2(k+1)，归纳成立。
• 代入f(n)可得：f(n)=(n+2)/2^n ≤3n/(2n)=1.5。取c2=1.5、n0=1，即可满足上界要求。

下界验证 #

• 计算相邻两项的递推比值：f(n+1)/f(n) = (n+3)/(2(n+2))。n≥1时，这个比值最大为n=1时的2/3<1，说明f(n)从n=1开始是严格递减的正序列，每一项最多是前一项的2/3。
• 对任意给定的正c1>0，只要n足够大，严格递减的序列值一定会低于c1：比如c1=0.0625，n=8时f(8)=10/256≈0.039<0.0625；哪怕取非常小的c1=0.001，也能找到对应的n让f(n)跌破这个阈值。
• 结论：不存在任何固定的正c1能满足对所有足够大的n，f(n)≥c1。因此(n+2)/2^n根本不属于Θ(1)范畴，之前“分母增长更快所以符合Θ(1)”的解释是完全错误的——这个函数和1/n一样，只是趋近于0的速度更快而已，本质上都不满足Θ(1)的正下界要求。

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