0

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?

2
Contributors
3
Replies
4
Views
7 Years
Discussion Span
Last Post by Rashakil Fol
0

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

Edited by needhelp83: n/a

0

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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.