Help understanding Recursive algorithm question We have a function that is defined recursively by $f(0)=f_0$, $f(1)=f_1$ and $f(n+2) = f(n)+f(n+1)$ for $n\geq0$

For $n\geq0$, let $c(n)$ be the total number of additions for calculating
  $f(n)$ using $f_0$ and $f_1 $ as input with $c(0) = 0$ and $c(1) = 0$. For $n \geq 2$,
  express $c(n)$ using $c(n-1) $ and $c(n-2)$
Determine if $c(n)\geq2^{(n-2)/2}$ for $n\geq2$ and prove your answer.

I'm lost as to what to do with this question.
 A: This is a badly formulated problem, the claim is probably wrong. 


*

*If the task is just to compute $f(n)$, then one can use matrix powers as
$$
\begin{bmatrix}f(n)\\f(n-1)\end{bmatrix}
=
\begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-1}
\begin{bmatrix}f(1)\\f(0)\end{bmatrix}
$$
These matrix powers can be computed by halving-and-squaring so that one needs $O(\log_2(n))$ additions and multiplications for the computation of the single value $f(n)$.

*If one wants to compute all of $f(0),f(1),f(2),...,f(n)$, then the step increasing $n$ adds one addition to the computational effort, resulting in $O(n)$, more precisely $(n-1)$, additions.

*Of course, to demonstrate the dangers of blind implementation of recursive functions, the exponential estimate results from the worst possible implementation of the computation of $f(n)$.
See the computation of the Fibonacci-sequence for further details such as complexity in bit-operations.
A: Hint:
$$c(n+2)=c(n+1)+c(n)+1$$
Solve this to get $c(n)$ and prove that $c(n) \ge 2^{\frac{n-2}{2}}$ by induction.
A: Try doing by induction:
Base step:
$$ c(2) = 2 \ge 2^{(2-2)/2} = 1$$
Inductive step:
if $c(n) \ge 2^{(n-2)/2} \rightarrow c(n+1) \ge 2^{((n+1)-2)/2}$
You probably need to think the way to calculate how $c(n)$ increases whit each value of $n$
A: In reality, only n-1 additions are needed. The only formula that we can use is f(n+2) = f (n+1) + f (n) for n >= 0. If f0 and f1 are given, the only value this formula allows us to calculate is 
f2 = f1 + f0 (applying the formula with n = 0)

Now with f2 available as well, the only value the formula allows us to calculate is
f3 = f2 + f1 (applying the formula with n = 1)

and so on. 
I'd express the number of additions as
c(n) = c(n−1) + 1

or if you insist on using c(n-2) in the formula then 
c(n) = c(n−1) + 1 + 0 * c(n-2)

