作者adxis (acer)
看板Prob_Solve
標題Re: [轉錄][問題] 遞迴關係求解
時間Fri Sep 4 00:21:17 2009
※ [本文轉錄自 Math 看板]
作者: adxis (acer) 看板: Math
標題: Re: [轉錄][問題] 遞迴關係求解
時間: Fri Sep 4 00:20:52 2009
※ 引述《vicwk (Victor)》之銘言：
: ※ 引述《adxis (acer)》之銘言：
: : S(0) = 0, C(0) = 0
: : S(n) = S(n-1) + 2*C(n-1)
: : C(n) = n-1 + S(n) / n
後來自己有算出來
過程大致上跟板友差不多
先化簡成
n-1
C(n) = (n-1) + (2/n) Σ C(i)
i=0
multiplied by n
n-1
n C(n) = n(n-1) + 2 Σ C(i) -(1)
i=0
telescoping
n-2
(n-1)C(n-1) = (n-1)(n-2) + 2 Σ C(i) -(2)
i=0
(1) - (2)
n C(n) - (n-1) C(n-1) = 2(n-1) + 2 C(n-1)
n C(n) = 2(n-1) + (n+1) C(n-1)
divided by n(n+1)
C(n) / (n+1) = 2(n-1)/n(n+1) + n C(n-1) -(a)
telescoping
C(n-1) / n = 2n/(n-1)(n) + (n-1) C(n-2) -(b)
C(n-2) / (n-1) = 2(n-1)/(n-2)(n-1) + (n-2) C(n-3) -(c)
...
C(2) / 3 = 1/3 + C(1) / 2 -(d)
adding a~d
n+1
C(n) / (n+1) = 2 Σ [ (i-2)/ i(i-1) ]
i=3
n+1 n+1
= 2 [ Σ (2/i) - Σ 1/(i-1) ]
i=3 i=3
Let H(n) = 1 + 1/2 + 1/3 + ... + 1/n ≒ r + ln(n), and r ≒ 0.577
C(n) / (n+1) = 2 { [ 2( H(n+1) - 3/2 ) ] - [ H(n+1) - (n+2)/(n+1) ] }
C(n) = (n+1)( 2H(n+1) - 2 ) - (2n -1)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.123.218.30
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.123.218.30