Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

3 Answers 3

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.

share|improve this answer
    
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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.