# 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 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 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
show 2 more comments

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