Take the 2-minute tour ×

I have the following snippet:

public Foo(int n)
        new Foo(i)

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

share|improve this question
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
Let me amplify on my previous comments. This reminds me of when I was a "drop in math tutor" as an undergraduate. After I established a certain reputation for competence I would sometimes get questions from other subjects, like statistics and economics. I would protest that I didn't even know the terminology of these other subjects, and the person would assure me that it was "really a math question". But usually the person's translation into a math question would leave something to be desired and I would find myself trying to speedread their textbook in order to get a clue.... –  Pete L. Clark Sep 5 '11 at 21:44

3 Answers 3

up vote 1 down vote accepted

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer
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 –  VelvetThunder Sep 5 '11 at 20:35

Your Answer


