# 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!

-

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.

-
Am I correct with my induction? I've done it on paper and uploaded an image: i.imgur.com/a9ZxNt7.jpg – pyramid Oct 17 '13 at 1:18
@pyramid No. First, you need to check $a_0$ and $a_1$, because recursion for $a_n$ depends on the previous two elements ($a_{n-2}$ and $a_{n-1}$). Second, for $a_{k+1}$ you go from $F_{k+1+1}$ which you want to prove, so you cannot use it. Rather, put $a_{k+1} = a_{(k+1)-1} + 1 + a_{(k+1)-2}$ (from the recurision) $= a_k + a_{k-1}$, then use the assumption on $a_k$ and $a_{k-1}$ and see that you get the result $F_{(k+1)+1}-1$. – Vedran Šego Oct 17 '13 at 2:08

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.

-

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

-