Results 1 to 5 of 5

Math Help - Recursive relations

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    3

    Recursive relations

    Hi everyone, i am totally stumped with this section of my coarse work, Maths is not my friend, and my father, who is a maths 1,2 and calculus teacher can't for the life of him work these two out, thus i have resorted to my last ... resort ... ANY help would be greatly appreciated in working out these recursive relations.

    a)
    an = a(n/2) + n, for n >=2, with a1 = 0
    substitute n = 2^k, solve with iteration,

    thus,
    a2^k = a2^(k-1) + 2^k
    = a2^(k-2) + 2^(k-1) + 2^k
    =a2^(k-3) + 2^(k-2) + 2^(k-1) + 2^k


    Im stumpted here on, not a clue really as all the text book examples and lecturers examples do not follow these patterns.


    Also
    b)
    an = a(n/2) + n^2, for n >=2, with a1 = 0


    Not a clue ...


    Due tomorrow so im cutting it close, otherwise its a slap on submit job. (no there were 30 other questions i've done this isn't a last minute job, last 2 questions.)


    Thank you!!
    Mathzea
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    In a), you almost solved it. You unfolded the definition three times. Generalizing from 3 to i we get

    a_{2^k}=a_{2^{k-i}}+2^{k-i+1}+2^{k-i+2}+\dots+2^{k-1}+2^{k}

    What is the limit case? Rewrite this formula when i=k-1. This can be summed up using the formula for the sum of geometric progression. Be careful with the second term, which follows a_1=0.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2010
    Posts
    3
    OH i see what you've done there, however the only information we are given is:

    for n >= 2, with a1 = 0, when n is a power of 2.

    What do you mean by the 'limit case'


    Thank you for the reply I'm still a bit lost on the following steps of solving the geometric expression .



    Mathzea.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    "Limit case" is not an official term; I meant what happens when, in the right-hand side of the equation above, you cannot unfold a_{2^{k-i}} according to the definition a_n = a_{n/2} + n. This happens when a_{2^{k-i}}=a_1, i.e., 2^{k-i}=1, i.e., k-i=0. Actually, I was wrong earlier when I suggested considering i=k-1. The limit case happens when i=k.

    I'm still a bit lost on the following steps of solving the geometric expression
    The sum of geometric progression is a standard topic that must be described, in particular, in your textbook. Maybe you can search "Pre-Algebra and Algebra" section of this forum or ask a question there?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2010
    Posts
    3
    Ah sweet, thank you very much! My dad was able to help me with the geometric equation in the end . No doubt I will be back come the next fortnight *sigh*.

    +1 Thanks again
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relations and Functions - Inverse Relations Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 13th 2011, 12:20 PM
  2. Replies: 1
    Last Post: September 19th 2011, 01:09 PM
  3. Recursive to Sum if possible
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: March 26th 2011, 03:59 PM
  4. Recursive Relations...
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: September 6th 2010, 08:49 PM
  5. Primitive Recursive vs Recursive Functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 29th 2009, 07:32 AM

Search Tags


/mathhelpforum @mathhelpforum