# Math Help - calculation of recursion

1. ## calculation of recursion

How often will occur * ?

void Star(int n) {
for (i=0;i<n;i++) {
printf("*");
Star(i);
}
}

I thing so $2^n - 1$, but I don`t know how I can count it.

2. ## Re: calculation of recursion

You are right about the number of *. Let's call the number of * printed by a call to Star(n) by $s_n$. The program gives rise to the recurrence relation on $s_n$:

$s_n=\sum_{i=0}^{n-1}(1+s_i)=n+\sum_{i=0}^{n-1}s_i$.

After you have a recurrence relation, you can calculate the first several values and make a hypothesis about the general formula, but you have already done this. Then you need to prove this hypothesis, i.e., $s_n=2^n-1$ for all n, by induction on n using the recurrence relation.