Suppose that a recursive routine were invoked to calculate F(4). How many times would a recursive call of F(1) occur? The definition of a Fibonacci number is as follows: 
$$F_0=0\\F_1=1\\F_n=F_{n-1}+F_{n-2}\text{ for } n\geq 2$$
Suppose that a recursive routine were invoked to calculate $F_4$. How many times would a recursive call of $F_1$ occur?
Do I use n=1?
 A: For small $n$ the most straightforward way to answer the question is the one suggested by Orangutango: unwrap the recurrence. However, as the comments under that answer may suggest, there’s a general result almost ready to hand.
Suppose that the recursive routine requires $c_n$ calls of $F_1$ to evaluate $F_n$. Clearly $c_0=0$ and $c_1=1$. For $n>1$ we have $F_n=F_{n-1}+F_{n-2}$, where evaluating $F_{n-1}$ requirse $c_{n-1}$ calls of $F_1$, and evaluating $F_{n-2}$ requirse $c_{n-2}$ calls of $F_1$. Thus, evaluation of $F_n$ will require $c_{n-1}+c_{n-2}$ calls of $F_1$, and we must have $c_n=c_{n-1}+c_{n-2}$ for all $n\ge2$. But all of this just says that the sequence $\langle c_n:n\ge 0\rangle$ satisfies the same recurrence and has the same initial values as the Fibonacci sequence $\langle F_n:n\ge 0\rangle$, so it must be the same sequence: $c_n=F_n$ for all $n\ge 0$.
A: Unwrap it:
$$F[4]$$ 
$$= F[3] + F[2]$$
$$= F[2] + F[1] + F[1] + F[0] $$
$$= F[1]+F[0]+ F[1] + F[1] + F[0]$$ 
$$= 3F[1]+2F[0]$$
So, it gets called three times.
