推 G41271 :哪有用微分的國中解法呀 02/12 11:49
推 suhorng :原PO給的國中解法沒有用微分啊 02/12 12:08
→ G41271 :沒看第二行 抱歉 02/12 13:32
→ charliejack :感恩@@"~~推用心~~ 02/12 17:59
※ 引述《charliejack (charliejack)》之銘言：
: n
: 求 Σi^4 的 Big-O
: i=1
: 我知道答案是O(n^5)
: 但不知道在考卷上如何寫算式~"~ 或是證明
比較簡單的國中解法在下面一點
先說用生成函數的解法
1+x+x^2+... = 1/(1-x)
=> 1+2x+3x^2+... = 1/(1-x)^2 (對上式左右微分)
=> x+2x^2+3x^3+... = x/(1-x)^2 (將上式左右同乘以x)
=> 1+(2^2)x +(3^2)x^2+... = (1+x) / (1-x)^3 (再將上式左右微分)...過程省略
=> x+(2^2)x^2 +(3^2)x^3+... = x(1+x) / (1-x)^3 (再將上式左右同乘以x)
(PS.到這裡可以準備求Σk^2,但現在要求到k^4,所以得繼續.)
=>1+(2^3)x+(3^3)x^2+...= (x^2+4x+1) / (1-x)^4 (將上式左右微分)...過程省略
=>x+(2^3)x^2+(3^3)x^3+...= x(x^2+4x+1) / (1-x)^4 (將上式左右同乘以x)
=>1+(2^4)x+(3^4)x^2+...= (x^3+11x^2+11x+1) / (1-x)^5 (再將上式左右微分)
=>x+(2^4)x^2+(3^4)x^3+...= x(x^3+11x^2+11x+1) / (1-x)^5 =
x(x^3+11x^2+11x+1)[(1-x)^(-5)] ... 微分差不多練習完了
又因為1+x+x^2+... = 1/(1-x) , 將此式等號左邊還有等號右邊分別和上式相乘
可得0^4 + (0^4+1^4)x + (0^4+1^4+2^4)x^2 + ... + (0^4+1^4+...+n^4)x^n + ... =
(x^4+11x^3+11x^2+x)[(1-x)^(-6)] ... 算到這邊差不多昏死一半了
n
再來觀察上式可了解所要求的Σ k^4即是 (0^4+1^4+...+n^4)也就是上式
k=0
中x^n的係數
所以要來展開該式右方 ∞ -6 i
(x^4+11x^3+11x^2+x)[(1-x)^(-6)] = (x^4+11x^3+11x^2+x)*Σ C *(-x)
i=0 i
(負二項式定理)
∞ 5+i
= (x^4+11x^3+11x^2+x)*Σ (C )*x^i
i=0 i
(把負n取r換成正數以便運算)
因為所求為 x^n項的係數
所以sigma內的i值要分別代入 n-4 , n-3 , n-2 , n-1 來分別跟左方的x^4 ,11x^3
,11x^2 , x 相乘 , 然後再把這幾個結果相加可得
n+1 n+2 n+3 n+4
所求的x^n項的係數 = C + 11*C + 11*C + C
5 5 5 5
=[ (n+1)n(n-1)(n-2)(n-3) + 11(n+2)(n+1)n(n-1)(n-2) + 11(n+3)(n+2)(n+1)n(n-1)
+ (n+4)(n+3)(n+2)(n+1)n ] / 5!
= n(n+1)(24n^3 + 36n^2 + 4n - 4)/120 ... (計算過程略)
=n(n+1)(6n^3 + 9n^2 + n - 1)/30
=n(n+1)(2n+1)(3n^2+3n-1)/30 .......................終於有答案了
所以可得Σk^4 公式為 n(n+1)(2n+1)(3n^2+3n-1)/30
也看的出來是O(n^5)
==============================================================================
但也有國中的方法,以下用個國中的方法來驗證:
n
以下Σ都是指Σ , 但我省略一點 這樣比較好打
k=0
令 A = Σk^5 = 0^5 + 1^5 + 2^5 + ...+ n^5
B = Σ(k+1)^5 = 1^5 + 2^5 + ...+ n^5 + (n+1)^5
S = 所求 = Σk^4
把A跟B等號右方直接互減可得 B-A = (n+1)^5 ... (1)
把A跟B等號左方互減可得 B-A = Σ[(k+1)^5 - k^5]
展開得B-A = Σ(5k^4 + 10k^3 + 10k^2 + 5k + 1)
= 5S + 10*[n^2(n+1)^2]/4 + 10*n(n+1)(2n+1)/6 + 5*n(n+1)/2 + (n+1) ...(2)
(因為是0~n所以共有n+1項) (這邊在複習國中sigma公式)
由(1)(2)比較通分化簡之後可得 30S = 6n^5 +15n^4 +10n^3 -n
= n(n+1)(2n+1)(3n^2+3n-1)
(計算過程就省略了)
=> S = Σk^4 = n(n+1)(2n+1)(3n^2+3n-1)/30
也當然可以看出是O(n^5)了
不過不管用哪種方法好像都不用求到最後
因為這兩種方法都把答案求出來了
所以如果只是要求big O
應該都不用做到最後
就自己看看該做到哪囉
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.167.75.13
※ 編輯: jameschou 來自: 218.167.75.13 (02/12 09:15)
※ 編輯: jameschou 來自: 218.167.75.13 (02/12 09:17)