2
$\begingroup$

I have the following snippet:

public Foo(int n)
{
    for (int i=0; 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$?

  • 1
    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?2011-09-05
  • 0
    @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?2011-09-05
  • 0
    @Thijs: I was confused too, so I edited the formula to make it clearer (at least I hope it is clearer now).2011-09-05
  • 0
    @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?2011-09-05
  • 0
    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....2011-09-05
  • 0
    ...What I thought (and still think) is weird is: why couldn't they just ask the statistics / economics tutor? (Possible answer: they didn't tutor for as many hours as I did!) It's not as though the basic mathematics that comes up in these related disciplines is beyond the means of skilled practitioners of these disciplines. On the contrary, anyone I have ever met with a real mastery of CS or stat or econ was fully on top of the math that intervenes in those disciplines.2011-09-05

3 Answers 3

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

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

2

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

  • 0
    Is there any nice way to open my recurssive formula?2011-09-05
  • 0
    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 ?2011-09-05
  • 0
    It depends on the specific problem. There is nothing wrong with guessing an answer by experimentation and then proving it by induction.2011-09-05
  • 0
    @Elad, please clarify what you mean by "open my recursive formula".2011-09-05
  • 0
    @Elad Benda:For different problem use interpolation techniques (numerical analysis) to reduce it to a polynomial form2011-09-05