Results 1 to 11 of 11

Math Help - Solving recurrence systems

  1. #1
    Junior Member
    Joined
    Aug 2009
    Posts
    37

    Unhappy Solving recurrence systems

    Solve the recurrence system below and dtermine a formula for the time complexity function T(n).

    T(0) = 4.
    T(n) = 5 + T(n - 1) (n > 0)

    My effort at solving is below...

    T(3) = 5 + T(2).
    T(2) = 5 + T(1).
    T(1) = 5 + T(0).

    T(3) + T(2) + T(1) = 3 * 5 + T(2) + T(1) + T(0)
    T(3) = 3 * 5 + T(0)
    T(3) = 15 + 4.

    Now try to obtain a formula for T(n) in terms of n.
    T(n) = 5 + T(n - 1).
    T(n - 1) = 5 + T(n - 2).
    T(1) = 5 + T(0).
    T(0) = 4.

    T(n) + T(n - 1) + T(1) + T(0) = 3 * 5 + T(n - 1) + T(n - 2) + T(0) + 4.

    **THIS IS WHERE MY BRAIN HITS MELTING POINT AND THE COOLANT IS RELEASED.

    I'm pretty sure the formula should be T(n) = 5 * n + 4. So,

    T(0) = 5 * 0 + 4 = 4
    T(3) = 5 * 3 + 4 = 19.

    I need to prove it though
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    \begin{array}{rcl}<br />
   {T_4 } &  =  & {5 + T_3 }  \\<br />
   {} &  =  & {5 + \left[ {5 + T_2 } \right]}  \\<br />
   {} &  =  & {5 + \left[ {5 + \left[ {5 + T_1 } \right]} \right]}  \\<br />
   {} &  =  & {\left( 3 \right)5 + 4}  \\ \end{array}
    Now is not clear what the pattern is?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,678
    Thanks
    611
    Hello, RedKMan!

    You're making it much too hard . . .


    Solve the recurrence system and determine a formula for the function T(n)..

    T(0) = 4,\quad T(n) \:=\: T(n - 1) + 5, \quad n > 0
    Crank out the first few terms . . .


    . . \begin{array}{c|c} <br />
