Prove correctness of the following algorithm for computing the nth Fibonacci number.
algorithm fastfib (integer n) if n<0return0; else if n = 0 return 0; else if n = 1 return 1; else a ← 1; b ← 0; for i from 2 to n do t ← a; a ← a + b; b ← t; return a; end
Not 100% how to complete this with proof by induction. How I started: Base case: 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.
Now we assume that the algorithm return the correct Fibonacci number for n ( the nth Fibonacci number) for all n<= k where k >= 1. I wasn't sure if I was on right track and where to move from here.