Originally Posted by

**drthea** Hello,

I am trying to understand how to solve this kind of problems but I am stuck in this.

It is given this recurrence relation:

$\displaystyle T(n) = 3T(n - 1) - 2T(n - 2), T(1)=1, T(2)=2$

and the solution is as follows:

$\displaystyle T(n) = 3T(n - 1) - 2T(n - 2)

= 7T(n - 2) - 6T(n - 3)

= 15T(n - 3) - 14T(n - 4)$

so $\displaystyle T(n)=(2^k -1)T(n-k-1)-(2^k -2)T(n-k)$

I don't get how it goes from $\displaystyle T(n) = 3T(n - 1) - 2T(n - 2)$

to $\displaystyle 7T(n - 2) - 6T(n - 3)$,

could you explain please?

Also why T(1)=1, T(2)=2 are given? Where should I use them?