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)    endifHow can I prove the correctness of this algorithm by induction?
Prove correctness of recursive Fibonacci algorithm, using proof by induction
algorithms;algorithm analysis;correctness proof;induction