Results 1 to 2 of 2

Math Help - Recurrence Relations

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Recurrence Relations

    I am asked to solve the following recurrence relations...that is find a closed form for them. I am supposed to do this using "back substitution"

    a) a sub n = 4a sub n-1 + 5 for all n > 0 and a sub 0 = 2.

    b) b sub n = b sub n-1 + n^2 for all n > 0 and b sub 0 = 3.

    Any suggestions?? Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,667
    Thanks
    298
    Awards
    1
    Quote Originally Posted by jzellt View Post
    a) a sub n = 4a sub n-1 + 5 for all n > 0 and a sub 0 = 2.
    We need to "massage" this problem a little first:
    a_n = 4a_{n - 1} + 5

    a_n - 4a_{n - 1} = 5

    This implies that
    a_{n + 1} - 4a_n = 5

    Thus
    (a_{n + 1} - 4a_n) - (a_n - 4a_{n - 1}) = 0

    a_{n + 1} - 5a_n + 4a_{n - 1} = 0

    Finally:
    a_{n + 2} - 5a_{n + 1} + 4a_n = 0

    Solve the characteristic equation:
    m^2 - 5m + 4 = 0

    (m - 4)(m - 1) = 0

    m = 1, 4

    Thus the solution is of the form:
    a_n = A \cdot 4^n + B \cdot 1^n

    a_n = A \cdot 4^n + B

    Your initial condition states: a_0 = 2. So
    a_0 = A \cdot 4^0 + B = 2

    A + B = 2

    B = 2 - A

    Thus
    a_n = A \cdot 4^n + (2 - A)

    So we see that there is no unique solution here.

    You try the other one.

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence Relations
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: July 28th 2011, 02:50 PM
  2. Recurrence relations
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: February 24th 2011, 09:45 AM
  3. Recurrence relations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 1st 2010, 06:59 AM
  4. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 07:56 PM
  5. recurrence relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 10th 2008, 11:57 PM

Search Tags


/mathhelpforum @mathhelpforum