# How to find a mathematical formula for this recursion?

1. Oct 9, 2008

### transgalactic

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. Oct 9, 2008

### transgalactic

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)

3. Oct 10, 2008

### rcgldr

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:

$$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?

Last edited: Oct 10, 2008
4. Oct 11, 2008

### transgalactic

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
??

5. Oct 11, 2008

### rcgldr

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.

6. Oct 11, 2008

### Tacomablack

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

look for Recurrence Relation or Master Theorem

7. Oct 12, 2008

### transgalactic

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

8. Oct 12, 2008

### transgalactic

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
9. Oct 12, 2008

### rcgldr

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
10. Oct 14, 2008

### rcgldr

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.

11. Oct 14, 2008

### transgalactic

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

thanks

12. Oct 14, 2008

### uart

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
13. Oct 14, 2008

### rcgldr

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
14. Oct 15, 2008

### uart

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

Thanks Jeff, I fixed that typo.