如何用数学归纳法证明每个k次多项式都属于θ(n^k)，且a_k >0？

Question

问题如下:证明每个k次多项式p(n) = a_k n^k + a_k-1 n^k-1 +... + a_0且a_k>为0，属于θ(n^k)。

我不知道从哪里开始。

Answer 1

为了证明每个k次多项式都是O( n^k )，我们必须证明存在常数n0和c，使得对于n> n0，a_k n^k+ a_k-1 n^k-1 +…+ a_0 <= c* n^k。如果我们选择c= |a_k| + |a_k-1| +…+ |a_0|，则很容易验证RHS必须大于或等于LHS；否则不能，因为LHS中的每一项对应于RHS中的一项，该项必须大于或等于它。

为了证明每个k次多项式都是Ω( n^k )，我们必须证明存在常数n0和c，使得对于n> n0，a_k n^k+ a_k-1 n^k-1 +…+ a_0 >= c* n^k。为了演示这一点，取c= a_k/2。然后我们可以从两边减去a_k /2n^k得到a_k/2n^k+a_k-1n^k-1+…+ a_0 >= 0。这个多项式至多有k个实根；设n0是多项式的最大实根。然后，对于所有n> n0，多项式必须保持非负或非正。假设它仍然是非正的。然后a_k/2n^k <= a_k-1n^k-1+…+ a_0。除以n^k得到a_k/2 <= a_k-1 /n+…a_0 / n^k。这个不等式的RHS是一个严格的递减函数，随着n的增加而趋于零，没有界限；因此，这个不等式不可能在一般情况下成立。因此，多项式在最大根n0之后仍然是非负的；因此，原始多项式被确定为Omega( n^k )，其中c= a_k/2，并且n0等于多项式a_k/2n^k+…的最大根+ a_0。

因为每个次数多项式同时是O(n^k)和Omega(n^k)，所以它也是θ(n^k)。