解遞?關係式? - 考試

※ 引述《pinky94 (pinky)》之銘言：
: 請問87清大資訊的這題要怎麼解遞?關係式?麻煩可以列出詳細的計算過程嗎?
: Let f(n)=2f(n/3)+4 for n = 3^k,k>=1 and f(1)=2,evaluate f(729)
先用定義域轉換

n = 3^k, k = log_3 n

f( 3^k ) = 2f( 3^(k-1) ) + 4

再解線性非齊次式

a_k = 2a_(k-1)+4
a_(k-1) = 2a_(k-2)+4
兩式相減

a_k - 3a_(k-1) + 2a_(k-2) = 0
r^2 - 3r + 2 = 0
(r-2)(r-1)=0

通解為
a_k = c1 x k^0 x 2^k + c2 x k^0 x 1^k

代入f(n) 用消去法 求C1,C2

依題意 a_k = c1 x k^0 x 2^k + c2 x k^0 x 1^k
k=0,n= 3^k = 3^0 =1,f(1)=2,a_k= a_0 = c1 x 0^0 x 2^0 + c2 x 0^0 x 1^0 =2
k=1,n= 3^k = 3^1 =3,f(3)=8,a_k= a_1 = c1 x 1^0 x 2^1 + c2 x 1^0 x 1^1 =8
兩式相減，得
c1=6, c2=-4
f(n)= a_k = (6 x 2^k) - 4 = ( 6 x 2^(log_3 n) ) - 4

--