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?

It should be easy to plug a few numbers in and see for yourself.

Hope this doesn't come across as stupid, but how do I test with values. What exactly am I looking for when I test?

You have two separate formulas for T(n). If you want to see if they're equivalent, you could plug in 3 into both of the formulas and see if the results are the same. If they're different, then you made a mistake. If they're the same, it doesn't prove you did things correctly, because you could have gotten lucky. But if you try plugging in a few different values and get the same results, that should give you confidence of your correctness.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.