如何证明log(3𝑛³+2𝑛+17) = Θ(log(15𝑛⁵+7𝑛⁴−2))

核心前提回顾 #

要证明 f(n) = Θ(g(n))，需要找到正的常数 c1、c2和正整数n0，使得对所有 n ≥ n0`，满足：

c1 * g(n) ≤ f(n) ≤ c2 * g(n)

本题中：

• f(n) = log(3n³ + 2n + 17)
• g(n) = log(15n⁵ + 7n⁴ − 2)

正确证明思路 #

步骤1：确定对数内多项式的渐近上下界 #

对数是严格单调递增函数，所以我们可以先确定对数内部多项式的范围，再套入对数运算。
对足够大的 n（此处可取 n0 ≥ 3），可以得到如下不等式：

• 对f(n)的内部多项式：
  3n³ ≤ 3n³ + 2n + 17 ≤ 3n³ + 2n³ + 17n³ = 22n³
  （原理：n ≥ 1 时，2n ≤ 2n³、17 ≤ 17n³）
• 对g(n)的内部多项式：
  15n⁵ ≤ 15n⁵ + 7n⁴ − 2 ≤ 15n⁵ +7n⁵ = 22n⁵
  （原理：n ≥ 2 时，7n⁴ ≤ 7n⁵，常数项-2不影响上界，且多项式结果为正）

步骤2：对不等式两边取对数 #

因为对数单调递增，不等号方向不变，展开后得到：

• f(n)的范围：
  log(3n³) ≤ f(n) ≤ log(22n³)
  即 log3 + 3logn ≤ f(n) ≤ log22 + 3logn
• g(n)的范围：
  log(15n⁵) ≤ g(n) ≤ log(22n⁵)
  即 log15 + 5logn ≤ g(n) ≤ log22 + 5logn

步骤3：关联f(n)和g(n)的阶数 #

当 n 足够大时，对数的常数项会远小于logn项，可以忽略，因此：

• f(n) 和 3logn 同阶，即 f(n) = Θ(logn)
• g(n) 和 5logn 同阶，即 g(n) = Θ(logn)
  二者都和logn同阶，因此二者互为Θ关系成立。

严格不等式验证（可直接用于证明 #

上界验证（f(n) ≤ c2 * g(n)） #

取c2 = 2，当n ≥ 3时：
f(n) ≤ log22 + 3logn ≤ 3logn + 3logn = 6logn
同时g(n) ≥ log15 +5logn ≥5logn，即logn ≤ g(n)/5
代入得f(n) ≤ 6 * (g(n)/5) = 1.2 g(n) ≤ 2g(n)，上界成立。

下界验证（c1 * g(n) ≤ f(n)） #

取c1 = 0.2，当n ≥3时：
f(n) ≥ log3 + 3logn ≥ 3logn
同时g(n) ≤ log22 +5logn ≤ 5logn +5logn = 10logn，即logn ≥ g(n)/10
代入得f(n) ≥ 3 * (g(n)/10) = 0.3 g(n) ≥ 0.2g(n)，下界成立。 #

原有思路说明 #

你之前想的「对两边取2的幂看内部多项式」的思路方向是对的：因为当n足够大时，两个多项式都大于1，对数单调递增，若两个正函数同阶，它们的对数也同阶，只是不能直接跳步，需要补充上述的常数项和阶数推导即可。 #

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