2007-10-23

離散第五章第四節 ~誰可以幫我解釋這題為何不能特徵多項式法解遞迴


不想因為這節是生成函數法解遞迴界就那樣解
我的第一個想法是特徵多項式法
但是代入邊界條件 居然得出C1=0 , C2=0

3 則留言:

線代離散助教(wynne) 提到...

問題出在特徵多項式上, 你所列的式子是齊次型的, 即f(r)=0, 然而此題的型式卻不是固定的, 因為題目給定了f(2)=1, 則當r=2時, 它不會成立

p.s. 所以其實你的方法是可以解的, 只要假設該特徵多項式是在"r>=3"時成立, 而在求c1,c2時可代入r=1, r=2的f(r)作為邊界條件

提到...

請問為什麼不能用它給的邊界條件a0=a1=0
來求c1,c2

線代離散助教(wynne) 提到...

因為c1和c2是在式子成立的情況下算出來的, 且當r>=3時式子才成立, 則此時要求的ar所必須要找的邊界為ar-1, ar-2, 所以是a2,a1

或者反過來說, 若你用a1,a0去算會是對的
那表示a2代入式子也會成立, 則矛盾f(2)=1