Recursive fibonacci algorithm correctnes? [proof by induction]

Question

im studying for the computer science GRE, as an exercise i need to provide a recursive fibonacci algorithm and show its correctness by mathematical induction.

here is my recursive version of fibonacci algorithm:

Fibonacci(n):

    IF n = 0 then    // a stopping case
        return 0
    elseif n = 1 then    // another stopping case
        return 1
    else
        return Fibonacci(n-1) + Fibonacci(n-2)  // closer to stopping case
    endif

How can i proof the previous algorithm by induction?

Answer 1

There’s not actually very much to do, since the algorithm so closely follows the recursive definition of the Fibonacci numbers.

Clearly $\operatorname{Fibonacci}(0)=0=F_0$ and $\operatorname{Fibonacci}(1)=1=F_1$; that gets the induction off the ground. Now suppose that $m>1$, and your algorithm returns the correct value for all non-negative integers $n<m$. Then on the input $m$ it returns $$\operatorname{Fibonacci}(m-1)+\operatorname{Fibonacci}(m-2)\;,$$ which by the induction hypothesis is $F_{m-1}+F_{m-2}=F_m$, so it returns the correct value for all non-negative integers $n\le m$.