Re: [問題] 級數問題
※ 引述《e2167471 (八復爛人)》之銘言：
: ※ 引述《Herlo (赫蘿)》之銘言：
: : n(n+1)(2n+1)
: : 1^2+2^2+3^2+.......+n^2= 一一一 是怎麼導出來的?
: : 6
---
e大列的那個方法高中應該都會教吧 (降階)
降階法唯一的缺點是
假設 1^m + 2^m + ... + n^m = S(m,n)
要解出 S(m,n) 的 closed form (事實上只存在級數解)
需先求出 S(1,n) 、 S(2,n) 、 ... 、 S(m-1,n)
但要解出 S(m-1,n)
又必須先知道 S(1,n) 、 S(2,n) 、 ... 、 S(m-2,n)
所以當 m 為變數
n m-1 n m-1 m-1 n m-2
Σ[ k^m - k^(m-1) ] = C * Σk - C * Σk + .....
k=1 1 k-1 2 k=1
變成要用迴圈的方式不斷帶入
或是用二項式定理展開做刪減
計算過程會很龐大、而且解的過程有點不直觀
証明 維基百科有 (我只有貼結論)
http://en.wikipedia.org/wiki/Faulhaber%27s_formula
-------------------------------------------------------------------------------
我高中時有想到一個比較直觀的作法(跟二項式定理很像)
以原po 想問的當例子， 求 S(2,n) 的 closed form
因為 S(2,n) = 1^2 + 2^2 + .. + (n-1)^2 + n^2
= S(2,n-1) + n^2
所以題目變成是在求以下的遞迴式:
┌ S(2,1) = 1 ____(1)
└ S(2,n) = S(2,n-1) + n^2 ____(2)
解 (2) 式有一種方法
就是找出一個函數 f(k) , 使得 (2)式可改寫成:
S(2,n) - f(n) = S(2,n-1) - f(n-1)
所以就能用遞迴概念，從 order n 一直降到 order 1:
S(2,n) - f(n) = S(2,n-1) - f(n-1)
= S(2,n-2) - f(n-2)
= ...
= S(2,1) - f(1)
= 1 - f(1)
因此 S(2,n) = f(n) - f(1) + 1 就能得到 closed form 了
所以接下來的重心就擺在找出 f(n)
------
令 f(n) = an^3 + bn^2 + cn + d
所以 S(2,n) - f(n) = S(2,n-1) - f(n-1)
→ S(2,n) = S(2,n-1) + f(n) - f(n-1)
= S(2,n-1) + [ 3a*n^2 + (-3a+2b)*n + (a-b+c) ]
與 (2)式 比較係數可得:
3a*n^2 + (-3a+2b)*n + (a-b+c) = n^2
→ ┌ 3a = 1
│ (-3a+2b) = 0
└ (a-b+c) = 0
→ ┌ 3 0 0 ┐┌ a ┐ ┌ 1 ┐
│ -3 2 0 ││ b │ = │ 0 │
└ 1 -1 1 ┘└ c ┘ └ 0 ┘
接著就是求出上面的反矩陣
我故意寫成矩陣型態，是因為這個矩陣的反矩陣很好解
我用 [B I] → 列運算 → [ I B^(-1) ] 去解:
┌ 3 0 0 1 0 0 ┐ /3
│ -3 2 0 0 1 0 │ /2
└ 1 -1 1 0 0 1 ┘
┌ 1 0 0 1/3 0 0 ┐ ─┐
→ │ -3/2 1 0 0 1/2 0 │ ┤ 3/2
└ 1 -1 1 0 0 1 ┘ ┘ (-1)
┌ 1 0 0 1/3 0 0 ┐
→ │ 0 1 0 1/2 1/2 0 │ ─┐
└ 0 -1 1 -1/3 0 -1 ┘ ┘ 1
┌ 1 0 0 1/3 0 0 ┐
→ │ 0 1 0 1/2 1/2 0 │
└ 0 0 1 1/6 1/2 -1 ┘
即 ┌ a ┐ ┌ 1/3 0 0 ┐┌ 1 ┐ ┌ 1/3 ┐
│ b │ = │ 1/2 1/2 0 ││ 0 │ = │ 1/2 │
└ c ┘ └ 1/6 1/2 -1 ┘└ 0 ┘ └ 1/6 ┘
所以 f(n) = n^3/3 + n^2/2 + n/6 + d
因此由前面的結論可知道
S(2,n) = f(n) - f(1) + 1
= (n^3/3 + n^2/2 + n/6 + d) - (1/3 + 1/2 + 1/6 + d) + 1
= n^3/3 + n^2/2 + n/6
or = n(n+1)(2n+1)/6
------------------------------------------------------------------------------
上述解法有兩個 key point 與 一個 observation:
<1> 為何可以假設 f(n) 為三次多項式?
其實那個假設是用 try 出來的
基本上滿足 f(n) 的所有可能不只是多項式
也有可能是指數函數 or 三角函數等的合成函數型態
但至少我知道 多項式 f(n) - 多項式 f(n-1)
還是會等於多項式 ( f(n) - f(n-1) )
( 若有限項 多項式-多項式 會變成 指數or三角函數 就有鬼了＝＝ )
至於為何可假設 f(n) 是三次多項式
而非 二次多項式 or 四次以上的多項式?
關於這點可以自行嘗試假設帶入求解
應該就能歸納出原因了 ︿︿
ps: 等大學修過離散數學應該會更加了解
<2> 寫成矩陣型態有何用意?
那個矩陣又稱作 下三角矩陣 (Lower Triangular Matrix)
作列運算的話
用很少步驟就可將此矩陣化成 單位矩陣
不過關鍵不在於該矩陣好算
而是 我最後只需要該反矩陣的第一行 column
所以計算過程可以再大幅降低
在這裡我先賣個關子
其實不難想
m k
<3> 令 f(n) = Σ a_m * n
k=0
則 S(m,n) = f(n) - a_0
m k
= Σ a_m * n ( S(m,n) 與 a_0 無關 )
k=1
這個現象也不難說明
就留給原po自己想
這個現象是在說明
若 S(m,n) = S(m,n-1) + n^m
則只需假設 f(n) 為 (m+1) 次多項式
且不需要假設常數項
等解出 f(n) 後
S(m,n) 其實就等於 f(n)
------------------------------------------------------------------------------
為免某書說我在打嘴砲
所以實際算一下 S(5,n) = 1^5 + 2^5 + 3^5 + ... + n^5 的 closed form
sol:
┌ a_6*n^6 ┐
│ a_5*n^5 │
令 f(n) = │ a_4*n^4 │
│ a_3*n^3 │
│ a_2*n^2 │
└ a_1*n ┘
則 f(n) - f(n-1)
┌ 6 ┐┌ a_6*n^5 ┐
│ -15 5 ││ a_5*n^4 │
= │ 20 -10 4 ││ a_4*n^3 │
│ -15 10 -6 3 ││ a_3*n^2 │
│ 6 -5 4 -3 2 ││ a_2*n^1 │
└ -1 1 -1 1 -1 1 ┘└ a_1 ┘
┌ a_6 ┐ ┌ 120 ┐ ┌ 1/6 ┐
│ a_5 │ 1 │ 360 │ │ 1/2 │
可解出 │ a_4 │ = ___ │ 300 │ = │ 5/12│
│ a_3 │ 720 │ 0 │ │ 0 │
│ a_2 │ │ -60 │ │-1/12│
└ a_1 ┘ └ 120+300-60-360 ┘ └ 0 ┘
即 S(5,n) = 1^5 + 2^5 + ... + n^5
= n^6/6 + n^5/2 + 5n^4/12 - n^2/12
不過以高中來說
應該不會出到 S(4,n) 以上
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.141.151
※ 編輯: doom8199 來自: 140.113.141.151 (10/29 02:21)
推
10/29 02:34, , 1F
10/29 02:34, 1F
推
10/29 19:18, , 2F
10/29 19:18, 2F
推
10/29 20:34, , 3F
10/29 20:34, 3F
推
10/29 20:50, , 4F
10/29 20:50, 4F
推
10/29 23:08, , 5F
10/29 23:08, 5F
推
11/02 09:29, , 6F
11/02 09:29, 6F
推
11/02 14:15, , 7F
11/02 14:15, 7F