Why does the sign change here?

46 Views Asked by At

They give the recurrence relation as:

$$T(n) − 4T(n − 1) + 3T(n − 2) = 0,\ T(0) = 0,\ T(1) = 2$$

And then they say it can be written as the following for $n > 1$:

$$T(n) = 4T(n − 1) − 3T(n − 2)\ \mathbf{ if\ } n > 1$$

How did they change the $+$ in middle to subtraction? Why isn't instead that $4T(n - 1)$ is negative?

1

There are 1 best solutions below

0
On BEST ANSWER

$$T(n)-4T(n-1)+3T(n-2)=0 \Rightarrow \\ T(n)-4T(n-1)+3T(n-2)+(4T(n-1)-3T(n-2))=4T(n-1)-3T(n-2) \\ \Rightarrow T(n)=4T(n-1)-3T(n-2)$$