Computing FIB(0) and FIB(1) has no additions, as it returns n.
Computing FIB(n) has one addition, plus as many additions as FIB(n-1) and FIB(n-2) have.
So, we have
$$a_n = \begin{cases}
0, & n \in \{0, 1\}, \\
a_{n-1} + 1 + a_{n-2}, & n > 1.
\end{cases}$$
Now, use the mathematical induction to check that $a_n = F_{n+1} - 1$ and comment if you get stuck.
Here is how I would prove this. The base case is obviously true as you pointed out, so let us assume that for $n$ people, the number of questions we have to ask is at most $3(n-1)$.
There are $n+1$ people in a room. Ask one person, call him Al, if he knows a second person, call him Bob. Now there are two possibilities, either Al knows Bob or he doesn't.
If Al knows Bob, then Al cannot be a celebrity so examine if there is a celebrity out of the other $n$ people, using the $3(n-1)$ questions. This gives a total of $3(n-1)+1$ questions so far. If there is no celebrity in this group then there are no celebrities in the room. If there is a celebrity in the group, call him Carl. Now ask Carl if he knows Al, and ask Al if he knows Carl. These two questions will reveal if Carl is truly a celebrity. This gives a total of $3(n-1)+1+2 =3((n+1)-1)$ questions the desired result.
If Al does not know Bob, then follow the same procedure as above but exclude Bob instead of Al from the $n$ people, and ask Carl if he knows Bob and ask Bob if he knows Carl if there is a celebrity in that group of $n$ people. This again gives a total of $3((n+1)-1$ questions.
Along with the base case, this proves that for any finite number of people in a room, you can determine if there is a celebrity in the room with at most $3(n-1)$ questions.
Best Answer
Start with small examples. For inductive/recursive problems you need them for your base case anyway, plus in most of the math I've seen working with small problems gives you the experience you need to figure out the general pattern.
For convenience, let $f(n)$ denote the number of times $\text{Pow}$ is called to compute $\text{Pow}(n)$. You don't really need to do this, but I'm super lazy and don't want to write that horrendously long phrase every time.
As you said, this is a homework problem that ends with the recurrence formula and not with a closed-form solution, so I'm not going to go any further in my explanation. Keep working with a few small examples if this isn't enough to get started, but hopefully the pattern is clear by now.