1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to solve this recurrence

  1. Nov 17, 2014 #1
    1. The problem statement, all variables and given/known data
    ##T(n) = 2 T(n-1) + n, n \geq 2##
    ##T(1) = 1##
    2. Relevant equations


    3. The attempt at a solution
    I'm using recursion tree method to solve the above recurrence
    Ques.jpg

    T(n) = Summation of non-leaf nodes + leaf nodes
    ##T(n) = n + 2(n-1) + 2^2(n-2) + ... + 2^{n-1}##
     
  2. jcsd
  3. Nov 17, 2014 #2

    jedishrfu

    Staff: Mentor

    So what is your question?
     
  4. Nov 17, 2014 #3

    NascentOxygen

    User Avatar

    Staff: Mentor

    This thread recurrs thrice.
     
  5. Nov 17, 2014 #4

    rcgldr

    User Avatar
    Homework Helper

    Each thread had a separate problem. Maybe they should have been combined.

    T(n+1) = T(n) + floor(sqrt(n+1))
    T(1) = 1.
    (I assumed that ⌊ ⌋ meant the integer floor of the sqrt).

    Note that floor(sqrt(1->3)) = 1, floor(sqrt(4 -> 8)) = 2, floor(sqrt(9->15)) = 3, ... .

    T(m^2) = m + 1*0 + 3*1 + 5*2 + 7*3 + ... + (2m-1)(m-1)
    T(m^2) = m + sum i=1 to m: (2i - 1)(i - 1)

    Which is a cubic equation of the form (I'll let you solve this one):

    T(m^2) = a m^3 + b m^2 + c m

    I don't know if there's a more generic method to solve this.

    - - -

    T(n) = 2 T(n/2) + 2
    T(1)=2
    Code (Text):


    n=2                               2
                               2             2


    n=4                               2
                               2             2
                            2     2       2     2  


    n=8                               2
                               2             2
                            2     2       2     2  
                           2 2   2 2     2 2   2 2

    sum i=1 to log2(2n) : 2^i
    2 T(n) - T(n) = T(n):

    2 T(n) =        4 + 8 + 16 + ... + 2^(log2(2n)) + 2^(log2(4n))
      T(n) =    2 + 4 + 8 + 16 + ... + 2^(log2(2n))
    ----------------------------------------
      T(n) =   -2                                   + 2^(log2(4n))
      T(n) =   -2                                   + 4n
      T(n) = 4n - 2
     
    - - -

    For the summation series in the first post above, I used power series method, subracting 1 x series from 2 x series:


    Code (Text):

    2(T(n)) =        (2)(n  ) + (2^2)(n-1) + (2^3)(n-2) + ... + 2^(n-1)(2) + 2^(n)
      T(n)  = (1)n + (2)(n-1) + (2^2)(n-2) + (2^3)(n-3) + ... + 2^(n-1)(1)
    ----------------------------------------------------------------------------
      T(n)  =   -n + (2)      + (2^2)      + (2^3)            + 2^(n-1)    + 2^(n)

    2(T(n)+n) =       (2^2) + (2^3) + ... + 2^(n-1) + 2^(n) + 2^(n+1)
      T(n)+n  = (2) + (2^2) + (2^3) + ... + 2^(n-1) + 2^(n)
    -----------------------------------------------------------------
      T(n)+n  = -2                                          + 2^(n+1)

    T(n) = 2^(n+1) - n - 2
     
     
    Last edited: Nov 17, 2014
  6. Nov 17, 2014 #5

    Mark44

    Staff: Mentor

    The other two copies have been deleted.

    Edit: The other two copies were deleted in error. They have been reinstated.
     
    Last edited: Nov 17, 2014
  7. Nov 17, 2014 #6
    as the height of the tree is n-1. So series would be
    ##T(n) = n + 2(n-1) + 2^2(n-2) + ... + 2^{n-3}(n-[n-3]) + 2^{n-1}##
    on solving with your approach I'm ending up with different ans
    ##2T(n) - T(n) = T(n) = n + 2 + 2^2 + 2^3 + ... + 2^{n-3} + 2{n-2}(n-[n-3]) + 2^{n-1} + 2##
    ##T(n) = n -1 - \frac{7}{2} 2^n##
     
  8. Nov 17, 2014 #7

    rcgldr

    User Avatar
    Homework Helper

    A terms is missing, it should be:

    ##T(n) = n + 2(n-1) + 2^2(n-2) + ... + 2^{n-3}(3) + 2^{n-2}(2)+ 2^{n-1}##

    Then 2 T(n) - T(n) is

    ## -n + 2 + 2^2 + 2^3 + ... + 2^n ##

    and you continue with T(n)+n as shown in my previous post.
     
  9. Nov 18, 2014 #8
    hmm Sorry little mistake

    ##T(n) = n + 2(n-1) + 2^2(n-2) + ... + 2^{n-2}(n-[n-2]) + 2^{n-1}##
    ##2*T(n) = 2*n + 2^2(n-1) + 2^3(n-2) + ... + 2^{n-1}(n-[n-2]) + 2^{n}##

    ##2*T(n) - T(n) = - n + 2 + 2^2 + ... + 2^{n-2} + 2^{n-1} + 2^n##
    ##T(n) = - n + 2 + 2^2 + ... + 2^{n-2} + 2^{n-1} + 2^n + 2^0 - 2^0##
    ##T(n) = - n + 2^0 + 2^1 + 2^2 + ... + 2^{n-2} + 2^{n-1} + 2^n - 2^0##
    Now We can directly apply sum of GP formula here

    ##T(n) = - n + \frac{2^{n+1} -1}{2-1} - 2^0##
    ##T(n) = 2^{n+1} - n - 2##

    By the way what is this "Power Series Method". All I can find on internet is "Power Series Method" for differential equations.
     
  10. Nov 18, 2014 #9

    rcgldr

    User Avatar
    Homework Helper

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: How to solve this recurrence
Loading...