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 find a mathematical formula for this recursion?

  1. Oct 9, 2008 #1
    how to find a mathematical formula for this recursion??

    i got this recursion

    Code (Text):

    int b(int n,int count) {
      int i;
      count =a(n,count);
         for(i=0;i<n;i++)
         count =b(i,count);
         return count;
     
    b(0,0)=1
    b(1,0)=3
    b(1,1)=4
    b(2,0)=8

    the formula for function "a" is a(n,c)=2^n + c

    what is the formal way to find a formula for b
    so i could predict whats the output of each input like b(12,15)??
    i dont have any intuition
    i am looking for the formal way
     
  2. jcsd
  3. Oct 9, 2008 #2
    Re: how to find a mathematical formula for this recursion??

    this is a part of the solution but
    i cant completely understand how to get there
    and how to come to a formula from that expression

    b(n,count) = b(n,0)+count
    b(n):=b(n,0)
    b(n) = 2^n + b(0) + b(1) + b(2) + ... + b(n-1)

    and using this outputs
    b(0,0)=1
    b(1,0)=3
    b(1,1)=4
    b(2,0)=8

    in the end we need to come to the formula
    b(n,c)=c+(n+2)*2^(n-1)
     
  4. Oct 10, 2008 #3

    rcgldr

    User Avatar
    Homework Helper

    Re: how to find a mathematical formula for this recursion??

    looking at the run tree for b(3,0)
    Code (Text):

    b(3,0)
      b(0,8)
      b(1,9)
        b(0,11)
      b(2,12)
        b(0,16)
        b(1,17)
          b(0,19)
     
    Note that b(n) = 2^n + sums of powers of 2. 2^0 is added 4 = 2^2 times. 2^1 is added 2 = 2^1 times, 2^2 is added 1 = 2^0 times, so b(3) = 2^3 + (2^2 x 2^0) + (2^1 x 2^1) + (2^0 x 2^2) = 2^3 + 3 x (2^2) = 8 + 12 = 20. In general:

    [tex]b(n) = 2^n + 2^{n-1} 2^0 + 2^{n-2} 2^1 ... + 2^0 2^{n-1}[/tex]

    [tex]b(n) = 2^n + n (2^{n-1})[/tex]

    [tex]b(n) = 2 (2^{n-1}) + n (2^{n-1})[/tex]

    [tex]b(n) = (2+n) (2^{n-1})[/tex]

    Note, I added posts to the other 2 threads to explain why a(n,c) = 2^n + c.

    update - if this is a programming class, these problems seem to require a bit more recognition of mathematical series (power series in the a(n, 0) case from the first threads) than normal. Is this some special class or are these more like thought puzzles?
     
    Last edited: Oct 10, 2008
  5. Oct 11, 2008 #4
    Re: how to find a mathematical formula for this recursion??

    what chapters from discrete math
    i need to know in order to find such formulas
    ??
     
  6. Oct 11, 2008 #5

    rcgldr

    User Avatar
    Homework Helper

    Re: how to find a mathematical formula for this recursion??

    I wouldn't know. Part of 1st year of calculus includes some series stuff, but this could differ by school and textbook. In this case of the b() function above, you had to observe that the iterations were summing up n products of powers of 2 were those products were always 2^(n-1), plus the initial 2^n value. For the a() function in the previous thread, you had to observe that the iterations were summing up incrementing powers of 2, a standard power series. I don't think this would have been clear for n==2 case, I used the n==3 case to get a better idea of what was going on.
     
  7. Oct 11, 2008 #6
    Re: how to find a mathematical formula for this recursion??

    look for Recurrence Relation or Master Theorem
     
  8. Oct 12, 2008 #7
    Re: how to find a mathematical formula for this recursion??


    n==3 takes lots of time

    n==2 stretched to the limit the time i got to solve this question on the test
    in the test i only have a pen and paper
    is there any easier way to find n==3
    except doing this frontal brute force way i used for n=2 ???

    Code (Text):

    b(2,0)                                          n=2   count=0

    count=a(2,0)=4                            n=2 count=4
    for (0<2)                                      n=2  count=4 i=0

       count=b(0,4)                             n=0 count=4
                       | count=a(0,4)=5                                  
                       |  
                       |  return count=5    


     return count


    ============================================
    for(1<2)

                                                        n=2  count=5 i=1
             
       count=b(1,5)                              n=1 count=5
                       | count=a(1,5)=7                                  
                       |  for(0<1)                  n=1 count=8   i=0
                       |    count=b(0,7)=8   n=1 count=8 i=0
                       |       return count
                               

     return count


    count=8

     
     
  9. Oct 12, 2008 #8
    Re: how to find a mathematical formula for this recursion??



    i have found a different formula to b(n)

    b(0)=1
    b(1)=2+1=3
    b(2)=4+1+3=8

    b(n)=2^n +b(0) +b(1) +b(2) +.. + b(n-2)+b(n-1)

    b(n-1)=2^n +b(0) +b(1) +b(2) +.. + b(n-2)

    b(n)=b(n-1)+b(n-1) =2*b(n-1)


    which by the way is wrong because b(1) doesn't equal to 2* b(0)

    b(n)=2*b(n-1)


    i cant see any mistake in the math here
    but my formula differs to yours

    where is my mistake
    how to transform it to the formula
    b(n,c)=c+(n-2)*2^(n-1)
     
    Last edited: Oct 12, 2008
  10. Oct 12, 2008 #9

    rcgldr

    User Avatar
    Homework Helper

    Re: how to find a mathematical formula for this recursion??

    I'm not sure where you got the formula, but it appears correct.

    Although not needed, I reversed the order of the terms, which may help later:

    b(n) = 2^n + b(n-1) + b(n-2) + ... + b(2) + b(1) + b(0)
    b(0) = 2^0 = 1
    b(1) = 2^1 + b(0) = 2+1 = 3
    b(2) = 2^2 + b(1) + b(0) = 4+3+1 = 8
    b(3) = 2^3 + b(2) + b(1) + b(0) = 8 + 8 + 3 + 1 = 20

    no, it should be:
    b(n-1) = 2^(n-1) + b(0) ... + b(n-2)

    This is a mathematical type problem where a recursive formula is to be simplified into a direct equation. Usually these type of problems involve some sort of "clever" thinking. I'm still a bit surprised that this is part of a programming class, unless the class is also for mathematics.

    Assuming this is homework, we're supposed to guide you through this process, so:

    Using the formula for b(n), and expand all the b() terms in the b(3) case, and tell me what you get. Group the expanded terms in () to keep track of things. In otherwords replace the b(2) + b(1) + b(0) parts with expanded sums of powers of 2 (use 2^0 instead of 1 for the b(0) case):

    b(3) = 2^3 + b(2) + b(1) + b(0)

    After you've done the expansion, look for a way to simplify the answer. It is this part that seems to go beyond programming and more into mathematics to me.
     
    Last edited: Oct 12, 2008
  11. Oct 14, 2008 #10

    rcgldr

    User Avatar
    Homework Helper

    Re: how to find a mathematical formula for this recursion??

    b(3) = 2^3 + b(2) + b(1) + b(0)
    b(3) = 8 + (4 + 2 + 1 + 1) + (2 + 1) + (1)
    b(3) = 8 + (4) + (2 + 2) + (1 + 1 + 1 + 1)
    b(3) = 8 + 3 x (4)

    Other than observation, I couldn't figure out a different way to determine the formula.
     
  12. Oct 14, 2008 #11
    Re: how to find a mathematical formula for this recursion??

    thanks
     
  13. Oct 14, 2008 #12

    uart

    User Avatar
    Science Advisor

    Re: how to find a mathematical formula for this recursion??

    One way is to use Z transforms. http://en.wikipedia.org/wiki/Z-transform#Table_of_common_Z-transform_pairs


    define s(n) = b0 + b1 + ... bn

    Then bn = 2^n + s(n-1)

    s(n) - s(n-1) = 2^n + s(n-1)

    s(n) - 2s(n-1) = 2^n : with s0 = 1


    Taking Z transforms we get : (See Tranform 11 in linked table and Property 3 - time shifting)

    S(z) [1-2z^(-1)] = 1/[1-2z^(-1)]

    S(z) = 1/[1-2z^(-1)]^2


    Taking Inverse Z transforms we get : (Using Transform 13 and again property 3)

    s(n) = (n+1) * 2^n

    Therefore s(n-1) = n 2^(n-1)

    and finally (typo) s(n) = 2^n + s(n-1) = (2+n) 2^(n-1)

    (edit)
    and finally b(n) = 2^n + s(n-1) = (2+n) 2^(n-1)
     
    Last edited: Oct 15, 2008
  14. Oct 14, 2008 #13

    rcgldr

    User Avatar
    Homework Helper

    Re: how to find a mathematical formula for this recursion??

    Thanks, something I should learn. I got to the first part of the equations, but then didn't know how to proceed.

    Last statement should be:

    finally b(n) = 2^n + s(n-1) = (2+n) 2^(n-1)
     
    Last edited: Oct 15, 2008
  15. Oct 15, 2008 #14

    uart

    User Avatar
    Science Advisor

    Re: how to find a mathematical formula for this recursion??

    Thanks Jeff, I fixed that typo.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: How to find a mathematical formula for this recursion?
Loading...