algorithm - 如何使用数学归纳法证明a_k > 0的每一个k次多项式都属于theta(n^k)？

Question

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

我不确定从哪里开始。

标签： algorithmdiscrete-mathematics

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 次多项式都是 Omega(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/2 n^k 得到 a_k/2 n^k + a_k-1 n^k-1 + … + a_0 >= 0。这多项式至多有 k 个实根；令 n0 为多项式的最大实根。然后，对于所有 n > n0，多项式必须保持非负或非正。假设它仍然是非正数。然后 a_k/2 n^k <= a_k-1 n^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/2 n^k + … + a_0 的最大根。

因为每个多项式同时为 O(n^k) 和 Omega(n^k)，因此它也是 Theta(n^k)。