I am studying for the final exam in my Discrete Mathematics class and came upon the following problem on the study guide we were given.
Given the following algorithm:
If $n = 0$, then $f(n) = 0$
else if $n = 1$, then $f(n) = 1$
else $f(n) = f(n-1) + f(n-2)$
For $n\geq 0$, let $c(n)$ be the total number of additions for calculating $f(n)$. (Hint: $c(0) = 0$, $c(1) = 0$, $c(2) = 1$). For $n\geq 2$ express $c(n)$ using $c(n-1)$ and $c(n-2)$.
Also determine if $c(n)\geq 2^{(n-2)/2}$ for $n\geq 2$ and prove your answer.
I believe for the first part we are just to write an equation to find $c(n)$, which I think should be fairly easy, but the second part has me a bit stumped as to how to prove it…
Thank you in advance!
Best Answer
For $n>2$, in order to calculate $f(n)$ using this recurrence you must first calculate $f(n-1)$, which takes $c(n-1)$ additions, and $f(n-2)$, which takes another $c(n-2)$ additions, and then add the results, which takes one more addition. This will give you the desired recurrence for $c(n)$.
Once you have that, you want to prove or disprove that
$$c(n)\ge 2^{(n-2)/2}\tag{1}$$
for $n\ge 2$. At this point, if not earlier, it would be a good idea to calculate some values of $c(n)$. You should get the following values:
$$\begin{array}{rcc} n:&2&3&4&5&6&7&8\\ c(n):&1&2&4&7&12&20&33 \end{array}$$
If you compare that bottom row with the corresponding values of $2^{(n-2)/1}$, you can make a pretty good guess that $(1)$ holds for $n\ge 2$. You can try proving it directly by induction, but it might be easier to take a detour.
Compare that bottom row with $f(n+1)$, and you can discover a formula for the $c(n)$’s in terms of $f(n)$’s, one that’s easily proved by induction on $n$. Then you can use the fact that the Fibonacci sequence is almost a geometric sequence with ratio $\varphi=\frac12(1+\sqrt5)$.