简单的求和问题

Posted by WildCow on November 20, 2018

写在前面


于尘世相忘,与世界同葬





题目


你需要尽可能快的算出 $f(n) = \sum_{i = 0}^{n} i^2$,$n \geq 0$

可能需要掌握的前置技能




方法 -1


$O(n)$ 做法的可以考虑一下自己该不该自裁了了





方法 0


现在都 8102 年了

求前 $n$ 个数的平方和肯定是已解决了的问题

简单的算出前几项发现是 0, 1, 5, 14 ……

然后 oeis 一下

然后问题就解决辣!

当然机制的同学也可以在 $CRC$ $Stamdard$ $Mathematical$ $Tables$ 的第 36 页找到答案

总之我们有答案:$f(x) = \frac{x(x + 1)(2x+1)}{6}$

然后这题就愉快的做出来辣!





方法 1


待定系数

我们会发现 $f’(n) = \sum_{i = 0}^{n}i^0 = n$

通项公式是一次的

然后我们又发现 $f’‘(n) = \sum_{i = 0}^{n}i$ 的通项公式是二次的

那么我们有理由相信 $f(n)$ 的通项公式是三次的= =!

我们设 $f(n) = an^3 + bn^2+cn+d$

然后手算前 4 项带进去就好了





方法 2


也许 方法 0 的解法让人觉得不是正道

我们应该尝试能用自己的推导得出答案

例如聪明的 $Heaven_$ 会尝试猜一个式子 $f’(x) = \frac{n(n + 0.5)(n + 1)}{3}$

带进去会发现前几项是对的

于是我们有理由相信这个是对的

但是这样一来就和 方法 0 一样令人感到不适了

所以我们要尝试证明一下

当然是归纳法啦

  • 当然我们能发现 $f(0) = \frac{0 × 0.5 × 1}{3} = 0^2$ 成立

  • 假设 $n > 0$ 且 $f(n - 1)$ 满足上面的那个式子 $f’(n - 1)$

    然后我们有

    然后移项一下就好了

    证毕

归纳法天下第一





方法 3


现在我们尝试直接算出来

这个东西其实大家都已经很熟悉了

他有自己的名字,叫扰动法

让我们充满信心的来一发(?)

然后我们会很悲伤的发现 $f(n)$ 被约掉了

然后我们发现出现了前 $n$ 个数的一次方的和

那我们对 $g(n) = \sum_{i = 0}^{n} i^3$,$n \geq 0$ 扰动一下,前 $n$ 个数的平方的和没准就出来了!


在我们的意料之内

$g(n)$ 被消除了然后给我们留下了 $f(n)$

经过简单的移项后,$f(n)$ 的式子就出来了





方法 4


我们其实还可以用微积分的方法解决这个问题

大家都知道一个函数的积分

可以看作在坐标轴中图像和坐标轴围城的图形的面积

我们可以用若干个狭长的小矩形或者是小梯形的面积相加来近似这个面积

当然我们也可以反过来

对与 $f(n)$

可以当作平面中若干个宽为 $1$,长为 $i^2$ 的矩形的面积和

近似等于 $0$ 到 $n$ 之间区间 $f’(x) = x^2$ 下面的面积

也就是所谓的 $\int_{0}^{n}x^2dx = n^3 / 3$

所以我们可以知道 $f(n)$ 近似等于 $n^3 / 3$

然后我们需要把误差补上

即 $E(n) = f(n) - \frac{n^3}{3}$

然后 $f(n)$ 满足 $f(n) = f(n - 1) + n^2$

我们就会发现 $E(n) $其实满足更简单的递归式!


另外一种方法是通过对楔形误差项的面积求和来得到 $E(n)$

两种方法都可以很好的求出 $E(n)$





方法 5


我们其实可以采用一个更复杂的式子来替换原先的式子

只要那个更复杂的式子拿捏得当(过分了!!!!!!!!!)

我们就可以化简了!





方法 5


可以直接用下降阶乘幂来搞

其中 $n^{\underline{m}} = n(n - 1)(n - 2)…(n - m + 1)$

关于下降阶乘幂下篇博客介绍





方法 6


直接生成函数

下下篇博客介绍