Re: [問題] 級數問題

[doom8199 (～口卡口卡 修～)]

※ 引述《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)
推 red0210:....好複雜@__@  先頭推!
推 gj942l41l4:強者阿......推!
推 e2167471:這才叫強者  拜他才是正經  推
推 wind42:原PO真神人
推 shelly23489:先推先拜 等一下再想辦法看懂@@
推 revivalworld:113 幫推
推 idphobia:有看有拜