# Determining function for recursive Fibonacci algorithm

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.

-

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

-
Thank you Aaron! Makes sense. – Yep Jan 27 '13 at 2:16

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.

-
I think it would be good for you to explain how and why - so it's helpful to the asker...and not just spit out an answer... – amWhy Jan 27 '13 at 1:39
@amWhy It seems to me like he's a programmer and he couldn't care less. – Git Gud Jan 27 '13 at 1:40
But why should s/he believe you? I'm just saying...no insult intended... – amWhy Jan 27 '13 at 1:42
If he couldn't care less, why did he post this on math stack? – Rustyn Jan 27 '13 at 1:42
Yes I would like an explanation. I'm not really just looking for the answer here as I want to understand what I'm doing. – Yep Jan 27 '13 at 1:44