I have been trying to solve the problem below (and similar problems) but I have no clue how to tackle it. Can you please help me tackle this particular problem, and how to attack similar problems?
The question in question is question 11 at this link: http://cglab.ca/~michiel/2804/winter14exam.pdf
That was an old exam that I was trying to work through. I know he will ask a similar type of question so I would like to be prepared. Any help will be appreciated.
Since this is a multiple choice test, the best way to solve the exam question is to actually run through the computation for $n=5$. Since all of the answers are distinct for $n=5$, this will uniquely specify the answer.
As for actually solving the mathematical question, you might notice that FIB$(4)$ is called exactly once whenever FIB$(5)$ is called and exactly one more time whenever FIB$(6)$ is called. You can generalize this observation and try to find a recurrence relation for the $a_n$.