$1.$ The following recursive algorithm takes an integer parameter n and returns the nth Fibonacci number. The Fibonacci numbers are as follows: $0,1,1,2,3,5,8,13,21,34,55,$ etc. We can expect fib$(0)=>0,$ fib$(1)=>1,$ fib$(2)=>1,$ fib$(3)=>2,$ etc.

In general, fib$($n$)=$ fib$($n$-1)+$ fib$($n$-2)$

Prove the function fib is correct.

Precondition: n is a non$-$negative integer

Postcondition: fib returns Fibonacci value of n

long fib$($long n$)$

$\{$

if $($n $==0||$ n $==1)$

return n;

else

return fib$($n$-1)+$ fib$($n$-2)$;

$\}$