Second order linear recursive equation

T(n) = T(n-1) + 2T(n-2) + 3 ----(1)
T(n-1) = T(n-2) + 2T(n-3) + 3 ----(2)

(1) - (2) , we have
T(n) - T(n-1) = T(n-1) + T(n-2) - 2T(n-3)
T(n) = 2T(n-1) + T(n-2) - 2T(n-3)
T(n) - 2T(n-1) - T(n-2) + 2T(n-3) = 0

Thus, the characteristic equation is,

a^3 - 2r^2 - r + 2 = 0
The roots of it is 1, -1, 2

So,
T(n) = A + B 2^n + C (-1)^n

for n = 0
0 = A + B + C ------ (1)

for n = 1
0 = A + 2B - C ------(2)

for n = 2, T(2) = 3
3 = A + 4B + C -----(3)

(3) - (1), we have B = 1
(2) - (1), we have B - 2C = 0, implies C = 1/2
So, A = -3/2

Therefore, the general solution is
T(n) = 2^n + 1/2 (-1)^n - 3/2

In second answer, there is NO careless mistake in the third row after "Therefore".
It is my mistake.

這個答案看似來比較複雜，但事實上它解釋了Characteristic Polynomial的原理。

圖片參考：http://i187.photobucket.com/albums/x22/cshung/70080319001391.jpg


圖片參考：http://i187.photobucket.com/albums/x22/cshung/70080319001392.jpg

這個方法又叫Z-Transform，在訊號分析處理上有很大的用途。