作者taitin (小南)
看板Grad-ProbAsk
標題Re: [理工] [離散]-解遞迴式的問題
時間Wed Aug 26 22:06:03 2009
回第一題
B(x)的分母先拆解
2x^2+x^3=1-2x-x^2+2x^3-(1-2x-3x^2+x^3)
=(1-2x-x^2+2x^3)/2 -(1/2-x-5/2x^2)
得b(x)=1/2+(-1/2+x+5/2x^2)/(1-2x-x^2+2x^3)
因為是B(x)拆出來的，所以跟你直接去拆一樣
b0=0 n>=1的原因是因為
如果你把 n= 0 帶入 bn會得到 -3/2+1/6+5/6 !=0
因此必須而外寫出來 但n=1 帶入bn為0 因此>=1都成立
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.222.74
※ 編輯: taitin 來自: 61.230.222.74 (08/26 22:07)
1F：→ taitin:下一題概念一樣，為了要讓式子滿足boundary 08/26 22:09
2F：→ taitin:你也可以寫ar=(....) r>=1 a0=0 就可以了 08/26 22:11
※ 編輯: taitin 來自: 61.230.222.74 (08/26 22:22)
3F：推 brasil:嗯嗯 boundary的部分我懂了 不過還是不太懂為什麼要拆出1/2 08/26 23:15
4F：→ brasil:這樣不是比較慢嗎?? 因為我看答案 1/2也不在bn裡面呀.. 08/26 23:17
其實這是比較正規的做法，因為就分母來說(1-x)(1+x)(1-2x)為三次式
但是要做部分分式時，為了要比較係數，分母要二次式才行。
ex 1/(1-x) 通分時要乘上另外兩個式子，因此分子最高只有二次式。
二次式再怎麼相減也減不出三次式。因此這邊要先想辦法消掉x^3
但其實像課本提供用帶x=1 x=-1 x=1/2 等於左式帶值得方法也會正確(也就是你對的原因)
可以在不提出1/2的情況下，先把後面的生成函數算出來，也就是課本71頁第五行
然而這並不是正確的生成函數，必須滿足在n=0時的生成條件，因此再補加1/2上去即可。
不過這算有點偷懶的作法，不曉得會不會給滿分。
生成函數的意義在 X^0的係數即是b0的值，x^1的係數是b1的值
因此1/2只會影響b0的值，但卻不會影響bn(n>=1)以上的值
這也是為什麼最後答案要分兩段來寫的詳細原因
※ 編輯: taitin 來自: 61.230.222.74 (08/27 01:15)
5F：推 brasil:嗯嗯 我懂了 謝謝你的解答~ 08/27 22:31