Results 1 to 2 of 2

Math Help - Recurrence relation problem

  1. #1
    Member javax's Avatar
    Joined
    Jan 2008
    From
    Milky Way
    Posts
    139

    Recurrence relation problem

    Hi All. I usually solve recurrence relations but I'm struggling with this one. I need to find the general term.

    A(n)= c n + A(\lfloor n/2 \rfloor) for n > 2, A(n) = 1 for  n = 2 where c-constant

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    147

    Re: Recurrence relation problem

    It's usually helpful to just calculate the first few values to "see" what's happening in a recurrence. What follows doesn't solve it, but might prove helpful.

    A(2) = 1.
    A(3) = 3c + A(floor(3/2)) = 3c + A(1). Uh-oh, A(1) isn't defined.

    A(4) = 4c + A(2) = 4c+1.
    A(5) = 5c + A(floor(5/2)) = 5c+A(2) = 5c+1.

    A(6) = 6c + A(3) = 6c+(3c+A(1)) = 9c + A(1).
    A(7) = 7c + A(floor(7/2)) = 7c+A(3) = 7c + (3c+A(1)) = 10c + A(1).

    A(8) = 8c + A(4) = 8c+ (4c+1) = 12c + 1.
    A(9) = 9c + A(floor(9/2)) = 9c+A(4) = 9c + (4c+1) = 13c + 1.

    A(10) = 10c + A(5) = 10c+(5c+1) = 15c + 1.
    A(11) = 11c + A(floor(11/2)) = 11c+A(5) = 11c + (5c+1) = 16c + 1.

    A(12) = 12c + A(6) = 12c+(9c + A(1)) = 21c + A(1).
    A(13) = 13c + A(floor(13/2)) = 13c+A(6) = 13c + (9c + A(1)) = 22c + A(1).

    A(14) = 14c + A(7) = 14c+ (10c + A(1)) = 24c + A(1).
    A(15) = 15c + A(floor(15/2)) = 15c+A(7) = 15c + (10c + A(1)) = 25c + A(1).

    A(16) = 16c + A(8) = 16c+ (12c + 1) = 28c + 1.
    A(17) = 17c + A(floor(17/2)) = 17c+A(8) = 17c + (12c + 1) = 29c + 1.

    What becomes clear from that?
    First: A(1) is left undefined.
    Second: for n>=4, we need only consider even values n = 2k, since A(2k+1) = A(2k) + c.
    Third: Look for patterns (and then try to prove inductively):
    n = 4, c-coeff = 4 (perhaps exludable as an "initial" value?)
    n = 6, c-coeff = 9
    n = 8, c-coeff = 12 (+3 from last)
    n = 10, c-coeff = 15 (+3 from last)
    n = 12, c-coeff = 21 (+6 from last)
    n = 14, c-coeff = 24 (+3 from last)
    n = 16, c-coeff = 28 (+4 from last)
    The pattern is unclear. Finding it is what remains of the problem.

    Constant term is +1 except at n even being = 6, 12, and 14, where it's +A(1).

    Note how n=6 was +A(1), so n=7 was +A(1) also. That's 2 consecutive +A(1). But that led to n = 12 and n=14 being +A(1), so 4 consecutive +A(1) (n = 12, 13, 14, 15).
    Since n = 12, 13, 14, 15 are all +A(1), will have +A(1) later for n=24, 25, 26, 27, 28, 29, 30, and 31. So those 4 consecutive +A(1) leads to the next batch of +A(1)'s being 8 consecutive.
    The pattern for the constant term should appears clear and calcuable.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 8th 2011, 07:45 AM
  2. recurrence relation problem!
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: May 9th 2011, 05:54 PM
  3. Writing up a Recurrence Relation Problem...
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 11th 2010, 06:55 PM
  4. Recurrence Relation Problem...
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 10th 2010, 03:41 PM
  5. Recurrence relation problem
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 11th 2008, 11:23 AM

Search Tags


/mathhelpforum @mathhelpforum