作者RoamingGhost (遊魂)
看板Math
標題Re: [中學] 求生成函數 初始值a_{0}=1 a_{k}=3a_{k …
時間Tue Jun 21 23:42:23 2011
※ 引述《MinusHeart (ICRT)》之銘言：
: 求生成函數 初始值a_{0}=1 a_{k}=3a_{k-1}+2
: 答案為 a_{k}=2*3^k-1
Standard procedure for solving linear recurrences using generating function:
inf
Let f(x)= sigma a_n x^n
n=0
From recurrence relation we have f(x)-3x*f(x)=1+2x+2x^2+.....=2/(1-x) - 1
=(1+x)/(1-x)
Hence f(x)= (1+x)/(1-x)(1-3x)
inf inf
By partial fraction f(x)= 2/(1-3x) - 1/(1-x) = sigma 2*3^n x^n - sigma x^n
n=0 n=0
inf
= sigma (2*3^n - 1) x^n
n=0
Thus a_n = 2*3^n - 1
QED
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 211.74.216.192
1F：→ jacky7987 :推 06/21 23:54
2F：推 MinusHeart :感謝解答 此版好多高手!! 06/22 00:22