Prove the number of computations produced by the Nth fibonacci number

Question

Given the generic Fibonacci function:

procedure fib(integer: n):
    if n = 0  return 0
    else if n = 1  return 1
    else return fib(n - 1) + fib(n - 2)

Prove the number of computations $C(n) = F(n + 2) + F(n - 1) - 1$ by induction.

The problem also gives:

$C(0) = C(1) = 1$ (base case)

and

$C(n) = C(n - 1) + C(n - 2) + 1$ (The number of computations recursively)

The basis step is given for $C(0)$ and $C(1)$.

The induction step is where I am confused. The answer in the back of the book says something along the lines of "the proof is simple", and offers no further explanation.

I am used to straightforward induction proofs and I'm not sure how to go about solving a recursive algorithm through induction.

Answer 1

So for the inductive step, assume it is true for some $k>1$, i.e. $C(k) = F(k+2)+F(k-1)-1$. We must show that $$ C(k+1) = F(k+3)+F(k)-1. $$ But note that since $k>1$, the last case in the algorithm is activated, and computing it requires $$ \begin{split} C(k+1) &= C(k)+C(k-1)+1 \quad \text{from the algorithm itself} \\ &= [F(k+2) + F(k-1) - 1] + [F(k+1)+F(k-2)-1] + 1 \\ &= F(k+2) + F(k+1) + F(k-1) + F(k-2) + 1 \\ &= F(k+3) + F(k) + 1 \quad \text{by properties of Fibonacci sequence} \end{split} $$

Answer 2

Guide:

From induction hypothesis, we have $$C(n-1) = F(n+1)+F(n-2)-1$$

Also, write down the expression for $C(n-2)$.

After which, write $$C(n)=C(n-1)+C(n-2)+1,$$

substituting $C(n-1)$ and $C(n-2)$ with the expressions that you have just found. Also, use the property of fibonacci sequence, $F(n)+F(n+1)=F(n+2)$.