# how many times will a function print to the console?

I have the following snippet:

public Foo(int n)
{
for (int i=0; i<n; i++)
{
new Foo(i)
}
console.writeln("?")
}


For a given $n$, how many "?" will be printed?

Some testing shows that the answer is $2^n$. What is the way to reach the formula?

I got to the formula \begin{align} F(0) &= 1 \\ F(n) &= 1 + F(n-1) + \cdots + F(1) + F(0) \end{align} How do I simplify it to $2^n$?

-
I was a bit confused by the formula $F(n) = 1 + F(n-1) +... + F(1) + 1$, but I now see the last $1$ comes from $F(0)$. – TMM Sep 5 '11 at 20:45
This question is phrased in the language of computer programming. It requires some positive amount of mathematical acumen to solve, but aren't there plenty of people on SO qualified to answer questions like this? – Pete L. Clark Sep 5 '11 at 21:24
@Pete: But the content of the question is a mathematical recurrence relation, regardless of the syntax in which it is phrased, so I think it belongs fine here. Would it help if the snippet were translated to more easily understood pseudocode? – Rahul Narain Sep 5 '11 at 21:31
@Thijs: I was confused too, so I edited the formula to make it clearer (at least I hope it is clearer now). – Rahul Narain Sep 5 '11 at 21:36
@Rahul: if it's actually a math question, why should it be presented in pseudocode at all? But my point was actually the following: isn't the solving of simple recurrences like this something that CS people eat for breakfast? – Pete L. Clark Sep 5 '11 at 21:37

You have in general, $$F_n = F_{n-1} + (1+ F_0+F_1+\cdots +F_{n-2})$$ $$\Rightarrow F_{n} = 2F_{n-1}$$

It will be clear now that $F_n =2^{n}$

-

Start with $n=1$. Your recurrence says $F(1)=1+1=2=2^1$. Then assume you know $F(n)=2^n$. If you look at your recurrence, $F(n+1)=F(n)+F(n)$, where the second $F(n)$ is just all the rest of the terms in $F(n+1)$. So if $F(n)=2^n, F(n+1)=2^{n+1}$

-

Your recurrence formula looks correct. Since you have guessed an answer, try proving that it is right by long induction on $n$.

-
 Is there any nice way to open my recurssive formula? – Elad Benda Sep 5 '11 at 20:08 How would I get to the 2^n the first place ?I mean what if it was a harder pattern than: 0, 1, 2, 4, 8 ? – Elad Benda Sep 5 '11 at 20:09 It depends on the specific problem. There is nothing wrong with guessing an answer by experimentation and then proving it by induction. – Ted Sep 5 '11 at 20:12 @Elad, please clarify what you mean by "open my recursive formula". – Henning Makholm Sep 5 '11 at 20:23 @Elad Benda:For different problem use interpolation techniques (numerical analysis) to reduce it to a polynomial form – Quixotic Sep 5 '11 at 20:35