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.
A: If we replace the "then" branch with
f = 1

then the number of additions doesn't change, because there's never any control dependency on the returned value.
However, the changed algorithm computes $F_{n+1}$ rather than $F_n$. And the way it computes $F_{n+1}$ is by adding ones, and never using an intermediate result more than once. Therefore the additions form the internal nodes in a binary tree with 1 at each leaf, so there are $F_{n+1}$ leaves. The a binary tree has one less internal nodes than it has leaves, so there must be $F_{n+1}-1$ additions.
A: Look at your algorithm
and turn it into
a function that computes the number of
additions done.
Algorithm nFIB(n):
if n = 0 or n = 1 then
    f = 0
else
    f = nFIB(n-1) + nFIB(n-2) + 1 (for the addition)
endif
return f

Then
$nFIB(n) = nFIB(n-1) + nFIB(n-2) + 1$
and this is pretty close to
the $F_n$ recurrence
except for that
"$+1$".
To get rid of that
(and it takes some experience
to see quickly how to do this),
change it
by adding $1$ to both sides) to get
$nFIB(n)+1 = nFIB(n-1)+1 + nFIB(n-2) + 1
$.
Therefore
$nFIB(n)+1$
satisfies the same recurrence
as $F_n$
but with possibly 
a different offset,
so
$nFIB(n)-1 = F_{n+k}$
for some $k$.
Playing around gives
$k=1$,
so
$nFIB(n) = F_{n+1}-1$.