n & T(n) \\ \hline<br />
0 & 4 \\ 1 & 9 \\ 2 & 14 \\ 3 & 19 \\ 4 & 24 \\ \vdots & \vdots \end{array}


    The sequence starts at 4 and "goes up by 5."

    It is clear that the function is: . T(n) \;=\;4 + 5n

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Aug 2009
    Posts
    37
    How does this look below:-

    Now try to obtain a formula for T(n) in terms of n.

    T(n) = 5 + T(n - 1).
    T(n - 1) = 5 + T(n - 2).
    T(2) = 5 + T(1)
    T(1) = 5 + T(0).
    T(0) = 4.

    Sum each side and equate result...

    T(n) + T(n - 1) + T(2) + T(1) + T(0) = T(n - 1) + T(n - 2) + T(1) + T(0) + 4 + (n - 1) * 5 + 4.

    Subtract terms that appear on both sides...

    T(n) = (n - 1) * 5 + 4 = 5n - 5 + 4 = 5n + 4 = 4 + 5n.

    I'm a bit dubious about my algebra above, I feel like I'm close, I can taste it. Is it close / correct?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member Renji Rodrigo's Avatar
    Joined
    Sep 2009
    From
    Rio de janeiro
    Posts
    38
    You can do this

     t(k+1)=t(k)+5
    so

     t(k+1)-t(k) =5

    apply the summation  \sum^{n-1}_{k=0}
    on the both sides, the first is a telescoping summation

    \sum^{n-1}_{k=0} t(k+1)-t(k)  = t(n)-t(0)=t(n)-4 =\sum^{n-1}_{k=0} 5=5n
    so
    t(n)=5n +4
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by RedKMan View Post
    I'm pretty sure the formula should be T(n) = 5 * n + 4. So,

    T(0) = 5 * 0 + 4 = 4
    T(3) = 5 * 3 + 4 = 19.

    I need to prove it though
    Well I would hope that after reading these posts and thinking about them, you will no longer be "pretty sure" but rather 100% sure that the solution is T(n) = 5n + 4.

    As for proof, if you're comfortable with inductive proofs, this one is very easy. Using mathematical induction is the typical way to prove these kinds of things.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Aug 2009
    Posts
    37
    Problem is I need to use algebra to arrive at the formula rather than guessing and then using induction to prove it. Thats why I'm hoping someone can check my,

    T(n) = 5 + T(n - 1).
    T(n - 1) = 5 + T(n - 2).
    T(2) = 5 + T(1)
    T(1) = 5 + T(0).
    T(0) = 4.

    Sum each side and equate result...

    T(n) + T(n - 1) + T(2) + T(1) + T(0) = T(n - 1) + T(n - 2) + T(1) + T(0) + 4 + (n - 1) * 5 + 4.

    Subtract terms that appear on both sides...

    T(n) = (n - 1) * 5 + 4 = 5n - 5 + 4 = 5n + 4 = 4 + 5n.

    Thus T(n) = 4 + 5n
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by RedKMan View Post
    Problem is I need to use algebra to arrive at the formula rather than guessing and then using induction to prove it.
    There is no guessing involved. You can see that the expression is T(n) = 5n + 4 if you just look hard enough.

    It's like this sequence:

    a(0) = 1
    a(n) = 2*a(n-1), n>0

    I can just see that this is a(n) = 2^n and there is absolutely no guessing involved.

    Although to be fair, guessing is a valid approach for many of these types of problems.

    Quote Originally Posted by RedKMan View Post
    Thats why I'm hoping someone can check my,


    T(n) = 5 + T(n - 1).
    T(n - 1) = 5 + T(n - 2).
    T(2) = 5 + T(1)
    T(1) = 5 + T(0).
    T(0) = 4.

    Sum each side and equate result...

    T(n) + T(n - 1) + T(2) + T(1) + T(0) = T(n - 1) + T(n - 2) + T(1) + T(0) + 4 + (n - 1) * 5 + 4.

    ...
    Where did this last equation come from??? When I sum each side I get

    T(n) + T(n - 1) + T(2) + T(1) + T(0) = 5 + T(n - 1) + 5 + T(n - 2) + 5 + T(1) + 5 + T(0) + 4
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Aug 2009
    Posts
    37
    Your correct, when you sum each side you do get,

    T(n) + T(n - 1) + T(2) + T(1) + T(0) = 5 + T(n - 1) + 5 + T(n - 2) + 5 + T(1) + 5 + T(0) + 4

    Removing all the terms that appear on both sides, I get,

    T(n) + T(2) = 5 + 5 + T(n - 2) + 5 + 5 + 4

    Problem is I think I need to get rid of that T(2) term on the right some how??
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by RedKMan View Post
    Your correct, when you sum each side you do get,

    T(n) + T(n - 1) + T(2) + T(1) + T(0) = 5 + T(n - 1) + 5 + T(n - 2) + 5 + T(1) + 5 + T(0) + 4

    Removing all the terms that appear on both sides, I get,

    T(n) + T(2) = 5 + 5 + T(n - 2) + 5 + 5 + 4

    Problem is I think I need to get rid of that T(2) term on the right some how??
    I could be wrong, but I don't think your approach will succeed.

    If you really dislike induction, Renji Rodrigo's post looks like a great option for you.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Aug 2009
    Posts
    37
    I've gone with induction and it all works out.

    With the time complexity function being T(n) = 5n + 4.

    I've worked out the Big Oh value to be:-

    f(n) = 5n. Giving O(n) of linear type.

    Does that look right?

    Thanks for all the help everyone.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Solving a recurrence relation.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: January 11th 2011, 02:05 PM
  2. Need help solving recurrence formula
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 7th 2009, 12:08 PM
  3. Solving Recurrence Relation
    Posted in the Calculus Forum
    Replies: 0
    Last Post: February 16th 2009, 04:43 PM
  4. Solving a recurrence relation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 12th 2009, 10:19 PM
  5. Replies: 3
    Last Post: October 11th 2006, 09:15 PM

Search Tags


/mathhelpforum @mathhelpforum