# How to find a mathematical formula for this recursion?

how to find a mathematical formula for this recursion??

i got this recursion

Code:
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

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)

rcgldr
Homework Helper

looking at the run tree for b(3,0)
Code:
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:

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

rcgldr
Homework Helper

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.

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

look for Recurrence Relation or Master Theorem

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

Code:
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

looking at the run tree for b(3,0)
Code:
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 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:
rcgldr
Homework Helper

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.

Last edited:
rcgldr
Homework Helper

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.

thanks

uart

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:
rcgldr
Homework Helper

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)

Last edited:
uart