作者oNeChanPhile (親姐基)
看板Math
標題Re: [中學] 循環數列化簡
時間Sun Oct 21 02:22:47 2012
不用傅立葉的話,就用單位根去湊吧
Lemma:
2πi/n 0 1 n-1 n
設 z(n) = e (注意 z(n) =1, z(n) ,..., z(n) 為 x = 1 的 n 個根
n 為自然數
0k 1k (n-1)k
z(n) + z(n) + ...+ z(n) ╭ 0, if k 不是 n 的倍數
則 ──────────────── = ┤
n ╰ 1, if k 是 n 的倍數
pf:依最大公因數(k,n)討論
case(i) k,n 互質
此時 {0k, 1k, 2k, ....(n-1)k} 為 n 的完全剩餘系(註1)
0 1 n-1
z(n) + z(n) + ... + z(n)
故原式 = ────────────── = 0 (註2)
n
case(ii) k,n 不互質,且 k 不為 n 的倍數
令 k=k'q, n=n'q, q=k與n之最大公因數
k 2πik/n 2πik'/n' k'
則 z(n) = e = e = z(n')
0k' 1k' (n-1)k'
z(n') + z(n') + ...+ z(n')
原式 = ───────────────────
qn'
注意指數 {0k',1k',..(n'-1)k'}, {n'k',(n'+1)k'....(2n'-1)k'},
....., {(q-1)n'k',.....,(qn'-1)k'}
剛好輪完 q 個 n' 的完全剩餘系,所以適用 case(i) 的結論
case(iii) k是n的倍數
利用 (單位根)^n = 1 之性質直接計算,得原式 = 1
by case(i)(ii)(iii) 得證
============================================================================
註1:「完全剩餘系」指各數除以 n 的餘數由小到大重排後 = {0, 1, 2,..., (n-1)}
亦即此n數當中,任兩數之除以n之餘數皆不相等!
否則,把兩數ak與bk相減,
即得 n|(a-b)k → n|(a-b) → 矛盾)
註2:視為公比 z(n) 的等比級數,直接求和。
或者觀察單位根在複數平面上之正多邊形對稱性。
============================================================================
上面這個 lemma 在講什麼?
就是只要數列當中,有週期為 n 的成份,都可以用單位根去湊。
以下用實例直接說明
※ 引述《XDXIX (didi)》之銘言:
: 大家好
: 循環數列
: 像是
: 當 n: 1, 2, 3, 4, 5, 6, 7, 8, 9,10 .....∞
: 數值: 1,-1, 1,-1, 1,-1, 1,-1, 1,-1,...循環
: 可以變成 (-1)^(n±1)
: 但是當它變比較複雜的時候 我就不會解了...
: ====================分隔線 下面是問題====================
: 一、 ∞
: 原式:Σ (cos(nπ/3)+cos(5nπ/3)-2cos(2nπ/3))
: n=1
: 當 n: 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12 .....∞
: 數值: 1, 0,-2, 0, 1, 0, 1, 0,-2, 0, 1, 0.....循環
此數列由週期為2跟6的兩個成份組成
(i)週期為 2 的部份;
0k 1k k k
z(2) + z(2) 1 + (-1)
由 a_k = ─────── = ───── → {a_k} = {0,1,0,1,....}
2 2
要弄成 {1,0,1,0,...} 只要"往左平移" 1 個數即可
k+1 k+1 k
1 + (-1) 1 - (-1)
即 a_(k+1) = ─────── = ─────
2 2
(ii)週期為 6 的部份:
0k 1k 5k
z(6) + z(6) +...+ z(6)
b_k = ───────────── → {b_k} = {0,0,0,0,0,1,0,...}
6
k+3 2(k+3) 5(k+3)
1 + z(6) + z(6) +....z(6)
需左移 3 個單位 → b_(k+3) = ───────────────────
6
原數列 c_k = a_(k+1) - 3*b_(k+3)
iθ
因等號兩邊皆為實數,故可左右同取實部(利用 Re{e } = cosθ)
k
1 - (-1) 1 2π(k+3) 4π(k+3)
c_k = ───── - ─ [1 + cos───── + cos───── +
2 2 6 6
6π(k+3) 8π(k+3) 10π(k+3)
+ cos───── + cos───── + cos───── ]
6 6 6
k
-(-1) 1 kπ 2kπ 4kπ 5kπ
= ─── - ─ [ - cos── + cos── -cos(kπ) + cos── - cos── ]
2 2 3 3 3 3
k
(-1) 1 kπ 2kπ k k kπ k 2kπ
= - ─── + ─ [cos── -cos── +(-1) -(-1) cos── +(-1) cos──]
2 2 3 3 3 3
k
1-(-1) kπ 2kπ
= ──── [cos── - cos──]
2 3 3 #
(將你寫的級數做一下和差化積,應該也能得到這個形式)
: 簡單來說就是 6 個數值為一周期,
: 當n為 偶數 時,數值皆為0;
: 當n為 3的倍數 時,數值皆為-2;
: 當n為 其它基數 時,數值皆為1。
: -----------------------------------------------------------
: 二、 ∞
: 原式:Σ (sin(2nπ/3)-sin(4nπ/3)+2sin(nπ/3))
: n=1
: 當 n: 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12 .....∞
: 數值: x, 0, 0, 0,-x, 0, x, 0, 0, 0,-x, 0,.....循環
: 也是 6 個數值為一周期,
: 在週期內 第 1 個 數值為 X
: 第 5 個 數值為 -X
: 這樣有辦法化簡嗎?? 可以的話 請教我方法 感謝:D
利用上題週期為 6 的 b_k 數列
c_k = x*b_(k+5) - x*b_(k+1)
以下自己算了(和差化積)
√3 kπ 2kπ 4kπ 5kπ
= ── * x * [sin── +sin── -sin── -sin── ]
6 3 3 3 3
: 謝謝!!!
: ※ 編輯: XDXIX 來自: 123.205.109.87 (10/20 21:09)
: 推 XII :試試a+bw^n+cw^{2n}+..+fw^{5n},w=1/2+√3/2i 10/20 21:18
: 推 oNeChanPhile:一、的第六項不是-2? 10/20 21:18
: → XDXIX :一的第六項是0 它是 1 0 -2 0 1 0 這樣在循環 10/20 21:34
: → XDXIX :@XII 那方法我不是很懂 a b c 那要怎麼排@@" 10/20 21:35
: ※ 編輯: XDXIX 來自: 123.205.109.87 (10/20 23:58)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.27.8.196
推 XDXIX :大概懂了 但是沒辦法把sin cos全部消掉嗎 變成單純的 10/21 13:26
→ XDXIX :(X)^(Y) 之類的 因為這個出來之後還要平方.. 10/21 13:26
→ XDXIX :所以想請教看看有沒有辦法像 範例一 一樣 直接變簡單 10/21 13:27
→ XDXIX :的算式 感謝 10/21 13:27