Re: [理工] [離散] 找遞迴規則

[christianSK (AG)]

※ 引述《mqazz1 (無法顯示)》之銘言：
: Find a formula for a(n) satisfying the relation a(n) = -2a(n-2) - a(n-4)
: with a(0)=0, a(1)=1, a(2)=2, a(3)=3
: 請問這題為什麼要分n為奇數或偶數分別討論來求解?
: 又或者是有其它的方法嗎?
: 書上的答案是 a(n) =  -n(-1)^(n/2)            if n>=0 為偶數
:                      (3-2n)(-1)^((n-1)/2)    if n>=1 為奇數
: 謝謝
剛剛算了一下

我覺得應該是因為特徵方程式 (一般而言是 a(n) = A*a(n-1) + B*a(n-2) )

這題遞迴關係差了兩項 可以把原本數列看成兩個差一項的遞迴關係 ( even(n), odd(n) )

也就是說:

               a(0) = even(0)             a(1) = odd(0)

               a(2) = even(1)             a(3) = odd(1)

                   ...                        ...

               a(n) = even(n/2)           a(n) = odd(n-1/2)  {n=even,odd resp}

就會得到我們習慣的特徵方程式

        even (n) = -2*even(n-1) - even(n-2)       when n:even

        odd(n)   = -2*odd(n-1) - odd(n-2)         wneh n:odd

接下來就是各別求彼此的遞迴關係式了

(i) n:even

因為特徵根 = -1 (2重根)

->  even(k) = (A + B*k) * (-1)^k   where k >= 0

因為 even(0) = a(0) = 0,  even(1) = a(2) = 2

->  代入可以得到  A = 0 , B = -2

->  even(k) = (-2*k)*(-1)^k        ( 注意這裡足碼是 "k" )

因為 k = n/2

->  a(n) = -2*(n/2)*(-1)^(n/2)   when n:even

->  a(n) = -n*(-1)^(n/2)         when n:even

(ii) n:odd  (做法跟偶數類似)

因為特徵根 = -1 (2重根)

->  odd(k) = (A + B*k) * (-1)^k    where k >= 0

因為 odd(0) = a(1) = 1,   odd(1) = a(3) =  3

->  代入可以得到  A = 1, B = -4

->  odd(k) = (1-4K)*(-1)^k         ( 注意這裡足碼是 "k" )

因為 k = (n-1) / 2

->  a(n) =  1- 4*(n-1/2) * (-1)^(n-1/2)  when n:odd

->  a(n) = (3-2n) * (n-1/2)              when n:odd

(i), (ii)合併就會得到原po提供的答案了

應該沒算錯吧 ^^"

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.25.189.11
推 mqazz1:請問一下 要分奇數和偶數 這兩個case討論的原因..
→ mqazz1:是因為a(n) = -2a(n-2) - a(n-4)這遞迴式子
→ mqazz1:缺了a(n-1)和a(n-3)的關係嗎?
→ christianSK:也可以想像那兩項是0 這樣會解出特徵根為虛數
→ christianSK:我的做法只是把原本的問題轉換成我所習慣看到的
→ christianSK:也許也有可以直接求特徵根的方式 這我就不是很清楚了