H4.2.1.8. 多项式乘幂函数之和2
\(n,k\) 都是给定数，没什么区别
记 \(S_k=\sum_{i=1}^ni^kp^i\)
-
\(p=1\) 时 \(S_k\in\Theta(n^{k+1})\)
-
\(p<1\) 时
\[ \begin{aligned} (1-p)S_k&=\sum_{i=1}^n\left(i^k-(i-1)^k\right)p^i-n^kp^{n+1}\\ &=\sum_{i=1}^n\left(i^{k-1}+(i-1)i^{k-2}+(i-1)^2i^{k-3}+\cdots+(i-1)^{k-1}\right)p^i-n^kp^{n+1}\\ &\le\sum_{i=1}^n\left(i^{k-1}\cdot k\right)p^i-n^kp^{k+1}\le k\cdot S_{k-1} \end{aligned} \]\(\therefore S_k\le\dfrac{k}{1-p}S_{k-1},\therefore S_k\le\dfrac{k!}{(1-p)^{k}}S_0=\dfrac{k!}{(1-p)^k}\cdot\dfrac{p-p^{n+1}}{1-p}\in O(1).\)
-
\(p>1\) 时
法一：
\[\begin{aligned} (p-1)S_k&=-\sum_{i=1}^n\left(i^k-(i-1)^k\right)p^i+n^kp^{n+1}\\ &=-\sum_{i=1}^n\left(i^{k-1}+(i-1)i^{k-2}+(i-1)^2i^{k-3}+\cdots+(i-1)^{k-1}\right)p^i+n^kp^{n+1}\\ &\le-\sum_{i=1}^n\left((i-1)^{k-1}\cdot k\right)p^i+n^kp^{n+1}\\ &=-\sum_{i=1}^ni^{k-1}\cdot p^{i+1}+n^{k-1}\cdot p^{n+1}+n^kp^{n+1}=-S_{k-1}+\left(n^k+n^{k-1}\right)p^{n+1} \end{aligned} \]\(\therefore S_k\le\dfrac1{p-1}\cdot\left(-S_{k-1}+\left(n^k+n^{k-1}\right)\cdot p^{n+1}\right)\le\dfrac1{p-1}n^kp^{n+1}\in O\left(n^kp^n\right).\)
同理 \(S_k\in\Omega\left(n^kp^n\right),\therefore S_k\in\Theta\left(n^kp^n\right).\)
法二：
\[ \begin{cases} S_k\le\sum_{i=1}^nn^kp^i=n^k\cdot\dfrac{p^{n+1}-p}{p-1}\in O\left(n^kp^n\right)\\ S_k\ge n^kp^n\in\Omega\left(n^kp^n\right) \end{cases} \]\(\therefore S_k\in\Theta\left(n^kp^n\right).\)
注：为什么 \(i^k-(i-1)^k=\sum_{p=0}^{k-1}(i-1)^pi^{k-p}\)？因为 \(C_k^p=\sum_{i=0}^{k-1}C_i^{p-1}\).
标签：幂函数,right,cdot,多项式,sum,le,kp,left From： https://www.cnblogs.com/laijinyi/p/18544596