兩個方法求冪次和公式

以$1^2+2^2+3^2+...+n^2$為例。更高次仿此可得。

方法一：牛頓差分法

首先我們需要一個數列，這個數列的每一項都是冪次和。 注意必須從零開始，因為我們要用的公式是差分版的麥克勞林級數：

假定數列是$F(0),F(1),F(2),...$

$$
\begin{multline*}
F(n)=F(0)+\Delta F(0)n+\frac{1}{2!}\Delta^2F(0)n(n-1)+\frac{1}{3!}\Delta^3F(0)n(n-1)(n-2) \\
+\cdots+\frac{1}{r!}\Delta^rF(0)n(n-1)(n-2)...(n-r+1)+\cdots
\end{multline*}
$$

其中$\Delta F(0)=F(1)-F(0)$

        $\Delta^rF(0)=\Delta^{r-1}F(1)-\Delta^{r-1}F(0)$

$\Delta^r$稱為r階差分。

冪次數列：    $0,1,4,9,16$

冪次和數列：$0,1,5,14,30$

一階差分：    $\ \ 1,4,9,16$

二階差分：    $\ \ \ \ 3,5,7$

三階差分：    $\ \ \ \ \ \ 2,2$

因為我們要代入麥克勞林級數，所以我們只需要$\Delta^rF(0)$，也就是以上各列的第一項 。另外三階差分為常數，所以級數只到$\Delta^3$，之後的差分全都是零了。

我們要求的公式就是$F(n)$

$$
\begin{align*}
F(n)&=0+1*n+\frac{1}{2}*3*n(n-1)+\frac{1}{6}*2*n(n-1)(n-2) \\
&=\frac{n(n+1)(2n+1)}{6}
\end{align*}
$$

方法二：生成函數法

生成函數就不多做介紹了。只要注意數列的生成函數$g(x)$的和函數是$\frac{1}{1-x}g(x)$，以及一般化的二項式展開：$(1+x)^k$，$k$是負數的狀況。這時需要公式
$C_r^{-n}=(-1)^rC_{r}^{n+r-1}$，$n$是正整數。其實這只是照樣帶入普通的$C_r^n$公式而已。

$$
\begin{align*}
 1+x+x^2+\cdots &=\frac{1}{1-x}   \ \ 微分後得 \\
 1+2x+3x^2+\cdots &=\frac{1}{(1-x)^2} \ \   乘上x得 \\
 x+2x^2+3x^3+\cdots &=\frac{x}{(1-x)^2} \ \   微分後得 \\
 1+2*2x+3*3x^2+\cdots &=\frac{1}{(1-x)^2}+\frac{2x}{(1-x)^3} \\
\end{align*}
$$
此生成函數的和函數就是我們要的最終生成函數
$$\frac{1}{(1-x)^3}+\frac{2x}{(1-x)^4}$$。注意我們需要的是$x^{n-1}$的係數。
冪次和公式就是$$(-1)^{n-1}\ C_{n-1}^{-3}+2\ (-2)^{n-2}\ C_{n-2}^{-4}=\frac{n(n+1)(2n+1)}{6}$$