Results 1 to 6 of 6
Like Tree3Thanks
  • 1 Post By Prove It
  • 1 Post By BobP
  • 1 Post By BobP

Math Help - T(n) questions

  1. #1
    Member
    Joined
    Nov 2013
    From
    Australia
    Posts
    215
    Thanks
    49

    T(n) questions

    Could someone help me with these questions please.
    I really don't know where to start.
    Thank you.

    1) T(n)=7T(n-4)+n


    2) T(n)=2T(n/3)+n log n

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,829
    Thanks
    1602

    Re: T(n) questions

    There are not any questions posted here, only equations. What are you trying to do with these equations?
    Thanks from Melody2
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2013
    From
    Australia
    Posts
    215
    Thanks
    49

    Re: T(n) questions

    Thank you Prove It.
    I really have no idea. I was actually wondering if i even had a question. Thanks for clearing that up.
    Maybe they were intended as simultaneous equations. I really don't know.
    Regards,
    Melody.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jun 2009
    Posts
    661
    Thanks
    133

    Re: T(n) questions

    Hi Melody

    I suspect that these are difference equations.

    Take the first one for example, T(n)=7T(n-4)+n.

    That would imply that T(4)=7T(0)+4, \quad T(5)=7T(1)+5, \quad T(6)=7T(2)+6 and so on.

    The object of the exercise is to find an expression for T(n).

    The general solution of the equation is quite messy (and I would guess that it is not what is required), but the particular solution is relatively easy to find.

    Assume that T(n)=An + B for some constants A \text{ and } B and substitute into the difference equation, treating it as an identity.

    Solve, and you should find that T(n)=-\frac{n}{6}-\frac{7}{9}=\text{ (for convenience )}-\frac{3n}{18}-\frac{14}{18}.

    So,

    T(0)=-14/18, \quad T(1)=-17/18, \quad T(2)=-20/18, \quad T(3)=-23/18,

    T(4)=-26/18, \quad T(5)=-29/18, \quad T(6)=-32/18

    and so on.

    Check to see that these satisfy the three example equations I gave earlier.

    Try your luck with the second one, I've not attempted it yet.
    Thanks from Melody2
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Nov 2013
    From
    Australia
    Posts
    215
    Thanks
    49

    Re: T(n) questions

    Quote Originally Posted by BobP View Post
    Hi Melody

    I suspect that these are difference equations.

    Take the first one for example, T(n)=7T(n-4)+n.

    That would imply that T(4)=7T(0)+4, \quad T(5)=7T(1)+5, \quad T(6)=7T(2)+6 and so on.

    The object of the exercise is to find an expression for T(n).

    The general solution of the equation is quite messy (and I would guess that it is not what is required), but the particular solution is relatively easy to find.

    Assume that T(n)=An + B for some constants A \text{ and } B and substitute into the difference equation, treating it as an identity.
    Why would i assume the above line and how would that lead to the below line?

    Quote Originally Posted by BobP View Post
    Solve, and you should find that T(n)=-\frac{n}{6}-\frac{7}{9}=\text{ (for convenience )}-\frac{3n}{18}-\frac{14}{18}.

    So,

    T(0)=-14/18, \quad T(1)=-17/18, \quad T(2)=-20/18, \quad T(3)=-23/18,

    T(4)=-26/18, \quad T(5)=-29/18, \quad T(6)=-32/18

    and so on.

    Check to see that these satisfy the three example equations I gave earlier.
    Thanks BobP,
    I have include a question inside - I can't get this multi quote thing to work. I separated the two bits myself.
    Please can someone tell me what the trick is to using multi quote
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Jun 2009
    Posts
    661
    Thanks
    133

    Re: T(n) questions

    The method I used is known as a 'trial solution method', and it is just that. You try something, if it works fine, if not try something else. With practice it's usually possible to guess what the solution looks like.
    Have you done any work on second order ODE's with constant coefficients ? That's where your most likely to come across it. It's a commonly taught method for finding the Particular Integral. The general solution of such an equation will consist of the Particular Integral plus a Complementary Function (which is the solution of the corresponding homogeneous equation and which will contain two arbitrary constants). It's pretty much the same for the difference equation we are discussing, its general solution consists of two parts, a Particular Solution (which is what I've found), plus the solution of the corresponding homogeneous equation, (which I haven't).

    For the equation T(n)=7T(n-4)+n, we 'guess' that the solution is of the form T(n)=An+B where A \text{ and } B are constants, to be calculated.

    Substitution into the equation gets us An+B=7\{A(n-4)+B\}+n,

    and on rearranging, -6An+28A-6B=n.

    This is to be considered as an identity, that is, it has to be true for all values of n.

    That implies that A=-1/6 \text{ and }B=-7/9, (the part without the n in it must equal zero).

    In answer to your other question, I struggle with one quote let alone two or more.
    Thanks from Melody2
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: November 1st 2012, 06:30 AM
  2. Various questions
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: April 27th 2009, 05:58 AM
  3. Questions and more questions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 1st 2008, 11:27 PM
  4. Replies: 4
    Last Post: July 19th 2008, 08:18 PM
  5. Replies: 3
    Last Post: August 1st 2005, 02:53 AM

Search Tags


/mathhelpforum @mathhelpforum