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