Re: [理工] [離散]-解遞迴式的問題

[taitin (小南)]

回第一題

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)
→ taitin:下一題概念一樣，為了要讓式子滿足boundary
→ taitin:你也可以寫ar=(....) r>=1 a0=0 就可以了
※ 編輯: taitin          來自: 61.230.222.74        (08/26 22:22)
推 brasil:嗯嗯 boundary的部分我懂了 不過還是不太懂為什麼要拆出1/2
→ brasil:這樣不是比較慢嗎?? 因為我看答案 1/2也不在bn裡面呀..
其實這是比較正規的做法，因為就分母來說(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)
推 brasil:嗯嗯 我懂了 謝謝你的解答~