Quod Erat Demonstrandum

2016/02/28

冪和表成二項式係數

Filed under: Fun,NSS,Pure Mathematics — johnmayhk @ 12:05 上午
Tags:

2016-01-30 在圖書館某小書的某附錄,見

johnmayhk-power-sum-01

似乎是很精巧的結果,匆匆抄下在顏冊分享,雖然自然數等冪和(Faulhaber’s formula)已是很舊的東西,參考

https://en.wikipedia.org/wiki/Faulhaber%27s_formula

但書沒有證明上圖中的結果,當時想,或者它和帕斯卡三角(Pascal’s triangle)的生成,即

C^{n+1}_r=C^n_{r-1}+C^n_r

之類有關吧?今天嘗試證明上圖中結果(當然可能有更好方法,高手見諒)。

先由舊文出發:

http://johnng.inscyber.net/johntalk_puremath02.doc

(若想了解當中原理,可參考 http://johnng.inscyber.net/johntalk_puremath02a.doc,若時間不足者,可先忽略。)

舊文提到,總能把 r^k 可表成 r^{< 1 >},r^{< 2 >},\dots r^{< k >} 的線性組合,即

r^{k}=\displaystyle \sum^k_{j=1}D^k_jr^{< j >}

當中的係數 D^k_j 可透過綜合除法(synthetic division)找出,把它們一表列出如下:

johnmayhk-power-sum-02

比如紫色那些數字,代表

r^5=r^{< 1 >}+15r^{< 2 >}+25r^{< 3 >}+10r^{< 4 >}+r^{< 5 >}

D^5_1=1,D^5_2=15,D^5_3=25,D^5_4=10,D^5_5=1

為美觀,再把 D^k_j 表列如下:

johnmayhk-power-sum-03

考慮 k=6 的情況,由綜合除法的算法,知

D^6_1=1=D^5_1
D^6_2=31=1+30=D^5_1+2D^5_2
D^6_3=90=15+75=D^5_2+3D^5_3
D^6_4=65=25+40=D^5_3+4D^5_4
D^6_5=15=10+5=D^5_4+5D^5_5
D^6_6=1=D^5_5

可見

D^k_j=D^{k-1}_{j-1}+jD^{k-1}_j …………………. (*)

其中 D^k_j=0 for j=0 or j >k

好了,求冪和,即

\displaystyle \sum^n_{r=1}r^{k}

=\displaystyle \sum^n_{r=1}\displaystyle \sum^k_{j=1}D^k_jr^{< j >}

=\displaystyle \sum^k_{j=1}\displaystyle \sum^n_{r=1}D^k_jr^{< j >}

=\displaystyle \sum^k_{j=1}D^k_j\frac{(n+1)^{< j+1 >}}{j+1} (這是舊文提及的所謂 F-運算)

=\displaystyle \sum^k_{j=1}D^k_jj!C^{n+1}_{j+1}

=\displaystyle \sum^k_{j=1}D^k_jj!(C^n_{j+1}+C^n_j)

=\displaystyle \sum^k_{j=1}D^k_jj!C^n_{j+1}+\displaystyle \sum^k_{j=1}D^k_jj!C^n_j

=\displaystyle \sum^{k+1}_{j=2}D^k_{j-1}(j-1)!C^n_j+\displaystyle \sum^k_{j=1}D^k_jj!C^n_j

=D^k_1C^n_1+\displaystyle \sum^k_{j=2}(D^k_{j-1}(j-1)!+D^k_jj!)C^n_j+D^k_kk!C^n_{k+1}

=\displaystyle \sum^{k+1}_{j=1}(D^k_{j-1}(j-1)!+D^k_jj!)C^n_j (因為 D^k_j=0 for j=0 or j >k

=\displaystyle \sum^{k+1}_{j=1}E^{k+1}_jC^n_j

其中定義 E^{k+1}_j

E^{k+1}_j=D^k_{j-1}(j-1)!+D^k_jj!

當中 j=1,2,\dots ,k+1

好了,現在證明主要結果:

E^{k+1}_j=(j-1)E^k_{j-1}+jE^k_j

見下

E^{k+1}_j

=D^k_{j-1}(j-1)!+D^k_jj!

=(D^{k-1}_{j-2}+(j-1)D^{k-1}_{j-1})(j-1)!+(D^{k-1}_{j-1}+jD^{k-1}_j)j! (由 (*))

=D^{k-1}_{j-2}(j-1)!+(j-1)D^{k-1}_{j-1}(j-1)!+D^{k-1}_{j-1}j!+jD^{k-1}_jj!

=(j-1)(D^{k-1}_{j-2}(j-2)!+D^{k-1}_{j-1}(j-1)!)+j(D^{k-1}_{j-1}(j-1)!+D^{k-1}_jj!)

=(j-1)E^k_{j-1}+jE^k_j

Q.E.D.

再把 E^{k+1}_j 表列如下:

johnmayhk-power-sum-04

隨便寫 k=5 的情況在結:

\displaystyle \sum^n_{r=1}r^{5}=\displaystyle \sum^6_{j=1}E^6_jC^n_j=C^n_1+31C^n_2+180C^n_3+390C^n_4+360C^n_5+120C^n_6

1 則迴響 »

  1. 其實這些係數只是 finite differences 而已。用算子代數不難得到更一般的公式。

    迴響 由 Jacob Ha — 2016/02/28 @ 3:55 上午 | 回覆


RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在WordPress.com寫網誌.

%d 位部落客按了讚: