Characteristics Equation for Solving Recurrences

[needhelp83]

Solve the following recurrences using the characteristics equation
T(n) = 4T(n-1) – 3T(n-2)
T(1) = 1
T(2) = 2

T(n) – 4T(n-1) + 3T (n-2) = 0
r^n r^n-1 r^n-2

r^n – 4r^n-1 + 3r^n-2= 0
r^n-2 (r^2 -4r + 3) = 0

r = 3, r= 1
T(n) = C1 3n + C2 1n

For T(1) =1
C1 3^1 + C2 1^1 = 1

For T(2)=2
C1 3^2 + C2 1^2 = 2
9C1 + C2 = 2

Solving C1
C2 = 1 - 3C1
9C1 + (1 - 3C1 ) = 2
6C1 + 1 = 2
C1 = 1/6

Solving for C2
3*(1/6) + C2 = 1
(½) + C2 = 1
C2 = ½

for T(2) = 2
C1 3^2 + C2 1^2 = 1 for T(2) = 2

Therefore: T(n) = (1/6) 3n + (½) 1n

Did I do this correctly?

 

[Mark44]

So from your work, T(n) = n (= 3/6*n + n/2).

Check for yourself. Does your nonrecursive formula give you the same values as your recursive formula? If so, then it looks like you did the problem correctly.