幂和

首先我们从求前 n 个整数的平方和开始,也就是

  S_n = \sum_{i=1}^n n^2

然后可以尝试对 S_n 进行“扰动”,就像这样

 \begin{eqnarray*}
S_n + (n + 1)^2 &=& \sum_{i=0}^n (i+1)^2 \\
                &=& \sum_{i=0}^n (i^2 + 2i + 1) \\
                &=& S_n + 2\sum_{i=1}^n i + (n + 1)     \\
\end{eqnarray*}

最后发现 S_n 竟然被消掉了,“扰动”失败了,但是我们注意到这求出了 \sum_{i=1}^n i 的公式

所以会想,可不可以用更高的 C_n = \sum_{i=1}^n i^3 来求出 S_n

 \begin{eqnarray*}
C_n + (n + 1)^3 &=& \sum_{i=0}^n (i+1)^3 \\
                &=& \sum_{i=0}^n (i^3 + 3i^2 + 3i + 1) \\
                &=& C_n + 3S_n + \frac{3n(n + 1)}{2} + (n + 1)     \\
\Rightarrow S_n &=& \frac{(n+1)^3 - \frac{3n(n + 1)}{2} - (n + 1)}{3} \\
                &=& \frac{n(n+\frac{1}{2})(n+1)}{3}
\end{eqnarray*}

于是这样成功地求出了 S_n 的公式,既然如此,我们又会去尝试计算更高阶的幂和

首先,设

 \begin{equation} \label{pow-sum} f_k(n) = \sum_{i=1}^n i^k \end{equation}

那么,我们会有

 \begin{eqnarray*}
f_{k+1}(n) + (n + 1)^{k+1} &=& 1 + \sum_{i=1}^n (i+1)^{k+1} \\
                           &=& 1 + \sum_{i=1}^n \sum_{j=0}^{k+1} {{k+1} \choose j} i^j \\
                           &=& 1 + \sum_{j=0}^{k+1} {{k+1} \choose j} \sum_{i=1}^n i^j \\
                           &=& 1 + \sum_{i=0}^{k+1} {{k+1} \choose i} f_i(n) \\
                           &=& 1 + f_{k+1}(n) + (k + 1) f_k(n) + \sum_{i=0}^{k - 1} {{k+1} \choose i} f_i(n) \\
\end{eqnarray*}

这样就得到了

 \begin{equation} \label{simplified-pow-sum} f_k(n) = \frac{(n+1)^{k+1} - 1}{k + 1} - \frac{1}{k+1}\sum_{i=0}^{k - 1} {{k+1} \choose i} f_i(n) \end{equation}

或者我们可以写成

 \begin{equation} f_{k-1}(n) = \frac{(n+1)^k - 1}{k} - \frac{1}{k}\sum_{i=0}^{k - 2} {{k} \choose i} f_i(n) \end{equation}

这个公式有什么意义呢?在计算机里,有了它我们就可以用 \Theta(m^2) 的时间来计算 f_m(n),这比原来暴力来说至少是一个进步

现在我们换一种方式来试试推导这个和式

pow-sum-graph

显然,我们要求的就是图中紫色部分的面积,因为有微积分这个工具,我们现在可以很容易地求出蓝色部分以及紫色部分面积的和,也就是

 \int_1^{n+1} x^2 dx = \left .\frac{x^3}{3}\right | _1^{n+1} = \frac{(n+1)^3}{3} - \frac{1}{3}

我们可以考虑把误差扣掉,类似这样

 \begin{eqnarray*}
S_n &=& \int_1^{n+1} x^2 dx - \sum_{i=1}^n \left( \int_i^{i+1} x^2 dx - i^2 \right) \\
    &=& \frac{(n+1)^3}{3} - \frac{1}{3} - \sum_{i=1}^n \left( \frac{(i+1)^3-i^3}{3} - i^2 \right) \\
    &=& \frac{(n+1)^3}{3} - \frac{1}{3} - \sum_{i=1}^n \frac{3i+1}{3} \\
    &=& \frac{n(n+\frac{1}{2})(n+1)}{3} \\
\end{eqnarray*}

类似的,我们也可以用这种方法来计算 f_k(n)

 \begin{eqnarray*}
f_k(n) &=& \int_1^{n+1} x^k dx - \sum_{i=1}^n \left( \int_i^{i+1} x^k dx - i^k \right) \\
       &=& \frac{(n+1)^{k+1} - 1}{k+1} - \sum_{i=1}^n \frac{(i+1)^{k+1}-i^{k+1}-(k+1)i^k}{k+1} \\
       &=& \frac{(n+1)^{k+1} - 1}{k+1} - \frac{1}{k+1} \sum_{i=1}^n \left((i+1)^{k+1}-i^{k+1}-(k+1)i^k\right) \\
       &=& \frac{(n+1)^{k+1} - 1}{k+1} - \frac{1}{k+1} \sum_{i=1}^n \sum_{j=0}^{k-1} {{k+1} \choose j} i^j \\
       &=& \frac{(n+1)^{k+1} - 1}{k+1} - \frac{1}{k+1} \sum_{i=0}^{k-1} {{k+1} \choose i} f_i(n)
\end{eqnarray*}

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2014/09/power-sum

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

5 thoughts on “幂和

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.