※ 引述《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)