Prove the Number of Additions of Fibonacci Number Algorithm

Question

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!

Answer 1

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.

Answer 2

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.

Answer 3

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$.