用归纳法证明多项式Big-Theta？

Question

我理解big theta，big oh和big omega的概念..我只是很难证明这一点。我已经很长时间没有做归纳了，所以我很确定我只是生疏了，错过了一些简单的东西。

例如..我需要帮助的问题是展示5n² - 6n = Θ(n²)。

我已经了解了问题的Big-Oh部分(我做了big-Oh和Ω，分别对吗？)至：

6k² >= 5n² - 6n

最大的omega部分是：

5n² - 6n >= n²

....but我该怎么做?！我记得在入职时发生了类似于...我假设这些都是真的，现在为每个n插入(n+1) ...做..某物?在这一点上我迷失了自我。

Answer 1

为了证明5n^2-6n是O(n^2)，你必须证明5n^2-6n <= cn^2对于所有数n >= n0，对于某个数n0和常数c。

归纳法证明包括证明基本情况的声明和证明归纳步骤。在我们的例子中，我们可以看到，当n=1时，对于某个常数c，基本情况明显成立。

对于归纳步骤，我们假设对于某个数字k，声明是正确的，并使用它来证明声明对于k+1是正确的。因此，我们假设5k^2-6k <= ck^2，并显示：

5(k+1)^2 - 6(k+1)  = 5k^2 +10k + 5 -6k - 6
                   = 5k^2-6k + 10k -1        
                  <= ck^2 + 10k - 1
                  <= ck^2 + c*2k + c       (for any constant c  >= 5)
                   = c(k+1)^2

这证明了k+1的声明并完成了证明。

你可以用类似的方式来证明欧米茄的说法。