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

  • 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
    @Elad Benda:For di$f$ferent problem use interpolation techniques (numerical analysis) to reduce it to a polynomial form2011-09-05