how many times will a function print to the console?

Question

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

Answer 1

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

Answer 2

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

Answer 3

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