How to find a mathematical formula for this recursion?

[transgalactic]

how to find a mathematical formula for this recursion??

i got this recursion

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 what's the output of each input like b(12,15)??
i don't have any intuition
i am looking for the formal way

 

[transgalactic]

this is a part of the solution but
i can't 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)

 

[rcgldr]

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

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:

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

$$b(n) = 2^n + n (2^{n-1})$$

$$b(n) = 2 (2^{n-1}) + n (2^{n-1})$$

$$b(n) = (2+n) (2^{n-1})$$

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?

 

[transgalactic]

what chapters from discrete math
i need to know in order to find such formulas
??

 

[rcgldr]

what chapters from discrete math
i need to know in order to find such formulas

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.

 

[Tacomablack]

what chapters from discrete math
i need to know in order to find such formulas
??

look for Recurrence Relation or Master Theorem

 

[transgalactic]

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.

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 ?

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

 

[transgalactic]

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

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:

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

$$b(n) = 2^n + n (2^{n-1})$$

$$b(n) = 2 (2^{n-1}) + n (2^{n-1})$$

$$b(n) = (2+n) (2^{n-1})$$

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?

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 can't 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)

 

[rcgldr]

i have found a different formula to b(n)
b(n) = 2^n + b(0) + b(1) + b(2) +... + b(n-2) + b(n-1)

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

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

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

how to transform it to the formula: b(n,c)=c+(n+2)*2^(n-1)?

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.

 

[rcgldr]

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.

 

[transgalactic]

thanks

 

[uart]

One way is to use Z transforms. http://en.wikipedia.org/wiki/Z-transform#Table_of_common_Z-transform_pairsdefine 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 = 1Taking 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)]^2Taking 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)

 

[rcgldr]

One way is to use Z transforms.

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)

 

[uart]

Thanks Jeff, I fixed that typo.