1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Characteristics Equation

  1. Sep 15, 2009 #1
    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. jcsd
  3. Sep 15, 2009 #2

    Mark44

    Staff: Mentor

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook