Determining function for recursive Fibonacci algorithm

Question

I'm given a function:

int fib(int n) {
    if (n == 0 || n == 1) return n;
    return fib(n - 1) + fib(n - 2);
}

from which I am supposed to determine a function of n that expresses the number of additions performed.

Running this through some inputs, I see a pattern:

$$ \begin{array}{c|lcr} n & \text{Additions} \\ \hline 1 & 1\\ 2 & 2\\ 3 & 4\\ 4 & 7\\ 5 & 12\\ 6 & 20\\ 7 & 33\\ \end{array} $$

So what I can determine is that between each step it looks like it adds the Fibonacci number for n onto the previous number. Does anyone have any thoughts on how I should determine a function for this? I do not understand these concepts very well unfortunately and it is scaring me.

Answer 1

Let $F(n)$ be the $n$th Fibonacci number, and let $G(n)$ be the number of additions required to compute it. To calculate $F(n)$, we must calculate $F(n-1)$ and $F(n-2)$, and then perform one more addition. Therefore we have the recurrence

$$G(n)=G(n-1)+G(n-2)+1,$$

which we can (adding one to both sides) rewrite as

$$(G(n)+1)=(G(n-1)+1)+(G(n-2)+1).$$

Therefore, we see that the sequence $G(n)+1$ satisfies the same recurrence relation as the Fibonacci sequence. Because $G(0)+1=G(1)+1=1=F(1)=F(2)$, we will have (by induction or otherwise) that $G(n)+1=F(n+1)$. This gives us our formula. Git Gud's answer is just an explicit way (the Binet Formula) of writing out $F(n)$.

Answer 2

Your sequence is $$\displaystyle g(n)=\frac{1}{\sqrt{5}}\Biggl(\biggl(\frac{1+\sqrt{5}}{2}\biggr)^{n+2}-\biggl(\frac{1-\sqrt{5}}{2}\biggr)^{n+2}\Biggr)-1$$

How does one get to this formula?

You described $g(n)$ as adding the $n^{th}$ Fibonacci number to the previous element in the sequence. Another way to look at it is noticing that it is the $(n+2)^{th}$ Fibonacci number subtracted by $1$. So if you happen to know the formula for the $n^{th}$ Fibonacci number, it's easy to get $g(n)$ as you just have to subtract $1$. And that's exactly what I did. The formula for the $n^{th}$ Fibonacci number is given by $$F(n)=\frac{1}{\sqrt{5}}\Biggl(\biggl(\frac{1+\sqrt{5}}{2}\biggr)^{n}-\biggl(\frac{1-\sqrt{5}}{2}\biggr)^{n}\Biggr).$$

How does one find this formula or prove it works? If you're given the formula, one way to prove it is by induction. If you're not given the formula, you can find it resorting to methods to find recurrence relation formulas.