44111 利用遞迴關係式求 r 為自然數$\sum_{k=1}^{n}k^{r}$的公式解
利用遞迴關係式求 r 為自然數$\sum_{k=1}^{n}k^{r}$的公式解
李維昌, 　 2020年 3月(173) PDF

研究目的： 本文以遞迴關係式求 $\sum\limits_{k=1}^n k^r$ 的公式解, 其中 $r$ 為自然數, 解題的靈感偶然從腦海中閃過, 我即刻把握當下, 振筆疾書, 記錄這美好的尋求過程, 請看下文的剖析。

研究過程：

  1. 以 $S_r(n)$ 表示 $\sum\limits_{k=1}^n k^r$, 本文探討 $r$ 為自然數的情形。
  2. 尋求遞迴關係式： \begin{eqnarray*} &&\hskip -15pt \hbox{設}\ S_r(n)=\frac{1}{r+1}\sum_{i=0}^rC_i^{r+1}\cdot B_i\cdot n^{r+1-i},\\[4pt] &&\hbox{則}\ S_{r}(n-1)=\frac{1}{r+1}\sum_{i=0}^rC_i^{r+1}\cdot B_i\cdot (n-1)^{r+1-i},\\[4pt] &&\Rightarrow n^r=S_r(n)-S_r(n-1)=\frac 1{r+1}\sum_{i=0}^rC_i^{r+1}\cdot B_i\cdot [n^{r+1-i}-(n-1)^{r+1-i}]\\[4pt] &=&\frac 1{r+1}\!\cdot\! C_0^{r+1}\!\cdot\! B_0\cdot [n^{r+1}\!-\!(n\!-\!1)^{r+1}]\!+\!\frac 1{r+1}\!\cdot\! C_1^{r+1}\cdot B_1\cdot [n^{r}\!-\!(n\!-\!1)^{r}]\\[4pt] &&+\frac 1{r+1}\!\cdot\! C_2^{r+1}\cdot B_2\cdot [n^{r-1}\!-\!(n\!-\!1)^{r-1}]\!+\!\cdots\!+\!\frac 1{r+1}\cdot C_r^{r+1} \!\cdot\! B_r\!\cdot\! [n^{1}\!-\!(n\!-\!1)^{1}]\\[4pt] &=&\frac 1{r+1}\cdot C_0^{r+1}\cdot B_0\cdot [C_1^{r+1}n^{r}\!-\!C_2^{r+1}n^{r-1}+C_3^{r+1}n^{r-2}+\cdots+(-1)^rC_{r+1}^{r+1}]\\[4pt] &&+\frac 1{r+1}\cdot C_1^{r+1}\cdot B_1\cdot [C_1^{r}n^{r-1}\!-\!C_2^{r}n^{r-2}+C_3^{r}n^{r-3}+\cdots+(-1)^{r-1}C_{r}^{r}]\\[4pt] &&+\frac 1{r+1}\!\cdot\! C_2^{r+1}\!\cdot\! B_2\cdot [C_1^{r-1}n^{r-2}\!-\!C_2^{r-1}n^{r-3}\!+\!C_3^{r-1}n^{r-4}\!+\!\cdots\!+\!(-1)^{r-2}C_{r-1}^{r-1}]\\[4pt] &&+\cdots+\frac 1{r+1}\cdot C_r^{r+1}\cdot B_r\cdot [C_1^{1}]\\[4pt] &=&B_0\cdot n^r+\frac 1{r+1}\cdot[-C_0^{r+1}\cdot B_0\cdot C_2^{r+1}+C_1^{r+1}\cdot B_1\cdot C_1^r]n^{r-1}\\[4pt] &&+\frac 1{r+1}\cdot[C_0^{r+1}\cdot B_0\cdot C_3^{r+1}-C_1^{r+1}\cdot B_1\cdot C_2^r+C_2^{r+1}\cdot B_2\cdot C_1^{r-1}]n^{r-2}\\[4pt] &&+\frac 1{r\!+\!1}\!\cdot\![-C_0^{r+1}\!\cdot\! B_0\!\cdot\! C_4^{r+1}\!+\!C_1^{r+1}\!\cdot\! B_1\!\cdot\! C_3^r \!-\!C_2^{r+1}\!\cdot\! B_2\!\cdot\! C_2^{r-1}\!+\!C_3^{r+1}\!\cdot\! B_3\!\cdot\! C_1^{r-2}]n^{r-3}\\[4pt] &&+\cdots+\frac 1{r+1}\cdot [(-1)^r\cdot C_0^{r+1}\cdot B_0\cdot C_{r+1}^{r+1}+(-1)^{r-1}\cdot C_1^{r+1}\cdot B_1\cdot C_r^r\\[4pt] &&+(-1)^{r-2}\cdot C_2^{r+1}\cdot B_2\cdot C_{r-1}^{r-1}+\cdots+(-1)^{0}\cdot C_r^{r+1}\cdot B_r\cdot C_1^1]\\[4pt] &=&B_0\cdot n^r+\frac 1{r+1}\cdot[-C_0^{2}\cdot B_0\cdot C_2^{r+1}+C_1^{2}\cdot B_1\cdot C_2^{r+1}]n^{r-1}\\[4pt] &&+\frac 1{r+1}\cdot[C_0^{3}\cdot B_0\cdot C_3^{r+1}-C_1^{3}\cdot B_1\cdot C_3^{r+1}+C_2^{3}\cdot B_2\cdot C_3^{r+1}]n^{r-2}\\[4pt] &&+\frac 1{r\!+\!1}\!\cdot\![-C_0^{4}\!\cdot\! B_0\!\cdot\! C_4^{r+1}\!+\!C_1^{4}\!\cdot\! B_1\!\cdot\! C_4^{r+1} \!-\!C_2^{4}\!\cdot\! B_2\!\cdot\! C_4^{r+1}\!+\!C_3^{4}\!\cdot\! B_3\!\cdot\! C_4^{r+1}]n^{r-3}+\cdots\\[4pt] &&+\frac 1{r+1}\!\cdot\! [(-1)^r\!\cdot\! C_0^{r+1}\!\cdot\! B_0\!\cdot\! C_{r+1}^{r+1}+(-1)^{r-1}\!\cdot\! C_1^{r+1}\!\cdot\! B_1\!\cdot\! C_{r+1}^{r+1}\\[4pt] &&\!+\!(-1)^{r-2}\!\cdot\! C_2^{r+1}\!\cdot\! B_2\!\cdot\! C_{r+1}^{r+1}\!+\!\cdots\!+\!(-1)^{0}\!\cdot\! C_r^{r+1}\!\cdot\! B_r\!\cdot\! C_{r+1}^{r+1}]\\[4pt] &=&B_0\cdot n^r+\frac {(-1)^1}{r+1}\cdot C_{1+1}^{r+1}\cdot [C_0^{2}\cdot B_0\!-\!C_1^{2}\cdot B_1]n^{r-1}\\[4pt] &&+\frac {(-1)^2}{r+1}\cdot C_{2+1}^{r+1}\cdot [C_0^{3}\cdot B_0-C_1^{3}\cdot B_1\!+\!C_2^{3}\cdot B_2]n^{r-2}\\[4pt] &&+\frac {(-1)^3}{r+1}\cdot C_{3+1}^{r+1}\cdot [C_0^{4}\cdot B_0\!-\!C_1^{4}\cdot B_1 \!+\!C_2^{4}\cdot B_2\!-\!C_3^{4}\cdot B_3]n^{r-3}\\[4pt] &&+\cdots+\frac {(-1)^r}{r+1}\cdot C_{r+1}^{r+1}\cdot [C_0^{r+1}\cdot B_0-C_1^{r+1}\cdot B_1\\[4pt] &&+C_2^{r+1}\cdot B_2-C_3^{r+1}\cdot B_3+\cdots+(-1)^{r}\cdot C_r^{r+1}\cdot B_r]n^{r-r}\\[4pt] &=&B_0\cdot n^r+\sum_{k=1}^r \Big\{\frac {(-1)^k}{r+1}\cdot C_{k+1}^{r+1}\cdot\Big[\sum_{i=0}^k(-1)^i\cdot C_i^{k+1}B_i\Big]\Big\}n^{r-k}\\[4pt] &&\Rightarrow B_0=1\ \hbox{且}\ \sum_{i=0}^k(-1)^i\cdot C_i^{k+1}B_i=0,\ k=1,\ldots,r. \end{eqnarray*} 到此已尋得遞迴關係式進而可求得 $B_i$, $i=1,\ldots,r$。
  3. 以 $r=7$ 為例, 利用上述遞迴關係式可求得 $B_i$, $i=0,1,\ldots,7$: 將遞迴關係式寫成矩陣的形式 $$\left[\begin{array}{cccccccc} C_0^1&0&0&0&0&0&0&0\\ C_0^2&-C_1^2&0&0&0&0&0&0\\ C_0^3&-C_1^3&C_2^3&0&0&0&0&0\\ C_0^4&-C_1^4&C_2^4&-C_3^4&0&0&0&0\\ C_0^5&-C_1^5&C_2^5&-C_3^5&C_4^5&0&0&0\\ C_0^6&-C_1^6&C_2^6&-C_3^6&C_4^6&-C_5^6&0&0\\ C_0^7&-C_1^7&C_2^7&-C_3^7&C_4^7&-C_5^7&C_6^7&0\\ ~C_0^8~&-C_1^8&~C_2^8~&-C_3^8&~C_4^8~&-C_5^8&~C_6^8~&-C_7^8 \end{array}\right] \left[\begin{array}{c} B_0\\ B_1\\ B_2\\ B_3\\ B_4\\ B_5\\ B_6\\ B_7\\ \end{array}\right]= \left[\begin{array}{c} 1\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0 \end{array}\right],$$ 解得 $B_0=1$, $B_1=\dfrac 12$, $B_2=\dfrac 16$, $B_3=0$, $B_4=-\dfrac 1{30}$, $B_5=0$, $B_6=\dfrac 1{42}$, $B_7=0$。
  4. 利用所求得的 $B_i$, $i=0,1,2,\ldots, 7$ 與 $S_r(n)=\dfrac 1{r+1}\sum\limits_{i=0}^r C_i^{r+1}\cdot B_i\cdot n^{r+1-i}$, 去求 $S_r(n)$ 的公式解, $r=1,2,\ldots,7$ ： \begin{eqnarray*} S_1(n)&=&\frac 12\sum_{i=0}^1 C_i^2\cdot B_i\cdot n^{2-i}=\frac 12 n^2+\frac 12n,\\[-5pt] S_2(n)&=&\frac 13\sum_{i=0}^2 C_i^3\cdot B_i\cdot n^{3-i}=\frac 13n^3+\frac 12 n^2+\frac 16n,\\[-5pt] S_3(n)&=&\frac 14\sum_{i=0}^3 C_i^4\cdot B_i\cdot n^{4-i}=\frac 14n^4+\frac 12 n^3+\frac 14n^2,\\[-4pt] S_4(n)&=&\frac 15\sum_{i=0}^4 C_i^5\cdot B_i\cdot n^{5-i}=\frac 15n^5+\frac 12 n^4+\frac 13n^3-\dfrac 1{30}n,\\[-5pt] S_5(n)&=&\frac 16\sum_{i=0}^5 C_i^6\cdot B_i\cdot n^{6-i}=\frac 16n^6+\frac 12n^5+\frac 5{12} n^4-\frac 1{12}n^2,\\[-5pt] S_6(n)&=&\frac 17\sum_{i=0}^6 C_i^7\cdot B_i\cdot n^{7-i}=\frac 17n^7+\frac 12 n^6+\frac 12n^5-\frac 16n^3+\frac 1{42}n,\\[-5pt] S_7(n)&=&\frac 18\sum_{i=0}^7 C_i^8\cdot B_i\cdot n^{8-i}=\frac 18n^8+\frac 12 n^7+\frac 7{12}n^6-\frac 7{24}n^4+\frac 1{12}n^2. \end{eqnarray*}
  5. 結論： 以上, 我們列出了 $S_1(n)$, $S_2(n)$, $\ldots$, $S_7(n)$ 等的公式解。 事實上, 利用遞迴式 $B_0=1$ 且 $\sum\limits_{i=0}^k(-1)^i\cdot C_i^{k+1}\cdot B_i=0$, $k=1,\ldots,r$； 並且把此遞迴關係用矩陣的形式表示, 我們可以求得任何 $S_r(n)=\dfrac{1}{r+1}\sum\limits_{i=0}^rC_i^{r+1}\cdot B_i\cdot n^{r+1-i}$ 的公式解。

---本文作者為國立宜蘭高中退休教師---