我试图证明 k（n ^ 2）不是2 ^ n 的大欧米茄，其中 k 是正数实数。我看过大欧米茄的否定。因此，我试图找到一个大于或等于某个 n0 的 n ，该 n0 也满足 k （ n ^ 2） n ） c 其中 c 是一个正实数。
我尝试选择n = 2 ^ n0 的n，这使 n ^ 2 = 2 ^ n 成为问题是为了使不等式起作用， k 必须小于 c ，而我不能选择 k 和 c 是。我试图通过取双方的对数来解决不等式中的n，但最终得到log（ b ）-log（ c ） n ）+ n log（2），在这种情况下，我也不确定如何隔离 n 。任何提示将不胜感激
要获得真实的证明，请始终以 开头。
k（n ^ 2）是OMEGA（2 ^ n）当且仅当存在两个常数c> 0和d> 0时，对于所有n> d，k（n ^ 2）> c （2 ^ n）。
要证明是负面的，您几乎总是会尽力使用矛盾。假设您要证明的是 true ，并据此从逻辑上推论一个显然是错误的断言。
因此，假设k（n ^ 2）是OMEGA（2 ^ n），因此确实存在如上所述的c和d。
那我们知道
For all n > d,n^2 > (c/k)(2^n)
和
For all n > d,2 log_2 n > log_2(c/k) + n
要显示这一点很荒谬，请选择n = c / k。
如果您确实想透彻一点，其余的内容将由代数加上一些微积分。我让你解决。 Hint。
,假设kn ^ 2是Omega（2 ^ n）。然后，对于n> = n0和正常数c，k * n ^ 2> = c * 2 ^ n。除以RHS（我们可以做，因为它必须为正数），我们得到（k / c）n ^ 2/2 ^ n> =1。考虑到n接近无穷大，LHS的极限：
lim(n->inf) (k/c)n^2/2^n LHS
= (k/c) lim(n->inf)n^2/2^n lim cf(x) = c lim f(x)
= (k/c) lim(n->inf)2n/((ln2)2^n) l'Hopital's rule
= (k/c)(2/ln2) lim(n->inf)n/2^n lim cf(x) = c lim f(x)
= (k/c)(2/ln2) lim(n->inf)1/((ln2)2^n) l'Hopital's rule
= (k/c)(2/(ln2)^2) lim(n->inf)1/2^n lim cf(x) = c lim f(x)
= 0 lim 1/f(x) = 0 if lim f(x) -> inf
LHS增加n的极限为零。因此，对于零附近的任何间隔，都有一个n，它将使LHS的值处于该间隔内。选择间隔为0.5。然后有一个n使不等式成立。剩下的一切只是为了证明LHS代表n的单调递减函数。我们可以计算出导数：
d/dn (k/c)n^2/2^n LHS
= (k/c) d/dn n^2/2^n d/dx cf(x) = c d/dx f(x)
= (k/c) d/dn (n^2)(2^-n) 1/2^x = 2^-x
= (k/c) (d/dn n^2)(2^-n) + (n^2)(d/dn 2^-n) product rule of differentiation
= (k/c) (2n)(2^-n) + (n^2)((-ln2)(2^-n)) d/dx x^k = kx^(k-1),chain rule
= (k/c) [(-ln2)n^2 + 2n]/(2^n) algebraic rearrangement
每当（-ln2）n ^ 2 + 2n (-ln2)n^2 + 2n < 0
((-ln2)n + 2)n < 0
(-ln2)n + 2 < 0
(ln2)n > 2
n > 2/ln(2)
这意味着至少对于n> 4，该函数单调递减。如果假定的n0大于4，则没有问题。如果假设n0小于4，我们可以自由地将n0分配给n0'= 5，因为只要可行，n0的选择就不重要了。