math - 作业：证明 n <= 2^(n/4)？

Question

所以我有一个作业问题，我必须证明：

n^4 is in O(2^n)

仅通过查看函数图，我就知道在 c=1 和 n[0] = 16 时这是正确的。

在试图在纸上证明它时，我设法将不等式降低到n <= 2^(n/4)，但是，我无法弄清楚如何进一步简化它或从这里充分证明 n[0]=16 的大O断言成立。

有什么帮助吗？

Answer 1

标题不正确，错误很重要。

您不是要证明 n ≤ 2 ^n/4，而是要证明 n ∊ O(2 ^n/4 )，这是一个严格较弱的主张。不可能证明 n ≤ 2 ^n/4因为在 n=2 时，不等式是错误的。

通过取两边的对数，我们可以将问题简化为显示 log n ∊ O(n) 的问题，这很容易显示，因为当 n ≥ 1 时 d/dn log n ≤ 1。

Answer 2

使用归纳法很容易证明不等式适用于 n >= 16，不需要微积分：

首先，对于 n=16 你有 16 ⁴ =2 ¹⁶。

如果对于 n=k 不等式成立，则对于 n=k+1，您有 (k+1) ⁴ = ( ####)·k ⁴ < 2k ⁴ ≤ 2·2 ^k = 2 ^k+1。

QED。

_{由于这是家庭作业，我将把关键的步骤，找出代替 的内容留给####读者。}