Prove correctness of recursive Fibonacci algorithm, using proof by induction

I'm studying for the computer science GRE, and as an exercise I need to provide a recursive algorithm to compute Fibonacci numbers and show its correctness by mathematical induction.

Here is my recursive version of an algorithm to compute Fibonacci numbers:

Fibonacci(n):
    if n = 0 then     // base case
        return 0
    elseif n = 1 then // base case
        return 1
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2)
    endif

How can I prove the correctness of this algorithm by induction?

(Seems like it may be a duplicate, but the "Related" questions don't seem to be too close, with the possible exception of "this one)

The proof is by induction on $n$. Consider the cases $n = 0$ and $n = 1$. In these cases, the algorithm presented returns $0$ and $1$, which may as well be the 0th and 1st Fibonacci numbers (assuming a reasonable definition of Fibonacci numbers for which these values are correct).

Now, assume that the algorithm returns the correct Fibonacci number for all $n$ (i.e., the nth Fibonacci number) for all $n \leq k$ where $k \geq 1$.

We must show that the algorithm returns the correct value for $k+1$, i.e., the (k+1)th Fibonacci number. By the induction hypothesis, $k \geq 1$, so we are in the else case. We return Fibonacci(k) + Fibonacci(k-1) in this case. By the induction hypothesis, we know that Fibonacci(k) will evaluate to the kth Fibonacci number, and Fibonacci(k-1) will evaluate to the (k-1)th Fibonacci number. By definition, the (k+1)th Fibonacci number equals the sum of the kth and (k-1)th Fibonacci numbers, so we have that the algorithm returns the (k+1)th Fibonacci number on input $k+1$.

The proof of the claim follows by induction on $n$.

StackExchange Computer Science Q#14025, answer score: 5