作者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