Q:

Prove the Number of Additions of Fibonacci Number Algorithm

I am studying for a final exam and I'm having trouble with this question:
The following recursive algorithm FIB takes as input an integer $n \ge 0$ and returns the $n$-th Fibonacci number $F_n$:
Algorithm FIB(n):

    if n = 0 or n = 1 then
        f = n
    else
        f = FIB(n-1) + FIB(n-2)
    endif
    return f

Let $a_n$ be the amount of additions made by the algorithm FIB(n), the total number of times that the $+$-function in the else-case is called. Prove that for all $n \ge 0$
$$a_n = F_{n+1} - 1.$$
I am thinking I should use recurrence to solve it but I'm completely lost. Thanks in advance!

A:

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.

